ARMERIA

放置していたけど更新再開、Rubyと競技プログラミングの話が中心になっていく予定です

ABC099 参加記録

AtCoder Beginner Contest 099 - AtCoder

unratedですが参加しました。

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

f:id:betrue12:20180610232725p:plain

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

A - ABD

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

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問振り返ってみました。今回は難しかったんじゃないでしょうか…。