CodeChef October Challenge 2013を頑張ってみた
October Challenge 2013に参加しました。
初めて7問（正確には6.143問）解けたので参加記書きます。以下は解いた人が多い順です。
Maxim and Dividers
10進数表記で4か7を含むものをoverluckyと呼ぶ。n(1 <= n <= 10^9)が与えられたとき、nを割り切れるoverluckyはいくつあるか。
sqrt(n)まででnを割り切れ、かつ4か7を含むものを数える。
Little Elephant and Bamboo
長さnの配列HとDが与えられる。配列Hに対し、1つの要素を1減らし、後の要素を1増やす操作を行うことが出来る。このとき、HをDと同じ配列にするのに何回操作を行えばよいか出力せよ。無理なら-1を出力せよ。
考え方を変えると、上記の操作は「全ての要素に1を足し、1つの要素から2を引く」と考えることが出来る。なので、もしHをDに変形可能ならば（Dの総和）-（Hの総和）が(n-2)で割り切れるのが必要条件。あとは個々の要素を見ていく。
Yet Another Nice Girl
長さnの正数の配列が少年と少女に与えられる。少年と少女はランダムに配列から要素を取り出して、勝負する。少年の値をx、少女の値をyとしたとき、x^y > y^xなら少年は少女にキスしてもらえる。少年がキスしてもらえる回数の期待値を出力せよ。
xを固定したとき、yが何ならx^y > y^xになるかを考えてみると、
(i) x = 1
yが何でも勝てない。
(ii) x = 2
y = 2, 3以外は勝てる。
(iii) x = 3
3以外勝てる。
(iv) x = その他
自分よりも大きい数字と1に勝てる。
なので、少女の配列をソートして、二分探索をかければ固定したxが勝てる期待値を求めることが出来る。少年の配列の全ての値に対して期待値を求めればよい。
Sereja and Transformation
長さnの配列aが与えられる。b[i] = min(a) - a[i] + sum(a)の変形をk回行った配列をrとする。q(r) = max(r)-min(r)とする。1 <=a[i] <= mであるとき、a[i]は何通り存在するか出力せよ(mod 10^9+7)。
変形を見て難しそうに思えるが、実は配列内の要素の相対的な差は変わらない。なので、配列aで最大値と最小値を固定し、その数を数えればよい。
Edit Distance on Grid
N*Mの二次元格子が与えられる。各格子は白か黒で塗られている。
(i) 辺を共有している格子は1秒で取り替えることができる。
(ii) 白い格子を黒くするのはC2秒で出来る。
(ii) 黒い格子を白くするのはC3秒で出来る。
全て白い格子にするか、全ての黒の格子が繋がっている格子にするには最短何秒必要か。
CodeChefに毎回1問くらいあるマラソン系問題。マラソンめっちゃ苦手なので、とりあえず白と黒の少ない方を反転させるコードを提出。
Kamehameha
二次元平面に魔物のいる座標がN個与えられる。悟空はかめはめ波で一行、一列の魔物を全て消し去ることが出来る。最小何発のかめはめ波で魔物を全て消し去れるか。
全く分からなかった問題。あまりに思いつかないので「まさか枝狩りしまくればいけるのか・・・？」と2^1000に挑むも当然TLE。
なんと蟻本にほぼ同じ問題が載っていました。最小辺被覆に帰着できるらしいです。二部グラフにおいては最小辺被覆の辺数 = グラフの最大マッチングが成り立つので、最大マッチングを求めればOKです。
Rating 3892 -> 4517
今回は蟻本のおかげでレートが大きく上がりました。しかし、CodeChefのレーティングシステムはよく分からない。
