yukicoder No.7 プライムナンバーゲーム / No.11 カードマッチ / No.43 野球の試合
☆２でも引っかかるところがあるのでメモ記事．
yukicoder No.7 プライムナンバーゲーム
URL
回りくどいsubmission
http://yukicoder.me/submissions/147714
アイデア
動的計画法だが，貪欲っぽいイメージ．
簡単なインスタンスを挙げる．
減算後{0,1}になったら負けになるので，例えば，n=2の時は先手必勝ではない．
さらに，n=5=2+3の時，3を減算すればn=2の先手必勝でない状態に遷移できることから，n=5の時は先手必勝である．
LayCurseさんの解説を見たので，そちらが詳しいです．
yukicoder No.11 カードマッチ
URL
カンニングしたsubmission
http://yukicoder.me/submissions/147794
アイデア
包除原理らしい．
数式は解説ページに書かれているとおりだが，この数式はどうやって導出したのか？
分かりやすくするため，カードをスート毎にランク順に並べた七並べのようなものをイメージする．
例えば，標準入力から次が与えられたとすると
6 6 5 1 1 5 2 1 3 4 3 3 5
このような行列になる．
表の行同士や列同士を入れ替えても結果は何も変わらないはずなので，登場しなかったスートやランクを右下に寄せておく．
ところで，求めたかったカードの個数とは，緑色の領域の個数なので，である．
残りはyukcoderの解説通り．
感想
初期の方針では"今どの行・列が潰れているか"，"何行・何列潰れているか"とか色々捻ってました．
nantekottai
yukicoder No.43 野球の試合
URL
submission
http://yukicoder.me/submissions/147866
感想
順位は勝ち数が多い順で１位から決定していく。 勝ち数が同じであれば同じ順位のチームが複数のこともある。
コードが通らないと思ったら，ここを読み飛ばしていたんですねぇ．
この部分を説明したサンプルケースも無く，気づくのに時間がかかってしまった．
最終スコアがわかっていて順位を求めたい時， 『0番目のチームのスコアを控えておき，スコア配列を昇順にソート・重複除去して，控えたスコアを探索する』が簡単ですね．
