AtCoder Grand Contest 029

久しぶりのAGCでDまで時間をかけて考察したので残しておこうと思う。
本番は比較的速い時間にBを通すことができたので青パフォを得ることができた。
欲を言えばDは通せたなーと思ったが、まぁいいでしょう。

A - Irreversible operation

WとBを何回入れ替えることができるかという問題。
できるだけWを左に寄せればいいんだなーというのはすぐ気づき、ゆったりと実装してAC。
みんなの解くスピードが速すぎて順位表みてびびった。A問題のWA恐怖症なので結構念入りに確認してたのもあるかもしれない。

B - Powers of two

和が2のべき乗となるようにペアを組んだ時のペアの最大数を求める問題。
とりあえずN = 200000だからdpとかは無理そうだからソートしようってなってソートする。下から見ていったが貪欲に決めていったら決まらないことに気づく。例えば {1, 3, 15, 17}と{1, 3, 5, 15}の組み合わせだと{1,3}で組んでいい時とダメな時がある。

しばらく考えて上から貪欲に見ていくとうまくいくことに気づく。上の2つの例でもうまくいく。

それでは大きい数から見ていって、ペア候補となる数はどのようなものがあるかを考えてみる。注目する数をKとすると、ペアとなるべき数Xは

この条件を考えると、の表す値はKより大きな最小の2のべき乗のみを考えればよいことがわかる。
たとえば、であったら、のみを考えればよく、を考える必要はない。なぜなら後者を考えるとXは必ずKより大きな数になってしまうからである。
したがって、大きい順に見ていき、まだ使われていないペア候補が見つかればそれを使ってペア数をインクリメントすればよい。まだ使っていない数を見つけるために二部探索などを使っている人もいたが、mapを用いて使える残りの回数を持っておけばいいと思う。
atcoder.jp

C - Lexicographic constraints

いくつの文字数を使えば辞書順に並ぶような文字列を構成できるかという問題。コンテスト終了後に解いたが、かなり実装に手こずってしまった。

当然使える文字数が多いほど構築できる可能性は高くなるので、最小何文字を使えば可能かという二部探索の問題と捉えることができる。ここは経験があれば割と気づきやすい部分だと思うが、難しいのはこの判定を実装する部分である。　　
文字列長を左から順にみていく。もし前の文字列より後の文字列の方が大きければ末尾に'a'をその差分だけ足すのが最小とわかる。この場合は問題ない。
逆に前の文字列長が後の文字列長以上である場合には整数の繰り上がりのように最小の位のアルファベットを移動させていくことになる。この最小の位の位置は小さい方の値によって決定する。したがって文字列が'aaaa'の状態で文字列長が4から2へと遷移すれば上から２文字目のaがインクリメントされ結果として生じる文字列は'ab'となる。
この実装が思ったより難しく、文字列を圧縮したりstack使ったりする方法が色々紹介されていたが僕はmapのみを使うことにした。
具体的には、文字a,b,c...を0,1,2...とし、i桁目の文字をmp[i]というキーバリューの形で保持する。
K種類の文字列を使うとき、値を更新する桁を下から見ていき、値がK-1を超えたら次の桁へ繰り上がるということを繰り返す。
そうして繰り上がりがK文字以内でできなくなればそのKでは不可能と判定できる。
ここの判定はAtCoder公式の解説動画がわかりやすいと思う。

コードはこちら。
atcoder.jp
このコードでひたすらバグに悩んだのは45行目で特定の桁から下の数値をリセットする部分。これをしていなかったので桁の繰り上がりが正しく行われていなかったようだ。数ケースだけ落ちると原因がホントわかりづらい...

D - Grid game

800点問題。なのだがさすがに800点にしては簡単だと思う。800点問題初AC。
先攻はできるだけ下に行き続け、後攻はたどり着くのが可能な範囲で最も近い行き止まりをめがけて進むのが最適だとわかるので、まずはたどり着くことのできるマスの範囲を絞る。
高橋くんが先攻で下に移動した後、後攻の青木くんが右に進むことができるかできないかで経路が変わります。青木くんは必ずしも右に行かなくてもいいのだが、まずは行ける限り右に行くとして経路を決定する。
すると以下のようになる。

青木くんが最も右に移動した場合に図のような経路になるので、青線で囲った部分および経路上に関しては青木くんが自分の意志で移動できることになる(高橋くんは進む以外に選択肢がないため)。
したがって、この範囲の中から最も早くぶつかる(=最もX座標が小さい)点に行くのが青木くんにとって最善になる。
XとYが直感と逆なのでそこだけ気をつけよう。
atcoder.jp