http://code.google.com/codejam/contest/dashboard?c=639102

問題 'R', 'G', 'B', 'Y' からなる2次元正方配列を与えられる．多くとも K 個の文字だけ変更することで，縦・横・斜めに隣接する文字が同じ文字にならないようにしたい．変更後の状態で条件を満たすものはいくつあるか？

問題 N 枚のカードの表に 1〜N が重複なく，裏にも 1〜N が重複なく書かれている．このカード全てを1列に並べ替えてできる数列のパターンはいくつあるか？

問題 W×H の2次元空間において，(x, y) をスタートとしてランダムウォーク(上下左右のいずれかに 1/4 の確率で 1 だけ移動する)する．step 回移動するまでに W×H の空間からはみ出ていない確率はいくらか？

問題 スタートの数Nに対して，2人のプレイヤーが交互に数を減らしていく．減らす数は4k(1, 4, 16, 64…)で，計算結果が負の数になるのは駄目で，丁度0にしたプレイヤーが勝ちである．必勝は先攻(Taro)，後攻(Hanako)のどちらか？ 考え方

問題 'R', 'G', 'B', 'Y' で構成される文字列が与えられる．同じ文字が連続しないように一部の文字を変更したい．変更する文字数の最小数はいくつ？ 考え方

問題 N 個の座標 Pi と M 個の座標 Qi が与えられる．各 Q について「各 Pi を中心とし，Q を内側に含む円を描く時，その全ての円の内側に含まれる領域の最小面積」はいくらか？

問題 ルールを変更したライフゲームを行う．各マスについて 生きているマスについて，上と左が死んでいたらそのマスは死ぬ． 死んでいるマスについて，上と左が生きていたらそのマスは生まれる． *. → ** *@ → ** .@ → *. @. → *@ 与えられた初期状態に対し…

問題 2P チームによって行われるトーナメント戦において，「チーム i が出る試合は最大でも Mi 回見逃していい」という条件を定めている．試合の進行がどのようになっても条件を満たすために必要なチケットを買う場合，その最少額はいくらか？ 考え方

問題 以下のように数字(0〜9)を並べたものを「ダイアモンド」という． 2 8 3 7 3 3 3 8 2 2 4 1 4 8 1 3 3 2与えられたダイアモンドに対して 0 個以上の数字を追加することで，全体を上下対称かつ左右対称なダイアモンドにしたい．最小でいくつの数字を追加…

http://code.google.com/codejam/contest/dashboard?c=635102

駅駅間の所要時間が2次元配列で与えられる．(A-Zは1〜26，a-zは27〜52，#は通行不可) 目的地に達するまでに経由する駅においてスタートからの時間が13の倍数になってはいけない．(※) 0番の駅からN-1番の駅まで達するのに要する最短時間を求めよ．(※)4駅で移…

問題 3文字以上の，文字列の集合（文字列全体が同じものは無い）が与えられている．その中から重複を含めて K 個抽出して並べるパターンは(mod 1000000007で)何通りあるか． ただし，並べた順が s0, s1, …, sK-1 のとき，si の末尾３文字は si+1 の頭３文字…

問題 入力 a0 に対して ak+1＝[ak / 2] で数列を作る．その中で素数がいくつあるか求めよ． 考え方

問題 3次元空間で(0, 0, 0)と(xi, yi, zi)を結ぶ線分が与えられ，その線分を（回転させたり曲げたりするの禁止）繋ぎ合わせて途中で交わらない折れ線を作る． その折れ線の両端が最も離れるように繋げたときの両端の距離の２乗を求めよ． 考え方

問題 駅駅間の所要時間が2次元配列で与えられる．(A-Zは1〜26，a-zは27〜52，#は通行不可) 目的地に達するまでの各部分区間において所要時間が13の倍数になってはいけない．(※) 0番の駅からN-1番の駅まで達するのに要する最短時間を求めよ．(※)4駅で移動した…

問題 漸化式 ak+1＝[ak / 2] により数列を作る．その初めの D 項 a1〜aD が全て素数となる，N 以下で最大の a1 を求めよ． ただし[]はガウス記号で要するに小数点以下切り捨て． 考え方

とりあえず復習として．

Bの問題の文意が分かりにくいかもしれない．factor には因数という意味もあるので，"within a factor of C"は「C倍以内のスケールで」ということです．

基本的に提出したままのコード．解答途中に書いて消しそびれた部分も残ってる．

Problem A - Rotate の解答例 普通にやるんだったら右・下・右下・左下の4方向についてdx, dyを作ってやるのが楽だと思う．計算時間のオーダーどっちも O(N2K) だし，N,K≦50だし．方法が面白いので敢えてビット操作．以前見た情報処理学会会誌(2008年12月号…

Qualify Round も含めると5/8から行われているGoogle Code Jamの 1st Round の解答例．まぁ本サイト行けば上位層の実装が綺麗なのとかも見られるんだけど，ウェブでまんま見られると楽でしょ？解説を書くかどうかは未定だけどとりあえず本サイトの analytics…

簡易的に．まずは Qualification Round．参加者数，通過者数に制限は無い．3 問出題され，いずれかの問題について small input，large input の両方に対する出力が正しければ通過．次に Round 1．これは 3 つのサブラウンドで構成される．3 sub-round のいず…