今週の競プロ（2024/04/22 〜 28）

2024年4月28日 20:04

今週の復習

復習のルール
【平日】前日にACできなかった問題を復習する。月曜日の場合は、過去にACできなかった問題を適当に選んで復習する。時間があるときはAtCoder Daily Trainingにバチャで参加する。
【土日】平日に復習した問題をACできるかチェックする（週末は平日に復習した問題に集中する）。

今週、復習した問題は以下の10問です。

ABC350-C Sort
ABC324-D Square Permutation
ABC324-C Error Correction
ABC323-D Merge Slimes
ABC321-D Set Menu
ABC230-C X drawing
ABC221-C Select Mul
ABC219-D Strange Lunchbox
TPDC-C トーナメント
TPDC-B ゲーム

ABC350-C Sort

問題はこちら / ACしたコードはこちら

各数字の位置を覚えておいて、欲しい数字と今見ている数字の位置を入れ替えます。
欲しい数字をみているのか、または数字の位置をみているのかがゴチャゴチャになってしまうので注意です。

ABC324-D Square Permutation

問題はこちら / ACしたコードはこちら

問題文の「より厳密には」以降が難しくて無理っぽいなぁと思いました。
この問題は「並び替えたらSになる平方数は何個ありますか？」という問題に読み替えると、ACできそうな気になるのですが、そういう発想の切り替えが本番中にできればいいなと思います。

ABC324-C Error Correction

問題はこちら / ACしたコードはこちら

前から一致する文字数と後ろから一致する文字数を数えればいい問題。
場合分けで何度もミスしているので、注意が必要です。

ABC323-D Merge Slimes

問題はこちら / ACしたコードはこちら

取り出して、いろいろやって、戻したり、戻さなかったりという感じの問題です。
ABC328-D Take ABC や ABC351-C Merge the balls と同じような印象。
本来なら計算量を証明する必要があるのですが、なんとなく「まぁ、Nの2乗よりは少ないよな。$${N log N}$$ くらいだろう」と軽いノリでやってしまうのでそのうち痛い目に合いそうです。

ABC321-D Set Menu

問題はこちら / ACしたコードはこちら

二分探索で $${x}$$ 以上の個数を数えることができると、スムーズにACできる問題。
しかし、$${x}$$ 以上の個数が $${0}$$ の場合を考えるのを忘れていて何日もACできませんでした。

ABC230-C X drawing

問題はこちら / ACしたコードはこちら

AtCoder Daily Trainingにバチャで参加したときにACできなかった問題です。
$${max(1-A, 1-B) \leq \leq min(N-A, N-B)}$$ を
$${(1-A) \leq k \leq (N-A)}$$ かつ $${(1-B) \leq k \leq (N-B)}$$ と変形できるのに気がつきませんでした。
式を変形してみるのも大事です。

ABC221-C Select Mul

問題はこちら / ACしたコードはこちら

AtCoder Daily Trainingにバチャで参加したときにACできなかった問題です。
9桁くらいの数字なので、全パターン試せそうだなと気がつかないといけない問題です。
全パターンをどう作るか（bit全探索、順列全探索）という問題になりますが、最近 DFS ばかりやっていたので、DFSでACしました。

ABC219-D Strange Lunchbox

問題はこちら / ACしたコードはこちら

AtCoder Daily Trainingにバチャで参加したときにACできなかった問題です。
$${300 * 300 * 300 = 27,000,000}$$ になるためDPできないなぁと思い、ハマってしまいました。
$${300 * 300 * 300 = 27,000,000}$$ はいけます。

TPDC-C トーナメント

問題はこちら / ACしたコードはこちら

つまずいたところがたくさんあった問題。
・対戦する可能性がある人は誰か？
・すでに対戦したのでもう対戦しない人は誰か？
この2つを計算する方法がよくわかりませんでしたが、何度も解くことでわかってきました。
そして、$${i}$$ 回戦目で $${j}$$ が $${k}$$ に勝利する確率を DP で計算するのところで何度もミスしました。