今週の競プロ（2024/05/06〜12）
今週の復習
AtCoder NoviStepsで、5Qから2Qに問題が追加されたので、それらの問題を中心に復習しました。復習した問題（一部）は下記の通りです。
ABC351-C Merge the balls
ABC341-D Only one of two
ABC160-C Traveling Salesman around Lake
競プロ典型90問 002 - Encyclopedia of Parentheses（★3）
競プロ典型90問 007 - CP Classes（★3）
競プロ典型90問 038 - Large LCM（★3）
ABC351-C Merge the balls
問題通りシミュレーションします。
私は、dequeを使う方法がしっくりきました。
似た問題として ABC328-D TakeABC があります。
ABC341-D Only one of two
「包除原理」を考えると道筋が見える問題。
「ちょうど一方のみ」を「（Nで割り切れる数 ＋ Mで割り切れる数）− （NとMの両方で割り切れる数 × 2）」と変形して計算します。
NとMの両方で割り切れる数は、NとMの最小公倍数で割り切れる数になります。
ABC160-C Traveling Salesman around Lake
円環なので、N軒を2N軒に広げてしゃくとり法っぽくしたり、N軒目と1軒目の間について慎重に実装する必要があります。
この問題は合計から1本だけ辺を除いたときの最小値を求めたらいいので、N軒目と1軒目の間を慎重に実装する方法の方が楽かもしれません。
競プロ典型90問 002 - Encyclopedia of Parentheses（★3）
「カッコ列」と書いてあるので deque か？と思ったら、違ってて bit全探索の問題です。
しかし、bit全探索の全パターンから正しいカッコ列を抜き出すのが難しい。
競プロ典型90問 038 - Large LCM（★3）
何度もWAを出した問題です。
AとBが大きいのでC++の場合、long long 型の最大値を超えないように計算する工夫が必要です。
AとBの最小公倍数 = A /（A と Bの最大公約数）× B と変形できるので、
10^18 < A /（A と Bの最大公約数）× B の場合は Large を出力するように実装します。
ABC353に参加しました
Unratedですが、ABC353に参加しました。
結果は、ABCの3完で 4158 / 13,169 でした。
C問題は時間がかかってしまったのですが、解法を考えてACできたのでよかったです。1WAはデバック用の出力を消し忘れたWAなので、要注意です。
D問題も解法はいい感じだったのですが、long long 型の最大値を超えないように計算する工夫がうまくいかず時間切れでした。D問題もACできそうでしたので、残念でした。
次回もがんばります。
今週のAtCoder NoviSteps
今週末の状況は下の画像の通りです。
今週は5Qから2Qに問題が追加されたので、それらの問題を復習しました。
2Qに追加された問題がまだ10問残っているので、来週はこの10問を中心に復習します。
この記事が気に入ったらサポートをしてみませんか？