AGC025 参加記録

AtCoder Grand Contest 025 - AtCoder

90分台3完で201位。パフォーマンスは自己最高の2282を叩き出しました。AGC、ハマるとすごい。

f:id:betrue12:20180604201801p:plain

A～Cについて振り返ってみます。Dも本番中に考えていましたが、根本的に解法が違っていたようなので…いずれ、ちゃんと勉強して通します。

A - Digits Sum

公式解説の解法が天才ですが、 $N \le 10^{5}$ なので愚直で通ります。200点を信じろ。

ただ私のコードがあまりに愚直すぎて、 $N = 10^{5}$ の手元実行で1.5秒くらいかかってたので、ビビって対称性を利用して範囲を半分にしました。色々と真似してはいけないコードになりましたが、通ったのでよし。

本番コード（真似してはいけない）：Submission #2606932 - AtCoder Grand Contest 025
もうすこしマシな愚直コード：Submission #2617672 - AtCoder Grand Contest 025
公式解説の方法を使ったコード：Submission #2617683 - AtCoder Grand Contest 025

B - RGB Coloring

各色のブロックの点数が

赤色： $A$
緑色： $A+B$
青色： $B$
無色： $0$

であり、 $N$ 個のブロックの合計点数を $K$ にする。ということは、 $a, b$ を $0$ 以上 $N$ 以下の整数として $aA+bB=K$ が成り立っている必要があります。この時点で、この式を満たす $(a, b)$ の組それぞれについて数え上げを行い全部足す、という発想が浮かびます。

このような $(a, b)$ の組は、 $A, B$ が十分大きくて互いに素だったりすると数が減るのですが、残念ながら制約上は $A=B=1$ みたいなこともあり得るので、最大 $N+1$ 個あると思っておいたほうが良いでしょう。

では $(a, b)$ を固定した時に、赤、青、緑の内訳としてはどのようなものが考えられるでしょうか。緑の個数を $g$ とすると、赤の個数は $a-g$ 、青の個数は $b-g$ となります。なのであり得る緑の個数全てについて計算すれば、あとはひたすらcombinationを計算して答えにたどり着きますが…

TLEコード：Submission #2608378 - AtCoder Grand Contest 025

まあ、当然間に合いません。ダメ元で投げたらやっぱりダメでした（よくない）

$(a, b)$ の組を全部試すのがよくないのか、緑の個数を全部試すのがよくないのか。「緑の個数を全部試さなくていい方法はないかなあ」と考えていると、 赤と青を独立に塗って、たまたま重なったものは緑とみなす という発想が浮かびました。…何で浮かんだのかは自分でも分かりません。

というわけで無事に、 $(a, b)$ の組を全部試す1重ループで解けました。コンテスト本番特有の無駄な保険コードとかが入ってますが気にしないでください。

本番コード：Submission #2609206 - AtCoder Grand Contest 025

ちなみに…上記コードの上半分は、素数modでの組み合わせ（二項係数）を計算するライブラリです。使う問題はけっこう多いので用意しておいたほうが良いと思います。せっかく考察が合っているのにここが原因でACできないのは、やっぱりもったいないですよね（過去に1敗）

素数modの二項係数は、解説やコード例も含めて蟻本などに載っていますが…Rubyだと蟻本の方法では逆元計算だけでTLEしてしまうので、以下のブログで紹介されている方法を用いています。

Tech Tips: 素数を法とする世界の逆元をまとめて計算

私も他の人の提出コードをきっかけに知ったので、何か名前が付いているアルゴリズムなのかどうかも分かっていませんが…遅い言語を使っている人は是非活用してください。

C - Interval Game

高橋くんがぴょんぴょんする問題。

青木くんは高橋くんを沢山動かしたい。高橋くんはなるべく動きたくない。どういう動きになるのか厳密に考察するのは難しいですが、何となく青木くんの戦略としては、高橋くんを左右交互に動かしまくる のがいいんじゃないかと思います。

具体的なイメージを掴むため、サンプルを図示してみましょう。入力例3が一番イメージしやすいです。

f:id:betrue12:20180604214811j:plain

動作のイメージは以下のような感じです。あえてアルゴリズムっぽく言えば貪欲法です。

高橋くんをできるだけ大きく右に動かすため、青木くんは「一番右側にある区間」を選ぶ。高橋くんはなるべく動きたくないので、その区間の左端に移動する。
今度は高橋くんを左に動かすため、青木くんは「一番左側にある区間」を選ぶ。高橋くんはその区間の右端に移動する。
これを、「高橋くんが動かなくてもよくなる」まで繰り返す。

この記述で曖昧なところを、より厳密に考えてみます。

まずは「一番右側にある区間」。区間が重なっていたりすると一意に決めづらいですが、高橋くんが動くのは選んだ区間の左端なので、これは「まだ使っていない区間のうち、左端が一番右側にあるもの」を選ぶべきです。「左側」についても同様です。

次に「高橋くんが動かなくてもよくなる」とはどういうことか。単純に「一番右側にある区間の左端」→「一番左側にある区間の右端」と動いていくと、いずれこれはクロスする可能性があります。

f:id:betrue12:20180604225825j:plain

上図のように、クロスした後も「右端」「左端」と動き続けるのは、高橋くんにとって無駄です。

クロスしたということは、左端は現在地より左側に、右端は現在地より右側にあるので、高橋くんの現在地は区間に入っているはずです。そのため高橋くんはその位置からじっと動かず、最後に原点に戻りさえすればいいですね。

これで動きがシミュレーションできますが…最後に大事な点がひとつ。それは高橋くんを 最初に一番右側の区間に動かすべきか、一番左側の区間に動かすべきか はケースバイケースだという点です。どっちでも変わらないという場合もありますが、例えばサンプル2では結果が変わってきます。泥臭いですが、どっちも試して大きい方を取るのが堅実だと思います。

本番中に通したコードは以下です。上記の「最初どっちに動かすか」の2通りをコピペで処理しているのでコードが長くなっています…

本番コード：Submission #2610818 - AtCoder Grand Contest 025

もっと本質的な考察をして無駄を省いたり複数のケースを同一視できるようになると、地道なシミュレーションよりも簡潔な論理で解くことができて、その極致が以下のようなコードなんだと思います。これはすごい。

touristのコード：Submission #2609185 - AtCoder Grand Contest 025