今年もやりました。
コンテストページ：Xmas Contest 2019 - AtCoder
特設ページ：Xmas Contest 2019
たくさんのご参加ありがとうございました！
A問題（作:japlj）かなり好きです。
というのも、問題を解くだけならば †凡才大歓迎パズルコンテスト† って感じなんですが、これに「速く解く」という要素が加わることにより、「状況に合わせて適切なツールを選択する」能力が求められます。この能力、特にプログラマには必須だと思っていて、つまりこの問題はプログラマの資質を問える神問ということですね。（やや大げさ）
"一風変わった"プログラミングコンテストが目指したい１つの形だと思います。
他の問題だと、J（作:hos）好き（順位表のないコンテストで見てみたかった）、K（作:hos）はストレートに面白かったです。あと、Cの満点が少ないところを見て、みんな郵便配達ができないんだなぁと思うなどしました。
僕が作ったのはスタンプシリーズの４問（＋倉庫番のおまけ）でした。
この４問はいずれも「白黒で塗られたマス目を全て黒で塗りつぶすためにスタンプを押す回数の最小値は？」という形式の問題で、スタンプの形状が問題ごとに異なっています。
最初 I 問題が作問ストックにあり、この設定で色々変なことできないかなーと思った結果残りの３問が生えました。
最初は２個ずつのsubtaskにすることで２問として出題しようと思っていたのですが、いつの間にか１問１個で４問になっていました。
結局今年は普通の問題担当の人みたいになった。
自作問題の解説を書いていきます。（倉庫番のおまけに関しては別記事で・・・）
解説
F
F - Stamps 1
スタンプ：H/2*W/2 の長方形
明らかに、4 回あれば盤面全体を塗ることができます。
つまり0~3回で出来るかを判定すれば良いです。
同じサイズの長方形３つを配置すると、必ず二辺（縦と横１つずつ）を含むようなものが１個以上あります。
つまり、４隅のどれかから貪欲に取るのを繰り返すような探索をすれば良いです。
テストケース生成、長方形の重なり方をちゃんと網羅しないといけないので結構大変だった。
（本当に全部列挙すると 2 個ですら 20 パターン以上あるので、バグが起きそうなのだけを列挙するに留めた）
ギャラリー
思った以上にWA率が高かった。（ちゃんとテストケース強かったぽくてよかった）
G
G - Stamps 2
スタンプ：
このパターンは29*29の正方形で区切ると周期的になっています。
29 = 5*5+2*2 なんですが、この式は「密度 ＝ 1 / 斜めの正方形の面積」なことを考えるとしっくりきます。
以下、想定解です。
↓ i 行目を 12*i マス左にずらす
↓ j 列目を 6*j マス上にずらす
完成。（二部マッチングの典型問題に落ちました（蟻本参照））
まぁこんなことしなくても以下にも二部マッチングみたいな構造なのでお好きな方法で通せると思います。
H
H - Stamps 3
スタンプ：横一列を奇素数間隔で塗れる
まぁまず、行ごとに独立です。
3 があるので、3 回で全部塗れます。
0~2 の判定ですが、まず 1 は、白マスどうしの間隔のgcdをgとして、
- g が二冪（1 も含む）：無理
- それ以外：gが奇素数を素因数に含むはずなので、その間隔で塗れば塗れる
さて、2 の判定ですが、最も左にある白マスを塗るスタンプの間隔を全て試します。
1 回目のスタンプで塗られるマスを除いた白マスの集合が 1 回で塗れるか（つまり間隔のgcdが二冪でないか）を高速で判定できれば良いです。
これは以下のデータ構造があれば出来ます。
- 白マスの追加/削除ができる
- 白マスの間隔（隣接のみ）の集合とそのgcdを管理する
実現方法は例えば、白マスの位置をsetで、間隔の値の集合とgcdをsegtree（indexを値に対応させる）で管理すればできます。
計算量は、追加/削除が O(H*(W log W)) 回、追加/削除の計算量が O(log W) なので、合わせて O(H*W log^2 W) です。
他にもやりようはあると思います。
I
I - Stamps 4
スタンプ：
本題。
実はこの形、右上から貪欲出来ます。
↑貪欲がうまくいくの雰囲気を感じるための図（どうずらしても、右上か左下かのどちらかにしかはみ出さない）
背景について説明します。
まず、スタンプの黒マスの集合はなにかというと、(+19,+31)な直線（下図の極細赤線）が横切るマスの集合です。
具体的に表すと、マス (i,j) について f(i,j) = i*31-j*19 の値を計算すると、一度に塗れるマスの集合はある整数 x について x < f(i,j) < x+50 となるようなマスになります。
つまり、f(i,j) を数直線状にプロットすると、連続する長さ 48 の区間を一度に塗れます。（ジャッジ解でここを 49 にしており、リジャッジ案件になりましたm(_ _)m）
あとは普通の貪欲ですね。
終わり。
