AtCoder Beginner Contest 099 - AtCoder
unratedですが参加しました。
36分台全完で96位。C, Dにペナルティ込みで30分以上費やしていることを考えると「ARCじゃなくてよかった…」と思いますが、けっこう問題が難しめだったので相対的には健闘したほうかも?
1問ずつ振り返っていきます。
A - ABD
100回目記念で出そうな問題。 が999以下か1000以上かで場合分けすればOKです。
ACコード:Submission #2643670 - AtCoder Beginner Contest 099
B - Stone Monument
「隣り合った塔の高さの差」は等差数列になっていて、1ずつ増えていきます。
そのため、隣り合った塔の高さの差を見るだけで、それらが何番目の塔で、高さがいくつなのか特定することができます。
具体的には隣り合った塔の高さの差 を
とおくと、
- 低い方の塔の高さを
とすると、
- 高い方の塔の高さを
とすると、
です。そのため、 で答えが求まります。
の求め方は
を使うとよいです。
ACコード:Submission #2644569 - AtCoder Beginner Contest 099
C - Strange Bank
想定解法が分からなくてC問題なのにDPしました。 えー…
を
円引き出すのに必要な操作回数とすると、
という遷移ができます。 の中身は、「1手前」としてあり得る数を全て列挙しています(終端は書き表しにくいので省略していますが、もちろん非負の値だけです)。
これを1から まで計算すれば
が答えです。
計算量的に若干の不安がありますが、DPの遷移元である の中身の個数は、大雑把に言えば「
は6や9のおよそ何乗か」なので
で抑えられます。そのため全体の計算量は
であり、
なので間に合います。
ACコード:Submission #2646945 - AtCoder Beginner Contest 099
D - Good Grid
問題がややこしいですが、ほぼ全探索に近いやり方で解けます。愚直すぎる全探索だと になるので流石に通りませんが…
「良いグリッド」は、盤面が で3色に色分けされた状態です。余りが異なるマスの色が被ってはいけません(言い換えると、1色や2色になってはいけません)。
「色が被ってはいけない」という制約を除けば、3色それぞれを独立に考えることができます。 具体的には、余り および色
それぞれについて
「 のマスの色を全て
に変えると、コスト(問題文中では「違和感」)の合計はいくつになるか?」
を、独立に計算することができます。各計算において のマスを全て見るので、この計算量は
です。(余りの個数である3も考慮すべきですが、今回は定数なので省略)
これを前計算した後に、余りが 0, 1, 2 それぞれについてどの色を使うかを全通り試し、コストの最小値を出します。このとき、色が被っている組み合わせはちゃんと除外しましょう。この計算量は です。
最大サイズの で単純に計算してみると、
、
なので十分間に合う…と思いきやRubyで1500msでした。怖いよー。
ACコード:Submission #2648372 - AtCoder Beginner Contest 099
さいごに
4問振り返ってみました。今回は難しかったんじゃないでしょうか…。