2016-09-19

AtCoder Regular Contest 061 + AtCoder Beginner Contest 045

成績

ARC参加で354位。なかなか緑にはならない。

解法メモ

A問題

台形の面積は $S=(a+b)\times h/2$ 。

B問題

3人の手札と捨てられたカードの文字を変数に持たせて、実際にシミュレートすればよい。3人で最大300枚しかカードを持っていないのですぐに終わる。

C問題

結局のところ、与えられた数字列をバラバラに分解して、数字と数字の間に順番に+を入れたり入れなかったりしていけばよい。
ビット演算をつかえば効率が良い。最大で10文字しかないので、使うビットも最大9個だから十分。

D問題

C++とかならばmapを使えば一発らしいが、あいにくC言語にそういうのは用意されていない。
黒マスは最大で $10^5$ 個しかないから、与えられた黒マスに対して、そのマスによって黒マスの数が変化するような3行3列のマスを列挙していけばよい（最大 $9\times 10^5$ ）。3行3列のマスが識別できればよいから、どこか1つのマス（例えば左上）を代表として表すことにすればよい。
列挙したマスを上・左からの昇順でソートすると、それぞれの3行3列マスには出現した回数だけ黒マスがあることになる。
列挙したマスを順番に見ていって、1～9個あるマスの個数を数え、最後にその総和 $S$ を計算しておけば、黒マスのない3行3列マスは $(H-2)\times(W-2)-S$ 個あることがわかる。

わかってしまえばあっという間なのにわからなかったのが悔しい。

E問題

二部グラフを使えばよいらしい。まだわかっていない。

F問題

捨てられたカードを順番に見ていくことにする。たとえば、abcbacaa とカードが捨てられてゲームが終わったとする。

ゲームが終わったときにAのターンだから、Aが勝ったことになる。すなわち、Aが勝つためには最後に捨てられたカードが a でなくてはならない。
Aのターンでゲームが始まって、Aのターンでゲームが終わったから、Aは最初カードを4枚 (abca) 持っていたことになる。これは、a が書かれた捨てられたカードの枚数と一致する。
Bは先頭から ca 、Cは先頭から ba というカードを順に持っていたことがわかる。これも、b, c が書かれた捨てられたカードの枚数に一致する。

以上のことから捨てられるカードの順列は、最後に a が来るような、 $N$ 個の a、 $M$ 個以下の b、 $K$ 個以下の c の並べ方の総数に帰着する。

いま、 $i$ ターン目にAが最後に a のカードを捨てて勝ったとする。
並べる b の個数を $X$ 、c の個数を $Y$ とおくと、Bの持つ $M-X$ 枚の手札とCの持つ $K-Y$ 枚の手札はどの文字が書いてあってもよい。すなわち、カードの組み合わせは $3^{M+K-X-Y}$ 通り。
$i = N+X+Y$ だから、 $3^{M+K-X-Y} = 3^{N+M+K-i}$ 。
$i$ ターン目までに捨てられた $i-1$ 枚のカードのうち、a のカードが $N-1$ 枚、残る $i-N$ 枚が b, c のカードである。この組み合わせの数は、
$\displaystyle {}_{i-1}C_{N-1}\;{}_{i-N}C_X = \frac{(i-1)!}{(N-1)!(i-N)!}\frac{(i-N)!}{(i-N-X)!X!} = \frac{(i-1)!}{(N-1)!(i-N-X)!X!}$
通り。
したがって、求める数は
$\displaystyle \sum_{i=N}^{N+M+K} \sum_{X=0}^{\min(M,i-N)} 3^{N+M+K-i} {}_{i-1}C_{N-1}\;{}_{i-N}C_X$
を $10^9+7$ で割ったあまり。

二項係数を求めるところは、フェルマーの小定理を使って、 $i!$ と $(i!)^{-1}$ ( $0 \leq i \leq 900000$ )を事前に求めておく。

部分点解法

愚直に二項係数の総和を求めると時間を食うので、部分点しかとれない。

満点解法

二項係数 ${}_nC_r$ ( $0 \leq r \leq n$ ) の総和は $2^n$ である（二項定理）。このことを利用して、二項係数の和を一気に求める。

f:id:k-ashiya:20160919175048p:plain

図の破線で囲まれた部分の二項係数の和を求めてみよう。

1段目の和は1。
2段目の和は、1段目の1が2回現れるので1段目の2倍で2。
3段目の和は、2段目の2つの1がそれぞれ2回ずつ現れるので、2段目の2倍で4。
4段目の和は、3段目の3つの数がそれぞれ2回ずつ現れるので、3段目の2倍で8。
5段目の和は、4段目の左端を除く3つの数がそれぞれ2回ずつ現れ、左端のみ1回現れるので、4段目の2倍から4段目の左端を引いて15。
6段目の和は、5段目の両端を除く2つの数がそれぞれ2回ずつ現れ、両端はそれぞれ1回現れるので、5段目の2倍から5段目の両端を引いて25。
7段目の和は、6段目の中央の数が2回ずつ現れ、両端はそれぞれ1回現れるので、6段目の2倍から6段目の両端を引いて35。
8段目の和は、7段目の2つの数がそれぞれ1回ずつ現れるので、7段目の2倍から7段目の両端を引いて35。

以上のことから、

1段目の和は1。
$n\;(n \geq 2)$ 段目の和は、 $n-1$ 段目の和の2倍から、追加しない側の $n-1$ 段目の端の数を引いたもの。

というようにして高速に求めることができる。

キーワード

C問題

ビット演算

F問題

フェルマーの小定理、二項定理、二分累乗法

2016-09-03

AtCoder Regular Contest 060 + AtCoder Beginner Contest 044

競技プログラミング

解法メモ

A問題

合計の宿泊費は、 $N \leq K$ ならば $NX$ 円、 $N>K$ ならば $KX+(N-K)Y$ 円。

B問題

$w$ はたかだか100文字なので、どの文字がいくつあるか先頭から順に数えていって、奇数個の文字がひとつでもあれば"No"、ひとつもなければ"Yes"を出力する。

C問題

動的計画法で解く。
$dp[i][j][k]$ を、 $x_1$ から $x_i$ までのカードから $j$ 個とって合計を $k$ にすることができるカードの取り方の総数とする。すると、
$\begin{eqnarray} dp[i][j][k] = \begin{cases} 1 & ( i = j = k = 0 ) \\ dp[i-1][j][k] & (i \geqq 1\ \mathrm{and}\ k < x_i ) \\ dp[i-1][j][k] + dp[i][j-1][k-x_i] & (i \geqq 1\ \mathrm{and}\ j \geqq 1\ \mathrm{and}\ k \geqq x_i ) \\ 0 & (\mathrm{otherwise}) \end{cases} \end{eqnarray}$
と漸化式が立てられる。カードの平均が $A$ となるような組み合わせの数は $\sum_{k=1}^N dp[i][k][kA]$ だから、これを出力する。

上とは別に、

D問題

$s = n$ のときは明らかに $b = n+1$ 。0 から $n$ までの数が各桁に使われるのは基数が $n+1$ 以上の場合に限られるし、基数が $n$ 以下のときに各桁の和が $n$ になることはない。
$2 \leq b \leq n$ について愚直に $f(b,n)$ を計算すると時間がかかってしまうので、よい方法を考える。
$\sqrt{n} < b$ のとき、 $n$ の $b$ 進数表記は2桁以下になる ( $n = 100_{(\sqrt{n})}$ )。つまり、 $b$ 進数表記が $pq$ のとき、 $n = pb + q$ と表される。これより、 $b = (n-q)/p$ である。また、 $p+q=s$ だから、 $1+q/p=s/p$ より $b = (n-s)/p+1$ となることがわかる。すなわち、 $p$ と $s$ の値から $b$ が一意に定まる。こうして定められた $b$ が $f(b,n) = s$ を満たすかどうかを確認すればよい。

E問題

$r[i][k]$ を、 $i$ 番目のホテルから $2^k$ 日以内に到達できる最も右側のホテルの番号として、まず $r[i][0]$ を求め、次に $r[i][k+1] = r[r[i][k]][k]$ として順次求めることができる。こうしてできたテーブルを二分探索すればよい。

二分探索を工夫する

しかし、C言語の二分探索関数は、値が見つからないとNULLを返してくるので、いちばん近い値を求めるには工夫がいる *1。
今回は自作の二分探索関数を作ることで対応した。要素の数が奇数のときは、見ている範囲の中央にある2つの要素両方を見て判定する工夫を施した。
Submission #860171 - AtCoder Regular Contest 060 | AtCoder
また、最右端まで到達できるときは、最右端の番号ではなくてそれより大きな番号を格納しておくと、「それより少ない日数で最右端に到達できる」ことがすぐにわかる。

F問題

まだよくわかっていない。

キーワード

C問題

動的計画法

*1:このあたりの「かゆいところに手が届く」ライブラリやら関数やらがたくさん揃っているところがC++が人気な理由のひとつなのかもしれない。

2016-08-26

AtCoder Regular Contest 059

競技プログラミング

AtCoder Beginner Contest 043 と同時開催。
k-ashiya-code.hateblo.jp

コンテストページ

arc059.contest.atcoder.jp

解法メモ

E問題

$\sum_{c_1+\cdots+c_N=C} \sum_{x_1=A_1}^{B_1} \sum_{x_2=A_2}^{B_2} \cdots \sum_{x_N=A_N}^{B_N} x_1^{c_1} x_2^{c_2} \cdots x_N^{c_N}$ を計算する。
まず、 $c_i$ が定数であると仮定すると、
$\sum_{x_1=A_1}^{B_1} \sum_{x_2=A_2}^{B_2} \cdots \sum_{x_N=A_N}^{B_N} x_1^{c_1} x_2^{c_2} \cdots x_N^{c_N} = (\sum_{x_1=A_1}^{B_1} x_1^{c_1})(\sum_{x_2=A_2}^{B_2} x_2^{c_2})\cdots(\sum_{x_N=A_N}^{B_N} x_N^{c_N})$
と分解できる。したがって、各 $i$ に対して $\sum_{x_i=A_i}^{B_i} x_i^{c_i}$ を $c_i = 0, 1, \cdots, 400$ について前計算しておく。
次に、動的計画法で、 $dp[i][j] = i$ 番目までの園児にキャンディーを $j$ 個配ったときの積の総和となるように式を立てて実行する。

F問題

小文字 a,b,c,... は0、1のいずれか、B はバックスペースを表すとする。キーボード入力が abcBdBef ならば、エディタに表示されている文字列は abef となるはずである。このとき、a,b,e,f が表す文字列の組み合わせは $2^4=16$ 通りであり、a,b,e,f としてどの組み合わせが与えられても、abcBdBef の形のキーボード入力は $2^2=4$ 通りあることがわかる。
N文字の入力でK文字の出力となるような入力の数を $f(N,K)$ と表すことにすると、 $f(0,0) = 1$ , $f(1,0) = 1$ , $f(1,1) = 2$ である。
次に、 $i \geq 2$ について、 $j=0$ のときは $f(i-1,0)$ と $f(i-1,1)$ の文字列の後ろにBを足せばよいから $f(i,0) = f(i-1,0) + f(i-1,1)$ 。
$1 \leq j \leq i-2$ のときは、 $f(i-1,j-1)$ の文字列の後ろにa（0か1）を、 $f(i-1,j+1)$ の文字列の後ろにBを足せばよいから $f(i,j) = 2f(i-1,j-1) + f(i-1,j+1)$ 。
$f(i,i-1)$ は $f(i-1,i-2)$ の文字列にaを足せばよいから $f(i,i-1) = 2f(i-1,i-2)$ 。 $f(i,i)$ は $f(i-1,i-1)$ の文字列にaを足せばよいから $f(i,i) = 2f(i-1,i-1)$ 。
以上のようにして $f(N,N)$ まで求めたあと、 $f(N,|s|)/2^{|s|}$ を出力する。

フェルマーの小定理

途中の過程で $10^9+7$ で割った余りを求めているから、単純に $2^{|s|}$ で割ることはできない。そこで、フェルマーの小定理を用いる。

$p$ を素数とする。 $a^{p-1}$ を $p$ で割った余りは1である。

証明はWikipediaに譲る。これを利用すると、 $2^{|s|}$ で割ることは $2^{10^9+7-1-|s|}$ をかけて $10^9+7$ で割った余りを求めることと同値。

二分累乗法

$10^9+7-1-|s|$ は確実に9桁以上の10進数になるから、ふつうに累乗していこうとするととても時間がかかる。そこで、二分累乗法というテクニックを使う。
まず、求めたい累乗を格納する変数 $p$ 、底を格納する変数 $b$ 、指数を格納する変数 $e$ を用意する。最初は $p=1$ 、 $b=2$ とする。
$e$ が奇数ならば、 $p$ に $b$ をかけ、 $e$ の偶奇によらず $e$ を2で割った商に書き換えて、 $b$ を2乗する。 $e$ が奇数ならば、 $p$ に $b$ をかけ、…ということを繰り返していけば、かなりの時間短縮になる*1。
プログラム上では2で割るとか偶奇の判断をするとかよりも、ビット演算で1の位のビットが立っていれば掛け算する、 $e$ を1つ右シフトする、という操作の方が早いのかもしれない。

キーワード

E問題

動的計画法

F問題

フェルマーの小定理、二分累乗法

*1:線形時間らしいけど本当にそうなのかがわからない。

2016-08-19

AtCoder Beginner Contest 043

競技プログラミング

成績

700点、77分29秒＝125位

B問題で思わぬ落とし穴にハマって2回ペナルティ食らったのがよくなかったが、D問題の部分点解法まで解けたのでわりと満足。翌日は朝早くから予定があったので解答時間途中で終了。

解法メモ

A問題

与えられた $N$ に対して、必要なキャンディーの個数は $\sum_{n=1}^N n = N(N+1)/2$ である。

B問題

入力文字列 $s$ に対して、エディタ上の文字列 $K$ *1を用意する。
$|s|\leq 10$ だから、 $|K|\leq 10$ とわかる。ヌル文字を含めて11文字確保されていれば十分。
$s$ の文字を先頭から順に見ていき、

次の文字が0のときは、 $K$ の末尾に0をつける。
次の文字が1のときは、 $K$ の末尾に1をつける。
次の文字がBのときは、 $K$ が空なら何もしない。 $K$ が空でない時は、末尾から1文字消す。

最初に $K$ をヌル文字で埋めておき、 $K$ の現在の文字位置を示す変数 $j$ を用意すればよい。 $K$ の先頭がヌル文字ならば $K$ は空だから何もしない。そうでない時は $K$ の $j$ 文字目をヌル文字に置き換えて、 $j$ をデクリメントする。

C問題

$N$ 個の整数すべてを最小コストで書き換えられる整数を $K$ とおく。コストの総和は
$(a_1-K)^2+(a_2-K)^2+\cdots+(a_N-K)^2 \\ = NK^2-2(a_1+a_2+\cdots+a_N)K+a_1^2+a_2^2+\cdots+a_N^2 \\ = N(K-(a_1+a_2+\cdots+a_N)/N)^2-(a_1+a_2+\cdots+a_N)^2/N+a_1^2+a_2^2+\cdots+a_N^2$
だから、 $K=(a_1+a_2+\cdots+a_N)/N$ とわかる。

実際には、 $(a_1+a_2+\cdots+a_N)/N$ は整数とは限らないので、一旦 $K$ をdouble型で計算し、nearbyint関数などで最近接整数 $[K]$ をとるとよい。
そのときのコストは $-(a_1+a_2+\cdots+a_N)^2+a_1^2+a_2^2+\cdots+a_N^2$ をバカ正直に展開するよりは最初から $(a_1-[K])^2+(a_2-[K])^2+\cdots+(a_N-[K])^2$ を計算するほうが早い。

$N$ 個の整数の範囲が $-100\leq a_i \leq 100$ だから全探索でもすぐに終わるが、こういう問題を数学的に解けるようになっておいたほうがあとで生きてくることがあると思う。

D問題

部分点解法

$1\leq a < b \leq |t|$ なる $a,b$ に対して、 $a$ 文字目から $b$ 文字目までの間に各アルファベットが何回出てくるか毎回数え、どれかひとつでも過半数になった瞬間に探索を打ち切って答え（ $a b$ ）を表示する。 $2\leq |s|\leq 100$ を満たすデータセットに対しては時間内に答えが出せる。

満点解法

$t$ がアンバランスな文字列であるのは、 $t$ の部分列として $XX$ または $XYX$ の形（ $X,Y$ は異なる任意のアルファベット）が存在する場合に限る*2。
各アルファベット $X$ に対して、 $t$ 内で、ある場所の1文字先または2文字先が $X$ になっているところを探索する。あればそこで探索を打ち切って $a b$ を表示、なければ $-1 -1$ を表示。

*1:何を思ったのかキーボードのKにしていた。

*2:証明は文字数に対する帰納法を用いるのが簡単？