ABC103 参加記録

今回はABCオンリーでしたー。

結果は14分台全完で14位。けっこう速いかなと思いましたが、それでも1桁順位は取れないのですね…。

f:id:betrue12:20180721221654p:plain

A - Task Scheduling Problem

100点問題にしては難しいような気もしていますが…（というか問題文の読解が少し難しい）

タスク3つにそれぞれ値があり、「1つ前に解いたタスクの値との差の絶対値」だけコストがかかります。小さい方から順番にやっていくのがムダがないです。大きい方からでも良いです。

ACコード：Submission #2876070 - AtCoder Beginner Contest 103

当日は開始後しばらく、出力末尾に改行コードがあるとWAになる？という状態だったようで…ratedな人の焦りは尋常じゃなかったと思います…。*1

B - String Rotation

文字数が最大100しかないので、最大100通りの回転を全部試せばOKです。

ACコード：Submission #2877161 - AtCoder Beginner Contest 103

余談ですが、Rubyの配列には rotate というそのものズバリなメソッドがあります。文字列には使えないので、配列に分解する必要はありますが。

C - Modulo Summation

答えを知ってれば一瞬だけど、考え方が難しい問題。

$m$ の選び方は非負整数なら何でもOKです。逆に言えば選択肢が多すぎるので、何らかの条件で探索範囲を絞ったり、数学的に一発で求める必要があります。

$m \mod a_{i}$ の値は $0, 1, ..., (a_{i} - 1)$ なので、全ての $i$ について値を $(a_{i} - 1)$ にできれば理想です。そして、そのような $m$ は実は存在します。それは、 $m = (a_{1} \times a_{2} \times ... \times a_{N}) - 1$ です。

知識または閃きがあると速い問題ではありますが、上記のように「それぞれの値の範囲はいくつで、それらを同時に大きくすることはできるだろうか？」と考えてみたり、サンプルや自作ケースで実験してみると手がかりが掴めると思います。

ACコード：Submission #2878101 - AtCoder Beginner Contest 103

余談中の余談ですが、「素数が無限にあることの証明」の1つに、「素数が有限と仮定して、"全素数の積+1"という数を考えると、それは全ての有限な素数で割って1余る数なので、これも素数である。よって矛盾」というものがあります。私はそこから連想して解きました。

D - Islands War

争っている島の間に橋が1つもなければアウトです。この問題は、島たちを端から見ていくと分かりやすいです。東西よりも左右のほうが分かりやすいので、西を左として以下「左から」と書きます。

f:id:betrue12:20180721224017p:plain

左から見ていって、既に切れていないペアの右端にぶつかったときは、そのすぐ左の橋を切ります。既に切れている場合は無視します。

感覚としては、切る本数を減らしたいので、なるべく切るのを先送りにする、という気持ちです。

実装はペアを右端の値でソートして、ペアを1つ1つ順に見ていくといいでしょう。

ACコード：Submission #2879237 - AtCoder Beginner Contest 103

さいごに

ABCオンリー回はC, Dも比較的解きやすい問題が多いですが、ARCやAGC-Aでもこのくらいの問題が出たらサクっと解けるようになりたいので、unratedでも良い訓練になります。

脚注

*1:出力末尾の改行コードなんですが、最近のAtCoderでは問題文に明記されておらず、ABC/ARCなどの公式コンテストでは「あってもなくてもいい」というのが慣習的に知られてはいるようです。非公式コンテストでは付いていないとWAになることが割とあるので、私も癖で毎回付けるようにしています。できればルールとして明記したほうが良いのではないかと思っています…。