ARC122の感想

東京海上日動 プログラミングコンテスト2021（AtCoder Regular Contest 122)に参加しましたので感想を書いてきます。問題はこちらから。

Tasks - Tokio Marine & Nichido Fire Insurance Programming Contest 2021（AtCoder Regular Contest 122)

結果はこんな感じでした。

0完

一問も解けませんでした。現状のAtCoderのコンテストでは一回も提出を行わないと、0点ではなく不参加という扱いとなるため、私も例にもれず不参加になりました。解けた問題はありませんが、自分への戒めを兼ねて考察過程を書いていこうかなと思います。

A問題

プラスとマイナスをいい感じにくっつけてその総和を求めます。

皆目見当もつかなかったので、色々な例を試していました。そうして次のようなことに気が付きました。

・先頭の数字も+と-がつけられた場合、不適切な式も全部含めた値の合計は0となる。
・ここから、先頭のーがなくなるため、式の合計は先頭の値*2^(N-1)となる。
・この値から不適切な式の値を引くことで答えが求められる。

ということで、上記に沿って考察を進めていきます。といいましても、不適切な式ってどのように求めるんでしょうかね。これが全然わからなくて、1時間ぐらいお絵描きをしていました。

結局は次のような感じがルールがありそうだなとなりました。

これを実装してみて、入力例１はOK、２もOK、３はぜんぜん合いません。なぜ、、

３だけ合わないので、modintライブラリが壊れたのかなと心配になって、その辺のデバッグから始めました。でも、特にライブライをいじってないのでそんなこともなく、、

次にキャストを疑いました、入力はintでとっているので、modint型にする前に掛け算をしちゃうとオーバーフローします。ですので、intをlong longにしたり、掛け算の前に明示的に(modint)でキャストしましたが、これでもだめ、、

この辺で残り25分ぐらいでした。どんなに遅くなっても、解けたら提出しようと決めていたので、あきらめずに頑張ります。

ここで、ランダムケースを書き始めました。今思えばだいぶ遅いですね。

回してみると驚きました、ほとんどのケースで答えが合いません。逆に入力例１と２はよく合ったなと感心するぐらいでした。なんか根本から違うか、どこかで嘘をついている、という結論が自分の中で出たところで時間切れです。悔しい。

あとがき

今回はいわゆるNo Subというやつでしたので、レート自体は下がりません。ただ、余りにも悔しいですね。最近、ABCでも安定して400点問題や水色diffを取れていたので、ショックが大きいです。

コンテスト後に解法を確認して、1時間ぐらいかけてACしました。想定解はDPなのですが、おそらくコンテスト中にDPと気づけても解けていたかは怪しい気がします。詳細を詰めるのに時間がかかりました。

今回は残念な結果でした。が、くよくよしててもしょうがないので次頑張ります。明日は初心者コンテストのABCがありますので、気持ちを切り替えて参加していきたいと思います。