ABC204の感想
AtCoder Beginner Contest204に参加しましたのでその感想を書いていきます。問題はこちらから。
結果はこんな感じでした。
4完（51:26+1WA）
順位 1946 / 8899
パフォーマンス 1135
ちょっとだけレートが下がってしまいました。今回反省すべきはD問題でそれっぽい解法を提出したことです。もちろんWAを貰いました。15分ぐらい悩んでも正しい解法が浮かばなかったので、焦って提出してしまいました。あわよくば通ってくれないかな、と思ってましたがそんなに甘くないですね。手痛い5分でした。皆様はマネしないようにしましょう。
A問題
じゃんけんをします。３人の手はあいこになるみたいですので、それを判断します。
まず、x=yならzさんも同じ手ですので、xを出力します。
x!=yのときにはx,yとは違う手を出力します。幸いなことに、ぐちょきぱーには0,1,2と数字が割り当てられています。合計は3になるはずなので、3からxとyを引くことでｚの手が求まります。
順調ですね。次行きます。
B問題
10個以上ナッツがある木から収穫します。
これは単純ですね。
if(a > 10) ans += a-10;
で答えが出ます。オーバーフローなど難しいこともありません。
順調、順調！次行きます。
C問題
経路探索です。
C問題で経路探索が出るのは久しぶり、もしくは初めてかもしれません。ぼくはABC174から参加していますが、少なくともそれ以降ではないんじゃないかな。
と少し面くらいましたがやることはシンプルです。BFSをしましょう。さすがに、ABCに30回も出場していればBFSぐらいは何も考えずとも書けるようになっています。成長したなあ。
これをスタート地点をずらしながら探索していけばＡＣです。Ｎ回BFSをするので、計算量と初期化に若干の不安がありましたが、BFSはO(N+M)としっかり理解してますので、自信をもって送り出しました。
いい感じです。
D問題
2つのオーブンで料理します。
この問題を見たときにまず、ABC172のTsundokuが浮かんできました。ということで、Tsundokuの問題文を読んでました。でもよくよく考えると、結構違いました。ちょっとだけ時間を無駄にしました。
そのまま、15分ほど考えましたが、いまいち解法がぴんと来ず、、、結局2分探索でXを決め打って、そのXで実現可能かを判定しました。この判定が曲者で、わたしはよくわからないまま、時間の長いものから順に詰めていくという方式でやりました。
これで、サンプルは通るんですね。ということでこれを提出してWA。残念です。
ということで調べました。
数列 部分和
そしたらdpでできるよという記事が見つかりました。ということでdpを実装しまして無事ACです。反省の多い問題でした。でも面白い問題でもありました。
E問題
この問題はおそらく次の問題と似たような感じで解けるはずです。
本問題は待ち時間と短縮時間がちょうどいい感じになる場所を見つけるのがポイントなはず。ということで、Dを i と i+1で割ったときにその差が1となる箇所を求めようと、必死に計算をしていました。1~10まで試して、100を試して1000を試して、いっぱい計算しました。
その結果どうやら√D付近で出発するのが良さそうということに気が付きました。これに気づいた時点で残り10分でした。
残念ながら実装は間に合わず、時間切れです。
F問題
見てないです。
あとがき
D問題に時間を使ってしまいましたね。もう10分速く解けていれば、、と考えてしまいます。がこれも実力ですね。
でも、青diffのE問題が解けなくて、悔しいと感じるのはなかなかに感慨深いものがありますね。競プロ始めたばかりの時はD問題がいつか解けたら気持ちいいんだろうなーとか考えていましたので、少しずつですが成長できているのではないでしょうか。上を見ると青天井ですが、一歩一歩楽しんで邁進しております。
いつか5完ができる日がくるまで、地道に精進を続けます（実は1度だけ5完をしています。ただ5か月も前のことですし、あの時は大きく上振れただけなので、ノーカンということにしておきましょう）。
この記事が気に入ったらサポートをしてみませんか？