ABC250 感想・反省 - sankantsuのブログ

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)$ 時間で処理できる．