sankantsuの日記

技術メモ・競プロなど

ABC251 感想・反省

atcoder.jp

結果

atcoder.jp

ABCE4完 (69:09)

コード

github.com

各問題の振り返り

A

文字列を適当な回数繰り返し出力するだけの問題

簡単

1.5分消費

B

与えられた数列から3個以下を選んで和としてつくれる数の個数を数える問題

N\leq300と小さいので,O(N^ 3)の全探索で良さそうとわかる.

3個選ぶ全探索なので3重ループで書くのが基本だが,それだけだと1個や2個の場合がカバーできない. 少し考えて,仮想的に重さ0のおもりを2つ足して考えることで単一の3重ループで書けるようにした 解説にあるように1個や2個は別処理で書いたほうが素直だった気もする. A,B問題はあまりひねらず愚直に書いたほうが結果的に早く書けることが多いような.

8.5分消費

C

キー(文字列)が重複していない要素の中から最も高いスコアのものを選ぶ問題

文字列の重複判定を,それ以前に出現したすべての文字列と比較することによって行う愚直な解法だとO(N^ 2)でTLEなので,重複判定を高速化する必要がある.

重複判定をhashで行うことを考えたが,C++の hash tabel (unorderd_map) はあまり使い勝手がよくない.

重複判定は O(log N) でも十分間に合うのでset で十分ということに気づき,set を使って書いた.

8分消費

D

B問題の変種で,与えられた数以下の任意の数を3個以下の和としてつくれるような数列をひとつ求める問題

他の問題とは少 し異質で,Heuristic コンテストみたいな印象を受ける. 方針が浮かばないので小さいほうから詰めていったり,適当にO(2^ x)を詰めてみたり試してみるがうまくいかず. 途中でE問題に移行した.

コンテスト中には解法浮かばず. 解説を見て,解けなかったのは悔しいが面白い問題だと思った.

解説を書いた. https://sankantsu.hatenablog.com/entry/2022/05/15/021351

E

 N 個の頂点が円形につながっているグラフの最小点カバーを求める問題とみなせる.

ある頂点をカバーするためには,つながっている辺のどちらか1方はとる必要がある. このことを利用して,頂点1から頂点iまでをカバーするために必要な最小コストを順にDPで求める. 頂点1を選ぶときに行動1を使うか行動Nを使うかで場合分けすると良い.

60分消費 (D問題の試行錯誤もあるので,実質は30~40分ぐらい?)

解説を書いた. https://sankantsu.hatenablog.com/entry/2022/05/15/115203

F

ほぼ手をつけていない