ARMERIA

Rubyと競技プログラミングの話　AtCoderやCodeforcesの問題解説記事が多め。

ABC099 参加記録

プログラミング競技プログラミング AtCoder

AtCoder Beginner Contest 099 - AtCoder

unratedですが参加しました。

36分台全完で96位。C, Dにペナルティ込みで30分以上費やしていることを考えると「ARCじゃなくてよかった…」と思いますが、けっこう問題が難しめだったので相対的には健闘したほうかも？

f:id:betrue12:20180610232725p:plain

1問ずつ振り返っていきます。

A - ABD

100回目記念で出そうな問題。 $N$ が999以下か1000以上かで場合分けすればOKです。

ACコード：Submission #2643670 - AtCoder Beginner Contest 099

B - Stone Monument

B - Stone Monument

「隣り合った塔の高さの差」は等差数列になっていて、1ずつ増えていきます。

そのため、隣り合った塔の高さの差を見るだけで、それらが何番目の塔で、高さがいくつなのか特定することができます。

具体的には隣り合った塔の高さの差 $b-a$ を $d$ とおくと、

低い方の塔の高さを $h_{1}$ とすると、 $h_{1} = 1+2+...+(d-1)$
高い方の塔の高さを $h_{2}$ とすると、 $h_{2} = 1+2+...+(d-1)+d$

です。そのため、 $h_{2} - b$ で答えが求まります。

$h_{2}$ の求め方は $1+2+...+X = X(X+1)/2$ を使うとよいです。

ACコード：Submission #2644569 - AtCoder Beginner Contest 099

C - Strange Bank

C - Strange Bank

想定解法が分からなくてC問題なのにDPしました。 えー…

$dp(i)$ を $i$ 円引き出すのに必要な操作回数とすると、

$dp(0) = 0$
$dp(i) = 1 + \min(dp(i-1), dp(i-6), dp(i-6^{2}), ..., dp(i-9), dp(i-9^{2}), ...)$

という遷移ができます。 $\min(...)$ の中身は、「1手前」としてあり得る数を全て列挙しています（終端は書き表しにくいので省略していますが、もちろん非負の値だけです）。

これを1から $N$ まで計算すれば $dp(N)$ が答えです。

計算量的に若干の不安がありますが、DPの遷移元である $\min(...)$ の中身の個数は、大雑把に言えば「 $i$ は6や9のおよそ何乗か」なので $O(\log N)$ で抑えられます。そのため全体の計算量は $O(N \log N)$ であり、 $N \le 100000$ なので間に合います。

ACコード：Submission #2646945 - AtCoder Beginner Contest 099

D - Good Grid

問題がややこしいですが、ほぼ全探索に近いやり方で解けます。愚直すぎる全探索だと $O(C^{3} N^{2})$ になるので流石に通りませんが…

「良いグリッド」は、盤面が $(i+j) \mod 3$ で3色に色分けされた状態です。余りが異なるマスの色が被ってはいけません（言い換えると、1色や2色になってはいけません）。

「色が被ってはいけない」という制約を除けば、3色それぞれを独立に考えることができます。 具体的には、余り $k = 0, 1, 2$ および色 $c$ それぞれについて

「 $(i+j) \equiv k \mod 3$ のマスの色を全て $c$ に変えると、コスト（問題文中では「違和感」）の合計はいくつになるか？」

を、独立に計算することができます。各計算において $N \times N$ のマスを全て見るので、この計算量は $O(C N^{2})$ です。（余りの個数である3も考慮すべきですが、今回は定数なので省略）

これを前計算した後に、余りが 0, 1, 2 それぞれについてどの色を使うかを全通り試し、コストの最小値を出します。このとき、色が被っている組み合わせはちゃんと除外しましょう。この計算量は $O(C^{3})$ です。

最大サイズの $N=500, C=30$ で単純に計算してみると、 $C N^{2} = 7.5 \times 10^{6}$ 、 $C^{3} = 2.7 \times 10^{4}$ なので十分間に合う…と思いきやRubyで1500msでした。怖いよー。

ACコード：Submission #2648372 - AtCoder Beginner Contest 099

さいごに

4問振り返ってみました。今回は難しかったんじゃないでしょうか…。