忍者ブログ

競プロ日記

競技プログラミングの問題を解いた感想を書きます。

[PR]
×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。

ABC149
問題

unrated

4完
初めて参加したコンテストがunratedになった。
出来はひどかったので助かった。

A問題

かんたん。

B問題

問題文読み間違えた。
問題文のGreedy Takahashiからして、高橋くんは自分も青木くんもクッキーを持ってる場合、青木くんのクッキーから食べにかかると思って実装してしまった。
普段BくらいまではACを見ずに次の問題に取り掛かるのだが、今回はCを提出した後に20/20の表示でまだジャッジ中だった。
遅くない???と思いつつもDに取り掛かり、途中でBがWAしてるのを確認。
問題の読み間違いに気づき、再度提出してDに取り掛かる。
しかしBだからと高をくくって詰めが甘くてまたWA。
今度はDを解いた後に気づいた。
最終的にACDBという珍しいAC順になった。
毎回毎回あほらしいミスを繰り返しているが、簡単なBで何度もやらかしてしまったのは反省点高い。

C問題

かんたん。
エラトステネスの篩張ったら終わった。

D問題

最近のDにしては複雑な問題だなーという感想。
K個前の値を保存してDPすれば良さそう・・・と思ったのだが、どう頑張ってもK個前の値だけじゃ遷移を進められない。
「K個前の値」じゃなくて「K個前までの全ての値」を保存しないといけないという考えから抜け出せなかった。
あるところでK個毎に独立してるのでは?と気付き、modKで分けてDPの方針が立った。
この時点で結構時間が立っており、これ以上ミスを重ねたくないとかなり安定志向の実装にしたつもりだが、modK毎のインデックスがすんなりいかずデバッグにかなり時間を取られた。

最初は出す手を数字と連想配列でうまく関連付けてシンプルな条件式にしようとしていたのだが、安定志向で条件式が長くなってしまった。
今回はミスしなかったが、長いとミスも増えるしどっちが良いのか悩みどころ。
うまく関連付ける内容は、詳しい部分は忘れてしまった。
もう去年の話だぞ。
記事書いてるのは徹夜明けの早朝6時過ぎだぞ。

最終的にACしたのが73分。
時間かかりすぎ。

聞くところによるとDPなんかしなくても貪欲で良いらしい。
ちょっと考えてみればすぐわかる話だ。
とりあえず勝てるなら勝てる手を出せば、他の順番と比べて同じ点数になることはあっても悪くなることはない。
最善が複数ある場合に貪欲で解けるっていうの慣れないとなと感じた。
これゲーム問題の分野かな。
ゲーム問題も解かないとなぁ。

E問題

去年の話なのでもうあまり覚えていない。
去年の話とかいう便利な言葉。
とりあえず覚えているのが、AGC 020 Cを思い出したこと。
解いていないのだが、解説をちらっと読んだ覚えがあった。
全ての組み合わせの中から、大きい方からM個を考える時、必ず満たす性質がないかというのをずっと考えていた。
しかしうまくいかずにタイムアップ。

解説PDFをちらっと見て理解した解法が、ある値を決め打つ二分探索を基本として、その二分探索の途中でさらに二分探索をする方法。
2回目の二分探索がPDFで言う「左手で握手する人を先に決めたとき、右手で握手できる人が何人いるかは累積和を用いることでO(1)で求まる」という部分で、最初この部分が理解できなかったので、方針だけ理解して二重に二分探索すればできそうだなと考えた。
制約的にはO(Nlog^2N)でも間に合いそうだが、部分問題として考えるとO(logN)からO(1)は結構大きいので、この累積和の部分を頑張って考えた。
理解はできたのだが、PDFはもうちょっと詳しく書いてほしいなー。

累積和といえば累積和だが、「V[i] = 数列中のi以上の数」と見れば良いだけで、インデックスとして考えるのではなくて値として考えるというちょっと変わった累積和だ。
だから数列中の値の最大値も重要になってくる。

こういう添字に意味を持たせるタイプの問題ずっと苦手だなぁ。
記事に書いた記憶があるが、BITの添字に意味を持たせるタイプの問題で、「こういうデータの持ち方するという発想に至るのきついなぁ。考えられるようになれるかなぁ。」といったことを書いた記憶があるのだが、やはりきつい。
次はこういう発想も道具として取り出せるようにしておきたい。

F問題

なんかむずかしそー。
完。
まぁunratedだし?という気持ちが溢れてた。

まとめ

2019年最後がunrated!
まぁ助かった。

このコンテストは自分の苦手ポイントを自覚させてくれて得られるものが大きかったように思う。
ミスをするなというのは言わずもがな。
・modKで考える発想。
・必ずしも最善は一択ではなく、そのうちの1つが分かれば良いという発想。
・累積和やBIT等、配列的なデータ構造のインデックスに意味を持たせる発想。
この3つが足りないと感じた。
modKは最近の問題でも理解に時間がかかったばかりだ。
値を決め撃って二分探索する発想はかなり浮かぶようになってきたので、この感覚を参考にこれらの発想も定着させていきたいね。

今日は2020年初のコンテスト。
参加するなら新年初C++コーディングになる。
年末年始全くやっていないので心配だなー。
PR

コメント

コメントを書く