だらだら競プロ適当解説：AtCoder Beginner Contest 006
AtCoder Beginner Contestの第6回。
いつもどおりぼちぼちやっていく。
別にゆっくりやってもいいじゃない、コンテスト参加じゃなけりゃ競争じゃないんだし。
ていうか仮にコンテスト参加でも数こなさなきゃできるようになんないし、焦らずゆったりいこう。
総評
AもBも少し難しくなったかなという印象。
これまでB問題はifとforが使えればみたいな感じだったが、今回はデータの持ちかたみたいなものを考える必要がある。
前回同様、Cは思考問題でDは知識問題の節が強い。
とはいえD問題はアルゴリズムが得意な人が頑張って考えれば導き出せるかな～くらいの内容だと思う。
まあ、俺はすぐには導き出さなかったし、面倒で答え見たのだけど。
A - 世界のFizzBuzz
FizzBuzzのふりをして襲い掛かる偽物のFizzBuzz
略解
string s; int N; cin >> s; // 3が含まれるが面倒なので文字列処理か桁数処理をする. // 多分文字のほうが簡単. N = atoi(s.c_str()); //文字. if (s.find('3') != string::npos) { cout << "YES" << endl; return 0; } if (N % 3 == 0) { cout << "YES" << endl; return 0; } cout << "NO" << endl;
ポイント
３が含まれるときというのと３で割り切れるというのをどうやって処理するか考えること。
３で割れるというのは３で余りを出せば解けることはすぐに分かるが、３が含まれるはちょっと面倒である。
個人的には文字列で処理してしまうのが分かりやすくてよいかと思うが、下記のような方法で数字のまま一桁ずつ確認するなんていう方法もある。
// 数字だけで処理するなら下の感じ. while (N != 0) { if (N % 10 == 3) { cout << "YES" << endl; return 0; } N/=10; }
10で割った余りを出せば下一桁の値が分かることを利用して、”余りを確認→10で割って一桁ずらす”を繰り返すことで全桁を確認できる。
入力が数値だからと言って数値処理にこだわる必要はなく、時には文字列を利用するのもよい。
そしてよく問題を見たら、Nは一桁だから3が含まれるかどうかを考える必要はなかった。
B - トリボナッチ数列
こいつは偽物のフィボナッチなのか。今回は贋物が多いですね（失礼）
略解
// 10^6個覚えておくわけにもいかないので少しだけ記憶する. int tri[3];//前の情報を覚えておくやつ. // 初期値. tri[0] = 0; tri[1] = 0; tri[2] = 1; for (int i = 3; i < n; i++) { //足し算や掛け算なら途中で余りを出してもよい. tri[i % 3] = (tri[i % 3] + tri[(i + 1) % 3] + tri[(i + 2) % 3]) % 10007; } cout << tri[(n - 1) % 3] <<endl;
ポイント
問題に記載されている通りの数式を実装できればよい。
また、余りを出す系の問題は加算や乗算の途中に余りを出しても問題ないということを知っていればよい。
これを知らないで最後に余りを出そうとすると、桁あふれで誤った数値になってしまうので注意する。
この点は正直競プロ特有のアレなので、覚えておく以外のなんでもない。
そして、全部記憶しておくことは厳しいことを考慮する。（実は1000000くらい記憶できる気もするし、実際できるだろうけど……言語によるかも）
でっかい配列を用意できれば全部記憶できるので上記のように分かりにくい作りにする必要はないが、直前の3つだけ覚えておけばよいと思うと長さ3の配列を用意して余りを利用して添え字を回すという方法で十分実装できる。
この手のはおそらくC問題とかになると必要になるテクニックなのでどうせだから覚えておいて損はない。
業務的には音声や描画のバッファリングでよくお世話になる。
逐次データ処理という話ではネットワーク系でもこういったデータ処理の仕方をすることが多い。
C - スフィンクスのなぞなぞ
こいつはスフィンクスのふりをした数学マニアだな！
略解
int N, M; int num[3];//それぞれの人数. int sum;// 足の合計値. cin >> N >> M; // もちろん先に足切りしてもいい.N*2 < M < N*4 //人まずみんな大人. num[0] = N; num[1] = 0; num[2] = 0; sum = 2 * N; if (sum == M) { cout << num[0] << " " << num[1] << " " << num[2] << endl; return 0; } // 全員老人にしてみる. for (int i = 0; i < N; i++) { num[0]--; num[1]++; sum++;//大人が老人になるので実質１プラス. if (sum == M) { cout << num[0] << " " << num[1] << " " << num[2] << endl; return 0; } } // 全員子供にしてみる. for (int i = 0; i < N; i++) { num[1]--; num[2]++; sum++;//老人が赤ちゃんになるので実質１プラス. if (sum == M) { cout << num[0] << " " << num[1] << " " << num[2] << endl; return 0; } } // すべて赤ちゃんでだめならもう無理でしょう. cout << "-1 -1 -1" << endl;
ポイント
Nが100000で大人、老人、赤ちゃんの３種類なので、単純全探索は100000^2でちょっと厳しいということをまず察する。
全大人が最低値、全赤ちゃんが最高値であることに気づくこと。
そのうえで、大人から老人、老人から赤ちゃんはそれぞれ１増加なので、隙間なく上記の範囲を埋めることが可能なことに気づけばよい。
となると、まず全部が大人であると仮定して、一人ずつ老人に変えていく、そして次に老人を一人ずつ赤ちゃんに変えていき、Mになるかどうか確認すればよい。
これはたかだかO(N)で作業が完了する。
足が2本から急に5本とかになるとなかなかこうは解けないのだが、隙間なく埋まっていることに気が付けば実装自体はかなり単純な問題である。
と、これが想定解法だろってくらいの気持ちで解いていたのであるが、どうやら想定解法と全然違うらしいので、想定解法も確認してもらいたい。
私と同じ解法に至れば思考系の問題だが、想定解で解こうと思うと効率の良い全探索方法に関する知識問題になる。
想定解だとああ確かにC問題だなって感じだが、この解法だとC問題かな？って感じである。
下手に競プロ慣れしていないほうがすんなり解けたかもしれない。
生放送時に私はツルカメツルカメと言っていたくせして、一切ツルカメで解いていない。ツルカメの先入観のないほうが解きやすかっただろう。
D - トランプ挿入ソート
おいおいここにきて正統派かよ
略解
int N; int c[30000]; //ある長さx+1の時の最後尾の最小値. int mem[30000]; int main(){ cin >> N; for (int i = 0; i < N; i++) { cin >> c[i]; } for (int i = 0; i < 30000; i++) { mem[i] = INF;// 十分に大きい値. } // 処理の簡略化のために一つ目を入れておきましょう. mem[0] = c[0];// 長さ1はとりあえず初期のやつで. int maxlength = 1; for (int i = 1; i < N; i++) { // ここを必要ならあとで二部探にする. for (int j = maxlength - 1; j >= 0; j--) { // memより大きければつなげるはず. if (c[i] > mem[j]) { // 繋げるうえで繋いだ場合に最小になるなら更新. if (c[i] < mem[j + 1]) { mem[j + 1] = c[i]; if (maxlength < j + 2) { maxlength = j + 2; } } // つなげても繋げなくてもおしまい. // なぜなら繋げなかったとたら. //もっといいのがすでにつながっているってことだから. break; } // 0にたどり着いてしまったら仕方ないので0と比較. if (j == 0) { // 小さいので上書き. if (c[i] < mem[j]) { mem[j] = c[i]; } } } } // 最長の長さのもの以外がソートし直さないといけないもの. cout << N - maxlength << endl; return 0; }
ポイント
全探索はいつものように、計算量の問題で無理である。
ソートをするいう考えから、ソートされていないものを横にのけるという考えにもってこれるかというのが一つ目のポイントである。
要するに、外に避けたものは必ず適切な位置にあとで差し込まれると考えれば、トランプを除けきった残りがソートされていればよいという話である。
つまり、除ける数ができるだけ少なくして、ソートが完了した状態を作ればよい。
これは最長増加部分列を求める問題になる(らしい)
想定解をみて組んだ実装で、２分探索でないことを除けば想定解に順じている。
正直この計算量なら二分探索は必要ないと思ったし、実際に必要なかった。
とはいえ、２分探索は結構出てくるので、いずれどこかでメインになったときにしっかり紹介する。
長さxのソートされた列(増加列)の最後尾の数値を配列に記憶する。
そうすると、その数字より大きな数字が次に来た場合、その長さxに追加接続してx+1長の列が作成できる。
たとえば123と来た場合
mem[0] = 1 → mem[1] = 2 → mem[2] = 3 となる。
132と来た場合は、
mem[0] = 1 → mem[1] = 3 → mem[1] = 2 となる。
ここで2は3に接続できないので、mem[0]の1と接続し、かつより小さいのでmem[1]を上書きする。
最小値のみ保持すればいい理由は、大きい数字も接続できるものは小さい数字のものにも当然接続できるからである。
接続を繰り返していき、もっとも長くなった列を残し、全体から引くと、取り除かねばならない枚数=ソートに必要な回数が分かる。
だらだら配信
どんな感じの思考で解法に至ったのか知りたい稀有な人用。
https://www.youtube.com/watch?v=wcnxXzzIMu4
https://www.youtube.com/watch?v=0MZMhUjo_zk
https://www.youtube.com/watch?v=co1FxY9f6D0
