プログラミングコンテストチャレンジブック 3-7
3-7 GCJ の問題です。
- Numbers - (3+√5)^n の整数部下3桁を求める
- 一般項を求めて共役な式の一般項も求めると、一般項の整数項だけ求めればいいことがわかります
- 一般項の漸化式から行列の累乗を繰り返し二乗法で求めることで計算できる
- No Cheating - 椅子が MxN 並んだ教室で、隣と斜め前近傍の回答を覗くことができるとして最大何人が試験できるか
- グラフの最大安定集合問題 → 覗けるのは隣の列だけなので列が奇数が偶数かで二部グラフになっている
- Stock Charts - 株価チャートを線が交差しないようにしつつまとめる
- チャート同士の交差/接するものを繋いだグラフ → 彩色問題
- チャート同士が交差/接触もせず、全体を上に書けるほうに向けて有向グラフを作る
- この DAG から各ノード(チャート)を位置関係から2つに分離して二部チャートを作って最大マッチング問題に帰着させる
- Watering Plants - 植物に水をやるためのスプリンクラーの最小の半径
- ある半径で全ての植物をカバーできるかの判定をして二分探索で求める
- Number Sets - 与えられた区間の数をある数N以上の素因数を共有するグループにまとめた時の集合の数
- 素因数をたどりつつその倍数を併合していく
- Wi-Fi Towers - 電波塔のプロトコルをアップグレードするスコア(コストとメリットの差)を最大にする
3-7 は以上です。これで CHAPTER 3 も終わり、いよいよ CHAPTER 4 上級編に進みます。
