sankantsuのブログ

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

ほぼ手をつけていない

atcoder.jp

結果

atcoder.jp

ABCDE5完 (85:55 + 2ペナ)

コード

github.com

各問題の振り返り

A

隣接マス数を調べる問題

コンパクトに場合分けを書こうとして，行/列がひとつしかないような場合を見落としてし，修正に少し時間食ってしまう．入出力例がそれなりにしっかりしていたのでWAは避けられたが，サンプル次第ではWA出てもおかしくなく危なかった．絶対の自信があるわけじゃないなら，最初から愚直に書くほうが良いか．

サンプルが多く，入出力コピペにかかる時間もまあまあ消費していたような気がするので atcoder-tools の導入をするか，自作の同等のツールを改修するかしたい．

6分消費

B

チェス盤のような模様を描く問題

それほど問題なく書けたと思う．

5分消費

C

ボールの入れ替えをシミュレーションする問題

安直に書くとボールの入れ替え一回に $O(N)$ かかるので，多少工夫が必要．現在のボールの状態を並べた配列と，ボールの値から位置を調べる配列の2つを用意して管理することで解ける．

最初の提出で配列の範囲外アクセスを起こしてしまい，WA1回．訂正したのはいいが，cerrへのデバッグ出力を消し忘れたまま提出していまいTLEでさらに+1ペナ．間違い無く今回一番のやらかし．

配列はとりあえず何も考えずにmax+10ぐらいとっておいたほうが良いかも．

19分消費

D

特定の形に因数分解できる数の個数を調べる問題

3乗して $10^ {18}$ 以下にする必要があるので， $10 ^6$ 以下の素数について全探索すれば良さそうとわかる．

それほど問題なく書けたと思う．エラトステネスとかはライブラリ化しておくと時間削減できそうではあるが，実装練習という意味合いも考えて今はまだやらなくてもいいかなあと思っている．

9分消費

E

2つの数列の先頭を含む部分列に含まれる数の集合の一致判定をする問題

集合の一致判定に $O(N)$ かかるナイーブな方法だと $O(NQ)$ でTLEなのはすぐにわかる．集合の一致判定を $O(\log N)$ 以下にしたいという発想．

$A,B$ の先頭 $x$ 項に含まれる値の集合を $SA_x,SB_x$ とする先頭から順に要素を見ていったとき，すでに出現している要素がまた現れても集合としては要素は増えないので，新しい要素が出たときだけ注目すれば良いとわかる． $A,B$ それぞれに対して新しい要素が出現するときの添字を計算した配列 $v_A,v_B$ をつくってみる．

$v_A,v_B$ を使うと集合のサイズの判定は定数時間で済むが，中身の一致判定はまだ $O(N)$ かかるので，これを削減したい．そこで，集合のサイズが同じになる場合に要素集合も同じかどうか事前計算しておけないか考えてみる．

一致判定のために集合の要素を全走査すると $O(N)$ は避けられない．そこで，集合の要素が増えるタイミングで，いま増やした要素が差分に影響するかどうか考える．つまり， $|SA_{x-1}| \lt |SA_x|, |SB_{y-1}| \lt |SB_y|, |SA_x| = |SA_y|$ を満たすような $x,y$ について， $a_x,b_y$ がそれぞれ $SB_y,SA_x$ に含まれるかどうかを考えることによって差分を管理する．この方法なら $O(N \log N)$ で集合の一致判定まで含めた前処理が可能で，あとは1クエリあたり $O(\log N)$ 時間で処理できる．

時間はまあまあかかったが，水diff(diff 1421)なのでとりあえず解けただけで上等

55分消費

F

すぐに思いつくのは頂点ペア全探索の $O(N^ 2)$ これだとTLEなので，探索するペアの数を減らせないか考える．

一個の頂点Aを固定してもう一方の頂点Bを動かしていったとき，囲む面積が1/4を超えたらもうそれ以上見る意味はない．そのタイミングでAを1個ずらしてまたBを動かしていくという感じのしゃくとり法でうまくできそうというところまでは思いつく．

三角形の面積は，外積を使ってうまく計算できる．

実装時間全然足りず，コンテスト終了

終了後に自力AC． Eまでを速く解けるようにすることで，そのうち6完も狙っていきたい．

sankantsuのブログ

技術メモ・競プロなど

ABC251 感想・反省

結果

コード

各問題の振り返り

A

B

C

D

E

F

ABC250 感想・反省

結果

コード

各問題の振り返り

A

B

C

D

E

F