sankantsuの日記

技術メモ・競プロなど

ABC250 感想・反省

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完も狙っていきたい.