ABC478(AtCoder)参加記

今週の参加記

AtCoderのABC478に参加できなかったので、あとから解きなおししました。

今週も、問題を解いた感想と考察を文章にします。

結果

Unratedにつきレート変動なし

考察・所感

A問題、B問題

今回は繰り返し文を使ったほうが書きやすい問題でした。 各人の番号と $N$ をつかって剰余を計算すればそれぞれ $O(1)$ で正解が出そうですが、私としては計算ミスのリスクを背負いたくありません。

B問題は、一見「ナップザック問題か！？」と考えたくなる問題ですが、DPを書いた人はさすがに知り合いにはいなさそうでした。 制約を見れば総当たりで解けることが分かります。3重にfor文を書いてACできます。

C問題

私は単調増加になるよう配列のコピーをソートして、左から見て元の配列と異なる箇所を $left$ , 右から見て元の配列と異なる個所を $right$ とおきました。 $left$ と $right$ の差がKなら「操作」で並び替えてYesを出力する可能性があるので、それについて考えます。 操作する区間の最小値と最大値が $left$ より左、 $right$ より右に登場していなければYesとしました。 細かい実装が苦手なところが改善しておらず、3回間違いましたが無事ACしました。

D問題

imos法の応用ですね。 イベントとして区間と整数 $X_i$ が与えられるので区間の端に「 $X_i$ を追加する」「 $X_i$ を取り除く」をメモして後から復元するという発想でした。 基本的なimos法と異なる点は捜査対象が集合である点で、辞書をもってメモを追いかけるという操作が必要でした。 無事AC。

最後に

Eまで解けませんでしたが、細かい実装を最後まで通せたの点はよかったところです。 過去問を解くということをほとんどしないせいでほぼ1週間ぶりにAtCoderの問題を解くことになっていますが、実力がそこまで落ちていないことに安心しています。