AtCoder Beginner Contest 179の感想

「愚直にやると遅いから高速化する！」の考えは大事。

100-200(1)-300-400-500-0で1ペナ5完1500点。

A - Plural Form

文字列を複数形に変換する。文字列の末尾がsかそうでないかで処理が変わる。具体的な処理の流れとしては、入出力を除くと「文字列の末尾の文字を取得」「その文字がsかどうかを判定」「文字列の末尾に文字列を連結」の3つとなる。それぞれの処理の仕方がわからないときは素直にググるべし。

計算量は入出力がボトルネックで、 $O(|S|)$ 。

各 $i$ に対して、サイコロの目がゾロ目かどうかを保存するboolean型の配列を用意する。この配列の中で、"true"が3個以上続いている箇所を調べたい。この判定は、「今"true"が何個続いているか？」という変数を用意して、前から順番に $i$ 番目と $i+1$ 番目の値を判定していくとできる。どちらも"true"なら変数の値を $1$ 増やし、そうでないなら変数を $0$ にする（ $0$ にするのを忘れて1ペナ）。変数の値を $0$ にする直前の値が連続でゾロ目が出た回数なので、この回数が1度でも $3$ 以上になったことがあるなら答えはYesとなる。

計算量は $O(N)$ 。

C - A x B + C

愚直に解くなら、 $1$ から $N$ までの範囲で $A, B, C$ を回して実際に計算するという方法がとれる。ただしこの方法だと計算量は $O(N^3)$ となりTLEしてしまうので、効率の良い別の解法を考える。

$N$ が固定されているので、他のもう1文字を固定して考えるとよさそうだと考える。どの文字を固定するかで解法が変わる。

$A$ を固定する場合

この場合、 $B$ を決めれば元の式を変形させることで $C = N - A \times B$ となり、 $C$ の値が1パターンに決まる。 $C$ の値は正でないといけないので、 $0 \lt C = N - A \times B$ である。変形すると $A \times B \lt N$ 、さらに変形すると $B \lt \frac{N}{A}$ となり、 $B$ の値も一意に決まることがわかる！（不等号を等号に直せば $B = \lfloor \frac{N-1}{A}\rfloor$ となる）
あとは $A$ に関するループを回して総和を取ればよい。計算量は、 $O(N)$ 。

$C$ を固定する場合

式変形すると $AB = N-C$ となるので、 $N-C$ の約数がいくつあるかを数えたい。ある整数に対して約数の個数を求めるのには $O(\sqrt{N})$ の計算量がかかるので、全体では $O(N\sqrt{N})$ の計算量となり、このままだと間に合わない可能性が高い。ここで、 $N-C$ の値は $1$ から $N-1$ まで連続した値をとるという特徴を利用すると、約数の個数の総和を計算量 $O(N\log N)$ で高速に計算することができる。やり方を書こうと思ったけどうまく書けなかったので、これは読者への課題とする…（ググって）
全体の計算量ももちろん $O(N\log N)$ 。

どちらの方法でもすぐ通せるようならかなり強いと思う。今回は $A$ を固定する方法で通した。

D - Leaping Tak

$dp[i]$ := マス $i$ まで移動する通り数
という風な1次元の動的計画法を考えたいが、移動方法は最大でN通りあるため、普通に書くと計算量が $O(N^2)$ となりTLEする。（公式解説を見ると、実は $O(N\log N)$ でも解けるらしい？）

現在見ているマスを $i$ とすると、入力が区間で与えられることから移動先となりうるマスはある程度固まっていることがわかるので、これを利用する。先ほどの配列dpのほかにもう一つの配列aを用意して、区間の始まりである $a[i+L]$ に $dp[i]$ を足し、区間の終わりである $a[i+R]$ に $dp[i]$ を引く。こうすることで、配列 $a$ に対して累積和を前から実行でき、マス $i$ まで見たときの $a[i]$ はまさにマス $i$ までの遷移方法の通り数となる。

計算量は、 $O(NK)$ 。

E - Sequence Sum

愚直に計算すると $O(N)$ だが、制約が大きいためTLEとなる。より高速な解法を考える。

数列 $A$ の各項はすべて $M$ で割った余りであるので、各項の値は $0$ 以上 $M$ 未満である。さらに数列 $A$ はひとつ前の項に対する漸化式によって定義されているため、同じ値が2回以上登場するなら、そこから周期的にループする。ここで鳩ノ巣原理より、第 $(M+1)$ 項までに値が重複するので、「第 $1$ 項から周期に乗るまでの総和」＋「周期を繰り返した回数× $1$ 周期の項の総和」＋「 $1$ 周できなかった分の余りの総和」が答えとなる。これを求めるには、周期の長さと $1$ 周期の総和がわかればよい。

計算量は、 $O(M)$ 。

ちなみにダブリングというテクニックでも解けるらしいがそちらの方はわかりません。一般に、周期に注目して解ける問題はダブリングでも解ける、は正しそうだけど、どうだろうか。

F - Simplified Reversi

解けなかった。愚直に石を置き換える解法だと、空間計算量の時点ですでに $O(N^2)$ かかるため現実的ではない。黒い石で構成された長方形領域を考えるとき、操作を加えても分割される長方形は高々1つだけで、すべてのクエリが終わっても領域の個数は $N$ 個ほどしかないな、ということには気づいた。これを使ってうまく解けないか悩んでいたがここでタイムアップ。この発想はかなり近いところまで行ってたようで、例えば縦のラインに白い石が置かれたとき、それより右側の黒い石が置き換えられるのは縦に置くようなクエリが飛んできた時だけなので、そのような列（同様に行も）をメモしておけばよかったっぽい。

終了時のTwitterのTLを見た限りでは、遅延セグ木で解いている人が多そうだった。遅延セグ木がわからないのでもっと精進します。

感想

D問題に少し時間をかけてしまったがしっかり5完できたのはよかった。

3匹の猫

みみねこの競プロ精進メモ