ABC200の感想
京セラプログラミングコンテスト2021（AtCoder Beginner Contest 200）に参加しましたので、その感想を書いてきます。問題はこちらから。
結果はこんな感じでした。
4完（ABCD 61:41 +0WA）
順位：981 / 8577
パフォーマンス：1521
記念すべき200回目のABCコンテストでした。ですので、200にちなんだ問題がたくさん出題されました。なんかもうそれだけで楽しかったですね。
今回は久しぶりに４完できました。まずは一安心です。最近は３問しか解けないコンテストが続いていました。3問目までは「４か月前でも解けたよ」みたいな問題が多いので、やっと難しい感じの問題にて練習の成果がでました。うれしいですね。
あと、最近ipadのペンを買ったのでタブレットを試してみました。まだ慣れないですが、そのメモも載っけておきます。
A問題
西暦を世紀に変換する問題です。これ日常生活をしていてもたまにわからなくなります。2021年は21世紀で、1999年は20世紀で、2000年も20世紀ですよね。だいたい100で割ると近い値になりますが、そこの境界条件に少し悩みました。
結局、100で割った値を切り上げた値を出力すればACです。境界のテストケースをいくつか試して提出したのでWAを出すことなく解けました。
B問題
200で割るか、後ろに200を付けるかの問題です。
まず、200の倍数に1000があるので200の倍数の判定は下3桁が200の倍数になっているかでOKですね。ということは、200を追加した数は必ず200の倍数になります。地味にこれが重要な気がしてます。
追加した後は必ず割れますので、オーバーフローの心配はありません。intだと厳しいかもしれませんが、
あと、200を追加するのは*1000+200でOKですね。これをやるだけです。
C問題
200で割った余りが0になる組み合わせの数を求めます。
とりあえず、全部の数の剰余を求めてみました。modの世界では足し算、引き算、掛け算は好きなようにできるので、余りが同じ組でその組み合わせを求めてあげればいいな、考えました。ここまで、3分ぐらいです。
ですので、各剰余の数を数えてあげて、
剰余の数 C 2
を足し合わせてACです。
ABC併せて10分ぐらいで解けました。とっても速く解けたと思ったのに、この時点で1500位ぐらいでした、皆さん速すぎませんか？
D問題
200で割った剰余が等しくなるように数列から数字を取り出します。
まず、Nが小さいことに注目しました。最大でも200個の数字しかないのでここを上手いこと使うと考えました。また、余りの数も200種類しかないので、その状態を管理すればdp[200][200]で作成可能な余りを調べることができると考えました。
異なる個数で等しい余りが作成できれば、構築可能と判定ができます。次にそれを実際に構築します。判定時にどの余りで構築できるかを調べているので、それを上手い感じで復元できないかな、と考えましたが、上手くいかず。もっと言えば、このdpの実装が良くないため、余りが0となるときにうまく判定ができませんでした。
困りました。
ここで、余りが200種類しかない点をもう一回考えました。数字を一つずつ「使う」「使わない」とすると、2^200かかってしまいますが、余りが重複した時点で探索はおしまいです。このときの余りは鳩ノ巣原理で多くても201回探索すれば1回はかぶります。
ですので、全探索する勢いでdfsを書いて、あとは良しなにやってくれると信じて提出しました。
これで無事ACです。やることはシンプルなのに、どうしてそれでいいのかを考えさせられる素敵な問題でした。気づいたときに、ハッ、となりました。気持ちいいですね。
E問題
ケーキを並べて、K番目の値を求める問題です。
いまいちやり方が浮かばず、いろいろお絵描きしてました。nが小さいときの各数の個数を調べてみて、なにか法則が見つからないかと、試していました。とりあえず、前後は対象になることとなんかそれっぽい感じの法則がありそうだなーというところで時間切れでした。これは解けませんでしたね。
F問題
見てないです。
あとがき
200回にちなんだ素敵な問題でした。前回のZONeのコンテストに引き続き遊び心のある楽しいコンテストでした。
贅沢を言うのであれば、Ｄの考察でだいぶ遠回りをしてしまったので、剰余が200種類の時点で鳩ノ巣から全探索を見つけたかったですね。
今回も解答記事を書いてきたいと思います。ただ、あんなに逞しかったゴールデンウィークもあと1日となってしまった本日ですので、可能な限り明日中に書きたいなと思っています。頑張ります。終わらなかった分はのんびり書きます。
この記事が気に入ったらサポートをしてみませんか？