CADDi for Beginners 反省

12/22にあったCADDibに参加した

A. 12/22

4桁の数字が与えられるので, そこに含まれる"2"の個数を求める

count関数を使ってあげると短く書ける

ある縦H, 横Wを満たすような合金の板となるようにカットできるか？という問題

本来なら回転も考慮する必要があるが, そのような問題設定はないので

与えられた板がH以上かつW以上を数えればよい

C. Product and GCD

あるN個の数字 $a_1 , a_2, ..., a_N$ の積が $P$ となるとき, $a_1 , a_2, ..., a_N$ の最大公約数のうちもっとも大きい値を出力する.

ここである最大公約数を $d$ としておく

・考えたこと

1. $a_1 , a_2, ..., a_N$ は共通の最大公約数 $d$ を持つ

2. 1より $P≧d^N$ が成り立つ

3. $P$ を素因数分解したとき, ある素数 $p$ が $N$ 個以上あれば, $d$ のうちの一つとなる

4. 素因数分解は $O(sqrt(P))$ で行える

以上の考え方では $N=1$ がコーナーケースになるので注意する

ここで1WAしてしまった.

D. Harlequin

問題文:

プレイヤーが二人いて, あるゲームを行う.

$N$ 本のリンゴの木が与えられ, 各木にには $a_i$ 個のリンゴがなっている. プレイヤーはリンゴを一個だけ取るという操作を各木に対して行うか行わないかを選択できる. 最後のリンゴを取ったプレイヤーが勝利となる.

与えれた入力に対しどちらのプレイヤーが勝利するかを出力する.

(firstが先手, secondが後手とする)

・考えたこと

1. $N=1$ のとき, $a_1$ が奇数ならfirstが勝つ, 一方で偶数ならsecondが勝つ

2. sample2を見るとすべての木が偶数ならsecondが勝っている

3. 上記の二つの条件から「 $a_1, a_2, ... , a_N$ がすべて偶数ならsecondが勝つ」と仮定する

4. 上の仮定を保障してくれそうな事実を考える

$a_1, a_2, ... , a_N$ がすべて偶数のとき, firstが奇数個にしたリンゴと同じ木からリンゴを取ることで, secondのターン終了時に「 $a_1, a_2, ... , a_N$ がすべて偶数」という状況を維持できる

逆に, 初期の状態から奇数本の木が含まれていると, firstのターン終了時に奇数個の木を残すことができる. firstは奇数個のリンゴの木を1本でも残すことができれば勝てるため,

このゲームの勝利判定基準として, 「 $a_1, a_2, ... , a_N$ がすべて偶数か」を考慮すればよい.

(一部誤っているかもしれません, 申し訳ないです)

・全体の結果

rank: 25th

performance: 1600

今回の問題セットは得意だったので, 逆にアルゴリズム使って実装する系が苦手なんだなーとなってしまった.

賞金ほしかったですね

h3mky0's blog