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

atcoder.jp

結果

atcoder.jp

ABCDE 5完 (68:16 + 0ペナ) 久しぶりにペナルティ0で切り抜けられたのは嬉しい．今回で無事レートも入水することができた．

コード

github.com

各問題の振り返り

A

3桁の整数の下2桁を出力する問題

int よりも string で受け取ったほうが楽

1分22秒

B

問題文は少し読みにくいが，例を見ればパスカルの三角形のこととわかる

無駄に配列を再利用して計算しようとしてしまい，実装に少し手間取る．入力サイズが小さい2次元配列でまとめて領域を確保して計算したほうが楽だった．こういうのはさらっと書けるようにしたい．

10分ぐらい消費

C

固定間隔のスワップだけでソートできるか判定する問題

要素を入れ替えられるのは $K$ の倍数間隔で並んだ要素だけなので，インデックスを $K$ で割ったあまりで分類して各部分列を並び替えることしかできない．各部分列をソートした結果，数列全体もソートされているならば Yes, そうでないなら No となる．

10分ぐらい消費

D

掛け算して平方数になる数の組を数える問題

まず思いつくものとして $N^ 2$ 以下の $N$ 個の平方数を列挙し，条件を満たす約数を数えるという方針がある．約数の列挙はもとの数の大きさの 1/2 乗程度かかるので，この場合全体の計算量は $O(N \sqrt{N^ 2}) = O(N^ 2)$ となり間に合わない．

平方数の列挙をベースに考えるのはだめそうなので，約数を直接考えることにしてみる． $a$ という数と， $ab^ 2$ という数を組にすれば，掛けた結果が $a^ 2 b^ 2$ となって，良さそうである．ただし，これだけだと数え漏れがあって $a = p^ 2 q$ のように分解できるときは， $a$ と $qb^ 2$ のペアも考える必要がある．

この方法ですべて列挙することができて， $O(N^ {3/2})$ で解ける．約数に関する考察が必要で，D問題にしてはやや難しい印象．

アイデアを詰めるのに時間がかかり，34分ぐらい消費

E

グラフ上で一定以下の距離にある頂点の番号の合計を求める問題

距離も次数も定数でバウンドされているので，一回のクエリで足すことになる頂点数は定数個にしかならない (具体的には，最大で $1 + 3 + 3^ 2 + 3^ 3$ 個)．したがって，一回のクエリは深さ制限付きの DFS なり BFS なりで適当に処理すれば定数時間なので， $O(Q)$ で解ける．

E問題にしてはやや簡単すぎるような気もする．

13分ぐらい消費

F

長方形領域のGCDを求める問題

$A_i + B_j$ をすべて保存しようと思うと，それだけで $O(N^ 2)$ の時間，空間計算量が必要となりアウト．

なんとか $A_i$ と $B_j$ に対する前処理でうまく解けないか考える必要がある． GCDの性質について考察してみると，結局重要なのは領域に含まれる数どうしの差分であるということがわかる．したがって，それぞれの数列の差分を事前に計算し，連続する区間に含まれる差分のGCDを前処理で計算すれば良さそうであると考えられる．