プログラミングコンテストチャレンジブック 4-5 その1

4-5 「GCJ の問題に挑戦してみよう(2)」からです。

• Mine Layer - マインスイーパのように8近傍の爆弾の数が示されていた時に真ん中の段に含まれる爆弾の数
  • 1次元で考えてみると、奇数番目の和と偶数番目の和の差を取ることで真ん中のマスの数がわかる
  • まず各段について1次元と同様に中央のマスの上下に含まれる爆弾の数を計算して、今度は縦方向に同様の計算をする
    • 各段の計算をする時に上下のマスの影響があるから、と思ってしまうけどそのままでいい
• Year of More Code Jam - プログラミングコンテストのラウンドが1日にS個あると S^2 の幸福度になる少女のN日間の幸福度の和の期待値を求める
  • 普通に式変形。各トーナメントの開催日の確率分布で独立した式にする
• Football Team - N 人の選手が近い人とシャツの色が同じにならないように並ばせる。ただし Y 座標も与えられていてこれも「近い」かどうかの判定に関係する
  • まず選手間の関係(「近い」かどうか)をグラフで表現して彩色問題に
  • 平面性 → 4色で塗り分け可能
  • 内面が全て三角形 → 3色で塗り分け可能？
    • 辺を共有する三角形の面からなる部分グラフ毎に判定する