At Coder 6
お次は7/20にあったAtCoder6。
はじめての全問完答でした。
Problem A 宝くじ
問題
0-9のうち6個を重複せずに選ぶくじがある。
当選の判定は当選番号（６つの数字）＋ボーナス数字により判定され、
- 当選番号と全ての数字が一致したのなら1等
- 5つの数字が一致し、残りの一つがボーナス数字なら2等
- 5つの数字が一致したのなら3等
- 4つの数字が一致したのなら4等
- 3つの数字が一致したのなら5等
という規則になっている。
当選番号・ボーナス番号・自分が選んだ数字を与え、何等だったかを判定せよ。ハズレならば0を返せ。
考えたこと
当選番号と選んだ番号ソートして見比べればいいんじゃね？とか思ったら
当選番号：0,1,2,3,4,5
選んだ番号：1,2,3,4,5,6
とかの場合に猛烈に残念な結果を起こすことが判明。
諦めて全探索を行うことにする。
この問題文、当選番号に重複があっても良いといっているような気がするが、
選んだ番号が重複していないと言っているので、
選んだ数字が0が２個だけど、当選番号は0が１個だから、一つしかマッチしない！
みたいな、微妙なケースを考えなくても良い。
コード
vector<int> E; vector<int> L; int B; for( int i = 0 ; i < 6 ; i++ ){ int e; cin >> e; E.push_back(e); } cin >> B; for( int i = 0 ; i < 6 ; i++ ){ int e; cin >> e; L.push_back(e); } int count = 0; bool flag = false; for( int i = 0 ; i < 6 ; i++ ){ bool tmp = true; for( int j = 0 ; j < 6 ; j++ ){ if( L[i] == E[j] ){ tmp = false; count++; break; } } if( tmp && L[i] == B ) flag=true; } int ans = 0; if( count == 6 ) ans = 1; else if( count == 5 && flag ) ans = 2; else if( count == 5 ) ans = 3; else if( count == 4 ) ans = 4; else if( count == 3 ) ans = 5; cout << ans << endl; return 0;
problem B あみだくじ
問題
一箇所のあたりがあるあみだくじを与えられるので、あたりを引くためには左から何番目を選べば良いか答えよ
考えたこと
あみだくじって実質1からNまでの数列の並び替えと解釈できるので、
それを愚直に実行してやれば、左から何番目があたりのところに行き着くかがわかる。
コード
int N,L; cin >> N >> L; vector<int> vec; for( int i = 0 ; i < N ; i++ ){ vec.push_back(i+1); } string tm; getline( cin, tm); for( int i = 0 ; i < L ; i++ ){ string tmp; getline(cin,tmp); for( int j = 0 ; j+1 < N ; j++ ){ int ind = j*2+1; if( tmp[ind] == '-' ){ swap( vec[j], vec[j+1] ); } } } string tmp; getline(cin,tmp); int ind=0; while( tmp[ind*2] != 'o' ) ind++; cout << vec[ind]<<endl; return 0;
problem C 積み重ね
問題
重さの違う箱がじゅんじゅんにやってくるので、高橋くんはそれをじゅんじゅんに積み重ねていきたい。
しかし、軽い箱の上に重い箱を置くと潰れてしまうので、下にある段ボールの重さは上にある段ボールの重さ以上で無くてはならない。
段ボールの塔（？）の数の最小値を答えよ。
考えたこと
Greedyで解けと俺の直感が言っている…！
もうちょっとまじめに言うと、
与えられた箱をどのように処理するかについて、以下のパターンが考えられる
- 自分より重い箱の中で、最も軽いものの上に置く <- Greedyの考え方
- 自分より重い箱のなかで、↑以外の者の上に置く
- 新規塔を作る
もしも二番目の起き方や、三番目の起き方を行ったとして、
その後適切に箱を配置したとして、塔の数が実現可能な最小値になったとする。
しかしその塔の数は、Greedyの起き方によっても実現が可能であることがわかる。
よって、Greedyに箱を配置していっても良い。
コード
int n_case; cin >> n_case; vector<int> vec; int tmp; cin >> tmp; vec.push_back( tmp ); for( int i = 1 ; i < n_case; i++ ){ cin >> tmp; bool ok = false; for( int j = 0 ; j <(int) vec.size(); j++ ){ if( vec[j] >= tmp ){ vec[j] = tmp; ok = true; break; } } if( !ok ) vec.push_back( tmp ); sort( vec.begin(), vec.end() ); } cout << vec.size()<<endl; return 0;
problem D アルファベット探し
問題
盤面の上に、AとBとCがたくさん描かれている
AとBとCの数を答えよ。
ただし、A・B・Cは与えられた基本構造の整数倍サイズのものしか起こりえず、
盤面上でそれぞれの文字は、空白箇所も含めて領域を共有しないとする。
また、A,B,C以外の文字は描かれていない。
考えたこと
一箇所黒い部分を見つけたら、縦横斜めに人マス移動して黒い所は同じ文字を構成するパーツである。
このことを利用して幅優先探索で一つの文字領域の抽出する。
後は穴の数を数えて文字を判定すれば良い
コード
vector<string> field; int getfieldnum( int x1, int x2, int y1, int y2 ){ int width = x2-x1+1; int height = y2-y1+1; //cout << width << ", " << height << endl; bool checked[width][height]; memset( checked, false, sizeof( checked ) ); int ans = 0; int dx[] = {1,0,0,-1}; int dy[] = {0,1,-1,0}; for( int i = 0 ; i < width ; i++ ){ for( int j = 0 ; j< height; j++ ){ if( field[x1+i][y1+j] == '.' & !checked[i][j] ){ //cout << i << " ," << j << endl; ans++; queue< pair<int,int> > q; q.push( make_pair(i,j) ); while( !q.empty() ){ pair<int,int> p = q.front(); q.pop(); int x = p.first; int y = p.second; if( checked[x][y] ) continue; checked[x][y] = true; for( int i = 0 ; i < 4 ; i++ ){ int cur_dx = dx[i]; int cur_dy = dy[i]; int cur_x = cur_dx+x; int cur_y = cur_dy+y; if( cur_x >= 0 && cur_x < width && cur_y >= 0 && cur_y < height ) if( !checked[cur_x][cur_y] && field[x1+cur_x][y1+cur_y]== '.' ){ q.push( make_pair( cur_x, cur_y ) ); } } } } } } return ans; } int main(){ int w,h; cin >> h >> w; for( int i = 0 ; i < h ; i++ ){ string tmp; cin >> tmp; field.push_back( tmp ); } bool checked[h][w]; int dx[] ={1,1,1,0,0,-1,-1,-1}; int dy[] ={0,1,-1,1,-1,0,1,-1}; int ans[3]; memset( ans, 0, sizeof(ans ) ); memset( checked, false ,sizeof(checked) ); for( int i = 0 ; i < h ; i++ ){ for( int j = 0 ; j < w ; j++ ){ if( field[i][j] == 'o' && checked[i][j]==false){ queue< pair<int,int> > q; int h_max=i; int h_min=i; int w_max=j; int w_min=j; q.push( make_pair( i,j ) ); while( !q.empty() ){ pair<int,int> p = q.front(); q.pop(); int x = p.first; int y = p.second; //cout << x << ", " << y << endl; h_max=max(h_max,x); h_min=min(h_min,x); w_max=max(w_max,y); w_min=min(w_min,y); if( checked[x][y] ) continue; checked[x][y] = true; for( int dir = 0 ; dir < 8 ; dir++ ){ int cur_dx = dx[dir]; int cur_dy = dy[dir]; int cur_x = x+cur_dx; int cur_y = y+cur_dy; if( cur_x >= 0 && cur_x < h && cur_y >= 0 && cur_y < w ) if( field[cur_x][cur_y]=='o' && !checked[cur_x][cur_y] ){ q.push(make_pair(cur_x,cur_y)); } } } //cout << h_min << "-" << h_max <<", "<< w_min << "-" << w_max << endl; int n_field = getfieldnum( h_min-1,h_max+1,w_min-1,w_max+1 ); //cout << n_field << endl; if( n_field == 1 ){ ans[2]++; } else if( n_field == 2 ){ ans[0]++; } else{ ans[1]++; } } } } cout << ans[0] << " " << ans[1] << " " << ans[2]<<endl; return 0; }
後日談
わざわざ穴の数数えなくても黒い枡の数数えるだけで判定できるようだ。効率悪かったなあ。
