今週の競プロ（2024/04/29 〜 05/05）

2024年5月5日 16:37

今週の復習

今週は、AtCoder NoviStepsの2Qの未AC問題を中心に以下の5問を復習しました。

結局のところ、$${A_i}$$ と $${B_i}$$ をつなげてできたグラフが二部グラフか否かを判定しなさいというシンプルな問題になります。そこに気がつくまでが大変。あきらめずに、サンプルを参考に紙に書いてみて、いろいろ試そう。

3つの 'o' のうち1つは必ず縦と横の交差点であると決めてしまうと数えやすくなります。交差点に注目するというのはAHC005で気がつかず、くやしかったので覚えています。

問題通りに引っ張られて動いている様子をイメージしてしまうと、どうしたらいいかわからなくなります。入力例1の図をよく眺めると最後の点が無くなり、先頭に点が追加されているように見えます。そう見えると解けそうです。最初と最後に注目する問題はよく見かけます。

各連結成分で完全グラフを作るには、何本の線を引く必要がありますか？という問題になります。連結成分といえば、Union Findが楽ですね。

答えで二分探索、みたいな問題。解説で説明されている P × K ≤ sum の時は P 個以上のプロジェクトを作ることが可能であるという点がパッと思い浮かばない。状況をじっくり考える練習がまだまだ足らないなぁ。

Unratedですが、ABC352に参加しました。
結果は、ABCDの4完で 3537 / 12,786 でした。

425点のD問題を初見、0WAでACできたのはよかったです。
E問題は最小全域木 → クラスカル法は思いついたのですが、最小全域木をよく理解していなかったので、ACできませんでした。やっぱり、性質というか特徴というか、その辺りを理解することは大事ですね。
次回もがんばります。

今週もAtCoder Daily Training（MEDIUM）にバチャで参加して、練習しました。

D問題（2問目）の1WAはコピペのミスでした。このようなミスは減らしたいです。
G問題（5問目）は手も足もでませんでした。来週復習します。

F問題（4問目）までスッとACできていい感じでした。

残念ながら3完でした。
F問題（4問目）はACできたなぁと反省しています。

D問題（2問目）の1WAは条件の入れ忘れです。多分大丈夫だろうと思ったらダメでした。これはダメなWAでした。

今週末の状況は下の画像の通りです。

今週で2Qの問題ほぼ終わりました。
来週から1Qの問題に挑戦します。1QにはDPの問題が多く入っていそうで苦戦しそうです。じっくりがんばります。

この記事が気に入ったらサポートをしてみませんか？