buyoh.hateblo.jp

競プロ参加記録.開設したばかりなので暫くお待ちください.

yukicoder No.7 プライムナンバーゲーム / No.11 カードマッチ / No.43 野球の試合

☆2でも引っかかるところがあるのでメモ記事.


yukicoder No.7 プライムナンバーゲーム

URL

No.7 プライムナンバーゲーム - yukicoder

回りくどいsubmission

http://yukicoder.me/submissions/147714

イデア

動的計画法だが,貪欲っぽいイメージ.

簡単なインスタンスを挙げる.

減算後{0,1}になったら負けになるので,例えば,n=2の時は先手必勝ではない.

さらに,n=5=2+3の時,3を減算すればn=2の先手必勝でない状態に遷移できることから,n=5の時は先手必勝である.

LayCurseさんの解説を見たので,そちらが詳しいです.


yukicoder No.11 カードマッチ

URL

No.11 カードマッチ - yukicoder

カンニングしたsubmission

http://yukicoder.me/submissions/147794

イデア

包除原理らしい.

数式は解説ページに書かれているとおりだが,この数式はどうやって導出したのか?

分かりやすくするため,カードをスート毎にランク順に並べた七並べのようなものをイメージする.

例えば,標準入力から次が与えられたとすると

6
6
5
1 1
5 2
1 3
4 3
3 5

このような行列になる.

f:id:m_buyoh:20170205092555p:plain

表の行同士や列同士を入れ替えても結果は何も変わらないはずなので,登場しなかったスートやランクを右下に寄せておく.

f:id:m_buyoh:20170205092554p:plain

ところで,求めたかったカードの個数とは,緑色の領域の個数なので,{全体-右下の長方形-手札の数}である.

残りはyukcoderの解説通り.

感想

初期の方針では"今どの行・列が潰れているか","何行・何列潰れているか"とか色々捻ってました.

nantekottai


yukicoder No.43 野球の試合

URL

No.43 野球の試合 - yukicoder

submission

http://yukicoder.me/submissions/147866

感想

順位は勝ち数が多い順で1位から決定していく。 勝ち数が同じであれば同じ順位のチームが複数のこともある。

コードが通らないと思ったら,ここを読み飛ばしていたんですねぇ.

この部分を説明したサンプルケースも無く,気づくのに時間がかかってしまった.

最終スコアがわかっていて順位を求めたい時, 『0番目のチームのスコアを控えておき,スコア配列を昇順にソート・重複除去して,控えたスコアを探索する』が簡単ですね.