【yukicoder】No.45 回転寿司
yukicoderさんの問題
参考書
難しさ（初心者目線）
・考え方***
・実装***
・面白さ***
コード
#include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> #include <bitset> using namespace std; #define ll long long #define PI acos(-1.0) #define FOR(I,A,B) for(int I = (A); I < (B); ++I) //方針 //N<=10^3なので使うor使わないの愚直に全探索はO(2^N)??なので無理 //動的計画法を用いる //dp[N+1][use] //N個目まで調べた時Nを使った時(use=1)の美味しさの和の最大とNを使ってない時(use=0)の最大 int main(){ int N; cin >> N; //dp int dp[N+1][2]; FOR(i, 0, N+1) FOR(j, 0, 2) dp[i][j] = -1; dp[0][0] = 0; //動的計画法 FOR(i, 0, N){ int v; cin >> v; //実際はif必要ない //一個前が使用していないなら使ってもいいし使わなくてもいい if(dp[i][0]>=0){ dp[i+1][0] = max(dp[i+1][0], dp[i][0]); dp[i+1][1] = max(dp[i+1][1], dp[i][0] + v); } //一個前が使用してたら次使用しない if(dp[i][1]>=0){ dp[i+1][0] = max(dp[i+1][0], dp[i][1]); } } cout << max(dp[N][0], dp[N][1]) << endl; }
コメント
動的計画法を用いることでO(N)で解くことができた.
i回目を使わないときはi-1回目に使っていない場合と使っている場合があるどっちかの最大値を用いる.
i回目を使うときはi-1回目に使っていない場合だけという考え方も同じ.
【POJ】食物連鎖
POJの問題を解きました.
http://poj.org/problem?id=1182
参考書
難しさ(初心者目線)
・考え方****
・実装****
・面白さ****
問題文
N匹の動物がいます.
動物には番号がついており(1,2,…,N)です.
また、動物はA,B,Cの3種類のみとします.
この世には食物連鎖があり、ここでは以下が成り立ちます.
・AがBを食べる
・BがCを食べる
・CがAを食べる
さて、動物学を学んでるこうたくんにN匹の動物についての情報をK個聞きました.
情報は以下のような形式です.
type1：xとyは同じ種類
type2：xはyを食べる
しかしこうたくんは天然ぼけなので全て正しいことを言うわけではありません.
i個目の情報がi-1個目以下の情報と矛盾する場合とNより大きい番号の情報が与えられる場合があります.
これらの情報は無視します.
K個の情報が与えられるので何個の情報が無視されるか求めてください.
情報はtype x yの順で与えられます.
制約
1≦N≦50000
0≦K≦100000
入力
N K
type_1 x_1 y_1
.
.
.
type_K x_K y_K
出力
何個の情報が無視されるか
ヒント
・「同じ種類」「弱肉強食」の管理にUnion-Find木を使う
・種類の情報が与えられていないのでxがA,B,Cの時を同時に考える
コード
まだTime Limit Exceetedしてしまいます.
#include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> #include <bitset> using namespace std; #define pb push_back #define mp make_pair #define ll long long #define PI acos(-1.0) #define ALL(A) ((A).begin(), (A).end()) #define vsort(v) sort(v.begin(),v.end()) #define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define MAX_N 50000 int par[MAX_N*3]; //oya int myrank[MAX_N*3]; //ki no hu ka sa //////////////// //Union-Find木// //////////////// // n要素で初期化 void init(int n){ FOR(i, 0, n){ //最初は全部が根 //par mean 親 par[i] = i; myrank[i] = 0; } } //木の根を求める int find(int x){ //根なら根の番号を返す if(par[x] == x) return x; // 途中経過の親も根にしとく else return par[x] = find(par[x]); } //xとyの属する集合を併合 void unite(int x, int y){ x = find(x); y = find(y); if(x == y) return; if(myrank[x] < myrank[y]){ par[x] = y; }else{ par[y] = x; if(myrank[x] == myrank[y]) myrank[x]++; } } bool same(int x, int y){ return find(x) == find(y); } int main(){ int N, K; cin >> N >> K; int type, x, y; //Union-Find treeを初期化 //x, x+N, x+2Nをx-A,x-B,x-Cの要素とする //xがA,B,Cの3パターンについて矛盾がないか調べることができる //食物連鎖がある動物を同じグループに入れる init(N * 3); int ans = 0; FOR(k, 0, K){ cin >> type >> x >> y; //0からに合わせる x--;y--; //ありえない数字 if(x<0 || x>=N || y<0 || y>=N){ ans++; continue; } //弱肉強食xがyを食う if(type == 2){ //xがyを食うんだからx_Aとy_Aが同じグループだとダメ //x_Aとy_Cが同じグループだと強弱が逆だからダメ if(same(x, y) || same(x, y + 2 * N)) ans++; //矛盾がなかったら情報を更新 else{ unite(x, y + N); unite(x + N, y + 2 * N); unite(x + 2 * N, y); } } else{ //同じなのに違う種類だったら矛盾 if(same(x, y + N) || same(x, y + 2 * N)) ans++; //矛盾がなかったら情報を更新 else{ unite(x, y); unite(x + N, y + N); unite(x + 2 * N, y + 2 * N); } } } cout << ans << endl; }
コメント
種類の情報がないので難しくて解けなかった.
「食物連鎖」と「同じ種類」を表すためにUnion-Find木を用いている.
【CODEFORCES】Pupils Redistribution
CODEFORCEの問題を解きました.
http://codeforces.com/contest/779/problem/A
難しさ（初心者目線）
・考え方**
・実装*
・面白さ*
問題
幸多高校には2つのクラス（A,B）があります.
クラスの人数は共にn人です.
クラス対抗プログラミングコンテストを行ったところ、
クラスAとクラスBのそれぞれの人の成績がa_1,a_2,…,a_n,b_1,b_2,…,b_nとなりました.
成績は1,2,3,4,5点でつけられます.
片方のクラスが極端に強くなってしまってはつまらないので、
それぞれのクラスの人の成績の和が等しくなるように生徒を交換したいです.
交換は1人対1人で行います.
それぞれのクラスの生徒の成績が与えられるので、
最小で何回の交換を行うことで、クラスAとクラスBの生徒の成績の和を等しくできるか求めてください.
制約
1≦n≦100（整数）
1≦a_i,b_i≦5（整数）
入力
n
a_1 a_2 … a_n
b_1 b_2 … b_n
出力
最小値を出力
等しくできない場合は-1を出力
方針
・それぞれの成績の人の人数が偶数でないといけない
・それぞれの成績の人の人数が偶数の場合O(n)で解くことができる
コード
WhyamIhereさんのコード参考にしました.
#include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> using namespace std; #define pb push_back #define mp make_pair #define ll long long #define PI acos(-1.0) #define ALL(A) ((A).begin(), (A).end()) #define vsort(v) sort(v.begin(),v.end()) #define FOR(I,A,B) for(int I = (A); I < (B); ++I) int main(){ int n; cin >> n; //a[i]:クラスAの成績iが何人いるか //total[i]:クラスA,Bで成績iが何人いるか int a[6] = {0}, b[6] = {0}, total[6] = {0}; FOR(i, 0, n){ int input; cin >> input; a[input]++;total[input]++; } FOR(i, 0, n){ int input; cin >> input; b[input]++;total[input]++; } //それぞれの成績の人が偶数でないと二つのクラスに分けられない FOR(i, 1, 6){ if(total[i]%2==1){ cout << -1 << endl; return 0; } } //分けられる場合 //目指す値との差が2*xならx回交換すれば良い int ans = 0; FOR(i, 1, 6){ ans += abs(total[i] / 2 - a[i]); } ans /= 2; cout << ans << endl; }
【CODEFORCES】Weird Rounding
CODEFORCEの問題を解いた.
http://codeforces.com/contest/779/problem/B
難しさ（初心者目線）
・考え方*
・実装*
・面白さ*
問題
コウタ君は数をで割るのが大好きです.
今日は整数nをで割ろうと思います.
コウタ君はnがで割り切れないと怒るので、
割り切れるようにいくつかの桁の数字を削除してあげてください.
削除すべき数の最小値を出力してください.
最上位の桁は0ではありません.
削除したら桁が1つ少なくなります.
例えば30020で十の位の2を削除したら3000になります.
削除する必要がない場合は0を出力してください.
入力
0≦n≦2 000 000 000（整数）
1≦k≦9（整数）
出力
最小値を出力
ヒント
コード
WhyamIhereさんのコード参考にしました.
#include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> using namespace std; #define pb push_back #define mp make_pair #define ll long long #define PI acos(-1.0) #define ALL(A) ((A).begin(), (A).end()) #define vsort(v) sort(v.begin(),v.end()) #define FOR(I,A,B) for(int I = (A); I < (B); ++I) int main(){ //stringに格納した方が楽 string s; int k; cin >> s >> k; //0の数を数える int zero = 0; FOR(i, 0, s.length()){ if(s[i]=='0') zero++; } int dels = 0; //0の数が1の位から数えてkになると割り切れる if(k <= zero){ zero = 0; for(int i=s.length()-1; i>=0; --i){ if(s[i]=='0'){ zero++; }else{ dels++; } if(zero>=k) break; } cout << dels << endl; return 0; } //0にしないと割り切れない(0はどんな数字でも割り切れる) else{ cout << s.length()-1 << endl; return 0; } }
コメント
string使えばよかった.
【yukicoder】No.47 ポケットを叩くとビスケットが２倍
yukicoderさんの問題です.
http://yukicoder.me/problems/no/47
難しさ（初心者目線）
・考え方*
・実装
・面白さ**
ヒント
コード
#include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> #include <bitset> using namespace std; #define ll long long #define PI acos(-1.0) #define FOR(I,A,B) for(int I = (A); I < (B); ++I) //最初は1枚しかないのでN-2^k>=0を満たす最大のkを求める //=0がなり立てばkが答え //>ならば足りない枚数をポケットに入れて叩けばOK //持っている枚数>足りない枚数を満たしている //答えはk+1 int main(){ ll int N; cin >> N; int k = 0; while(N-pow(2, k)>0) k++; cout << k << endl; }
コメント
【yukicoder】No.3 ビットすごろく
yukicoderさんの問題
http://yukicoder.me/problems/no/3
参考書
難しさ（初心者目線）
・考え方***
・実装***
・面白さ***
以下にヒントがあります.
ヒント
幅優先全探索の問題.
コード
#include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> #include <bitset> using namespace std; #define ll long long #define PI acos(-1.0) #define FOR(I,A,B) for(int I = (A); I < (B); ++I) //方針 //2進数にした時の1の個数はbitsetか1<<iを使えば良い? //----> __builtin_popcountめちゃ便利だった //各マスに到達できる最小の回数を設定（初期値はINF） //移動した時に最小値を更新できたらqueueに保存(1~N以外はcontinue) //queueから一個取り出して次のマスを考える //queueが空になったら終わり int main(){ int N; cin >> N; int bit1[N+1]; //マスごとの2進数にした時の1の数を保存しておく FOR(i, 0, N+1){ bit1[i] = __builtin_popcount(i); } //quに次に始点となるマス番号を保存 queue<int> qu; qu.push(1); //マスまで行くための最小値初期はINF int d[N+1]; int INF = 99999999; fill(d, d+N+1, INF); d[1] = 0; while(!qu.empty()){ //今見ている場所 int now_x = qu.front(); qu.pop(); //Nに着いてたら次は調べない if(now_x == N) continue; //次に見る場所の候補 int next_x1 = now_x + bit1[now_x]; int next_x2 = now_x - bit1[now_x]; //次見る場所が1~Nの中にあるかどうか if(next_x1 >= 1 && next_x1 <= N){ //短い経路だったら次も調べる if(d[next_x1] > d[now_x] + 1){ qu.push(next_x1); d[next_x1] = d[now_x] + 1; } } if(next_x2 >= 1 && next_x2 <= N){ if(d[next_x2] > d[now_x] + 1){ qu.push(next_x2); d[next_x2] = d[now_x] + 1; } } } cout << (d[N]==INF ? -1 : d[N]+1) << endl; }
コメント
2進数にした時の1の数を求める方法どうやるか迷ってたけど
__builtin_popcountめちゃ便利だった.
bitset使ってもできるようです
1の数が求められたらあとは幅優先全探索すればOK
【CODEFORCES】Code For 1
CODEFORCESの問題
http://codeforces.com/contest/768/problem/B
プログラミングコンテストの参考書
難しさ
・考え方***
・実装***
・面白さ*****
問題文（日本語訳）
コウタ君はある整数xを,x mod 2,
に分解するのが好きです.
コウタ君は整数nが与えられたので、nが0か1になるまで上記の分解をし1が何個あるか知りたいと思いました.
例えばn=10の場合は[10]->[5 0 5]->[2 1 2 0 2 1 2]->[1 0 1 1 1 0 1 0 1 0 1 1 1 0 1]となり、1の数は10です.
しかし昨夜徹夜でゲームをしていたコウタ君は眠いです.
そこであなたはコウタ君の代わりに[n]を0か1になるまで分解した時に左からlとrの間にある1の数を数えてください.
入力
ただし、[tex:r-l≦105]
出力
lからrの間にある1の数
lとrにある1も含む
方針
・愚直に実装して全部の01求めようとしたら地球爆発するのでlとrの間だけ調べるように工夫する
・深さ優先全探索？再帰関数使う
コード
色々な方のコードを参考にしています.
#include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> #include <bitset> using namespace std; #define ll long long #define PI acos(-1.0) #define FOR(I,A,B) for(int I = (A); I < (B); ++I) //入力 ll int l, r; //全部分解したら長さがどのくらいになるか ll getLength(ll x){ return (x <= 1) ? 1 : (getLength(x/2)) * 2 + 1 ; } //nを分解,Lはnが広がるであろう左端,Rは右端 int dfs(ll n, ll L, ll R){ //範囲外ならこれ以上探索しない if(L > r || R < l) return 0; //おかしいのでreturn 0 if(L>R) return 0; //0か1になったら出力 if(n<=1){ if(L>=l && R<=r) return n; else return 0; } //分解した時の中心 ll m = (L + R) / 2; return dfs(n/2, L, m-1) + dfs(n%2, m, m) + dfs(n/2, m+1, R); } int main(){ ll n; cin >> n >> l >> r; cout << dfs(n, 1, getLength(n)) << endl; }
