ganmo::cout

競技プログラミング始めました

AtCoder Beginner Contest 129

今回は数学問が出たので温まってやっと青色になれました!!!
ですが凡ミスで黄パフォ出し損ねたのでそれはそれ

A - Airplane (100点)

問題: A - Airplane
環状線の3点を巡回するルートではどれか1つの道を通らないので、A+B+C-\max\left\{ A, B, C \right\}を出力してAC。O(1)
maxとmin間違えて1WA出してしまいました

拙解 (C++14): Submission #5834846 - AtCoder Beginner Contest 129

B - Balance (200点)

問題: B - Balance
素朴に全探索する。累積和を取ればO(N)だが、N \le 100なのでいちいちすべてのTについて2グループの和をとってO(N^2)でも十分間に合ってAC。

拙解 (C++14): Submission #5837108 - AtCoder Beginner Contest 129

C - Typical Stairs (300点)

問題: C - Typical Stairs
ド典型のDP問題。
\displaystyle dp[i] := i段目にたどり着くのに何通りか?
とする。まず0段目には「何もしない」の1通りでたどり着くため、dp[0]だけ1であとは全部0で初期化する。i段目にたどり着く方法はi-1段目とi-2からの2通りあるので、
\displaystyle
dp[i] = \begin{cases}
dp[i-1]+dp[i-2] & i段目の床が壊れていない \\
0 & \text{otherwise}
\end{cases}
\mathrm{mod} 10^9+7をとりつつ素直に実装してAC。

拙解 (C++14): Submission #5839535 - AtCoder Beginner Contest 129

D - Lamp (400点)

問題: D - Lamp
行/列ごとに見たときに '.' がいくつ連続しているかを、行でのそれをR_{i,j}、列でのそれをC_{i,j}としてO(HW)*1で前計算する。そうするとマス(i,j)にランプを置いたとき照らされるマスはR_{i,j}+C_{i,j}-1個となるので、これをすべてのマスについてチェックして最大値をとってAC。O(HW)

拙解 (C++14): Submission #5844368 - AtCoder Beginner Contest 129

E - Sum Equals Xor (500点)

問題: E - Sum Equals Xor
全加算器を考えると、繰り上がりが生じたときには次の桁がNXORになってしまいa+b=a \mathrm{XOR} bが成立しなくなるので、考えるべきは各桁が(0, 0), (1, 0), (0, 1)のものだけになる。ここで、Lを超えてはならないので、たとえばL={101100101}_{(2)}のとき、

101100101
101100100
1011000**
1010*****
100******
0********
(ただし'*'は0あるいは1のどちらでもよい)

のように1のある桁を0にして、その後ろが任意、という風にすればよい。Lが2進数N桁として、上i桁をLに一致させるのが何通りであるかをとってdp[i]とし、あとは'1'の桁について、上のように任意の桁がd桁あるときdp[i] \times 3^{N-1-i}をmodを気にしつつ足していけばAC。O(N)
L<2^{100,001}などの巨大な数でも文字列として扱うことができればO(\log L)になって間に合う。この前予選落ちしたGCJでもあった。

拙解 (C++14): Submission #5848363 - AtCoder Beginner Contest 129

F - Takahashi's Basics in Education and Learning (600点)

問題: F - Takahashi's Basics in Education and Learning
二分探索してs_i=A+Bi<10^dを満たす最大のiを求めていけば、d桁の項の個数C_dを求めることができる。
(以下、Editorial見ました)
ここで、(作る整数, 足していく項の値, 1)というベクトルを考えると、足していく項の桁数をdとして、
\displaystyle (X, s)\mapsto(X10^d+s,s+B)
とする写像を構築すればよく、これは線形写像
\displaystyle
\mathbf{x}_{i+1} = \begin{bmatrix}
10^d & 1 & 0 \\
0 & 1 & B \\
0 & 0 & 1
\end{bmatrix} \mathbf{x}_i, \\
\mathbf{x}_0 = \begin{bmatrix}
0\\
A\\
1\\
\end{bmatrix}
なので、行列累積が使えてO(\log L)に持ち込むことができる。すべての2\le d\le 18について10進d桁の項C_d個に対して上記の線形写像を行列累乗で(mod Mを気にしつつ)適用し、第1成分を出力してAC。項数パートと行列累乗パートともにO(\log L)で、全体としてもO(\log L)

拙解 (C++14, コンテスト後): Submission #5862559 - AtCoder Beginner Contest 129

まとめ

F問題は10^{18}なんていう中途半端に巨大な制約だったら行列累乗で行くべきでした、項数パートまで解けてただけに残念です
それ以前にA問題の凡々ミスで黄パフォ取り損ねたのはとてもくやしい
でも青くなれたのでよし(よくないが)

*1:うまく実装すると同じマスを丁度2回走査するのでO(H^2W^2)にはならずに済む