AtCoder Beginner Contest 118 感想

AtCoder Beginner Contest 118 に参加しました。

結果はAB2完、順位は1807/2881位でした。

A - B +/- A（AC+1WA）

B-A を A-B と勘違いしてWA。致命的。今回の反省点の1番目。

B - Foods Loved by Everyone（AC）

赤線で囲った部分の数字の意味が分からず、5分以上悩んでしまいました。結局この 2,3,2 が意味するものは、1番目の人が好きなものは2種類、2番目の人が好きなものは3種類、3番目の人が好きなものは2種類ありますよ、ということですね。全ての人に共通するもの（全ての人が発言しているもの）だけ抜き出すという典型問題だったはずなのですが、見慣れない入力形式だったために、時間を浪費してしまいました。今回の反省点の2番目です。

C - Monsters Battle Royale（WA）

A1~An の最大公約数が答えになるそうです。なんだそれ～わかるはずないじゃないの。何をどうやったらそんな発想が出てきてどうやったらそうなって答えになるの。自分の無能さに激昂しそうになりましたが、解説と、手元の計算用紙を比べ見てみると、どうやらあと一歩のところだったようです。

5 と 13 で殴りあう場合を考えてみます。

・5 → 13（5,8）
・5 → 8（5,3）
・5 ← 3（2,3）
・2 → 3（2,1）
・2 ← 1（1,1）

このような手順で、お互いの体力をギリギリまで削ることができます。ここまでは私も考えることができました、しかし気づくべきだったのです、この殴りあいの手順が「ユークリッドの互除法」の手順に酷似していることに。

この手順を A1~An に対して順に適応していくことで、最終的に n 番目のモンスターの体力が A1~An の最大公約数（答え）になるというわけです。ユークリッドの互除法に気づけなかったのは、ひとえに、僕が普段から数学に触れていないせいでしょう。そういったものに敏感な人なら、入力と出力を見ただけで、これは最大公約数だと気づけるのかもしれません。理不尽なひらめきを要求する問題かと思って一人でイライラとしていましたが、落ち度は全くもって僕のほうにあったわけですね、今回の反省点の3番目です。

D - Match Matching（WA）

D問題は今の自分にはまず解けないので、これまで手をつけずにきましたが、今回はC問題が解けそうになかったので、いちおう解いてみました。案の定、ACに至ることはできませんでした。解説を読むと DP をしなければならないらしく、解けないのも納得です。必要本数が最小の数字をまず並べられるだけ並べて、マッチ棒をちょうど使いきれていないなら、必要本数が最小の数字を減らしつつ、他の数字も導入していって、ぴったりになったところで数字の大きい順にソート……というやり方で多分解けると思うのですが、実装が面倒くさい上に他の問題に応用できる考え方でもありません、素直に DP を勉強すべきですね。

総括

今回は惨敗に終わりました。途中、自分のセンスの無さにイライラする場面もありましたが、終わってみると、センスどうこうではなく単純に勉強不足だということがわかりました。有意義なコンテストだったと思います。