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$ で割ったあまり。