ABC203の感想
AtCoder Beginner Contest 203（Sponsored by Panasonic）に参加しましたのでその感想を書いていきます。問題はこちらから。
結果はこんな感じでした。
ABCD（97:16+1WA）
順位：944 / 8432
パフォーマンス：1489
今回も4完でした。でもこの結果にはなかなかに満足しております。D問題がとても難しく途中で泣きそうになりましたが、ボロボロになりながらもACを獲得することができました。コンテスト後に調べてみるとこの問題は青diffらしいです。これは嬉しい。ぎりぎりでしたので3完の最速とほとんどパフォーマンスは変わりませんが、順位やパフォーマンス以上に納得できる結果となりました。
感想いきます。
A問題
またまたさいころの問題です。この間も見ましたね。
問題名を見ただけ何をするかなんとなくわかりました。そうです、ちんちろですね。大学生の一時期、何をするにもじゃんけんの代わりにちんちろで決着をつけていた私でありますので、ちんちろは得意です。
if文にてそれを実装して無事ACです。
B問題
部屋番号を足し合わせます。
ざっと問題を見た後に制約を見てわかりました。非常に制約が小さい（緩い）ので該当するものを全部試せば大丈夫だなとなりました。幸いなことに、全ての数字が1桁ですので、
i * 100 + j
で表せますね。これを全部足し合わせてACです。次行きます。
C問題
この問題はまず一行目を見てびっくりしました。なんと村が10^100+1個あるらしいです。これはシミュレーションは間に合わないかな、と思いました。が、結局はシミュレーションでした。
制約を見ると、aの値がとても大きいです。ですので、１歩進んでkを減らしていく、みたいなことはできません。
ということで、aの値でソートして現在地から次のaまでをO(1)で求めれば何とかなりそうだと気が付きました。
ということで、それを実装してACです。オーバーフローが怖くて全部long longでやりましたが、まあこのくらい用心するぐらいがちょうどいいでしょう。
D問題
これは難しかったですね。
まず、800*800ですので、6.4*10^5ですかね。これならまだ間に合いそうです。また、これに何かしらのlogがついても何とかなりそうですね。
中央値の最小値、logがついてもいい
となると、候補に挙がるのはあいつですね。二分探索です。
ただ、その判定方法を考えるのに苦労しました。ですので、「中央値、2分探索」でグーグル先生に聞きました。すると、なんだか似た例を扱っている問題が見つかりました。ただ、今回の中央値はN/2+1番目に大きいものでしたので、その部分がこんがらがりました。
ここで、入力例とにらめっこです。入力例１は3*3のうち、2*2の範囲を扱います。もし、Xが中央値としてあり得るならば、X以下のものが2個以上あるはずです。また、入力例2は3*3です。この時には5個必要になります。
例はこの２つだけですが偶数と奇数の例が出てきました。
グリッドのマス目の数を２で割ったときの切り上げ以上
がOKとなる条件となりそうです。
これで、2分探索部分は完了です。次に待ち受けるのはその数をどうやって数えるかです。ここも骨が折れそうになりました。
愚直にやると間に合わなさそうです。畳み込み演算が必要ですので、なかなか大変な計算量になります。ここでぱっと浮かんだのは累積和です。横方向だけの累積和を取ってそれを縦方向分計算すれば答えが若干高速に求まります。
これで提出。そしてTLEでした。間に合いませんか、、、
諦めそうになりましたが、気合を入れなおしてデバッグです。デバックというか高速化です。累積和の部分がネックになっていますのでここをどうにかしなければいけません。
累積和と言えども前の値を使わないといけないんだろうなということで、CNNでいうところのフィルタを動かす際にその差分を管理して計算しました。
これでなんとかAC。残り２分でした。通ったときは嬉しいやら、びっくりやらで、うわあああ、となっていました。
でも嬉しいです。
あとがき
コンテスト中に解いた最高diffを更新しました。しかも制限時間ぎりぎりでです。なんかドラマみたいですね。本当に嬉しいです。
レーティングの方も少しずつですが上がってきています。やはりコツコツが大切ですね。一歩一歩頑張ります。
また、今回も解説を書こうと思います。前回のFをまだ積み残していますが、どうしましょう。書ける問題からやっていこうかな。
この記事が気に入ったらサポートをしてみませんか？