午前4時過ぎまで研究室で作業 帰宅して就寝，午前8時半起床 10時からGoogle Code JamのRound 1A ＼(＾o＾)／ ←今ここ - A : Rotate 問題：ボードを時計回りに90°回転したとき、一直線上にRまたはBがK個以上並ぶか判定する 眠い・・・でも英語読む・・・分か…

本番で解けなかった問題シリーズ．問題 長方形の上辺と下辺にそれぞれn(≦10000)個の点が打ってある 上辺の点と下辺の点すべてを1対1でランダムで結ぶ 高々50個のペアは既に線が結んである 交差する線分のペアの数の期待値は？ 解法 上辺の2点について，そこ…

本番で解けなかった問題シリーズ．問題 部屋0から部屋nが一列に並んでて，部屋はドアで区切られてる ドアは高々16種類の色で色分けされている Johnが部屋0，Gogoが部屋nにいて，交互にドアを開けながら部屋trophyを目指すゲーム ルール：John先攻で，自分の…

これで#13との因縁を清算できる・・・。というわけで今度はE問題です。問題 1番からN番までの番号を持つ穴が一列に並んでて，各穴は正整数のpower[i]をもつ。 穴iに玉を入れると，玉は列から出るまで，穴i+power[i]への移動を続けていく このルール上で，以…

本番中に解けなかった問題シリーズ。今更ですが，前回のCodeforcesより。問題 平面上にN個の赤い点とM個の青い点があって，NもMも最大500。 赤い点からなる三角形のうち，内部に青い点を含まないものの数は？ 制約として，どの3点も同一直線上にはない 解法 …

Google Code Jamに挑戦してみる。 開催を知ったのは，Qualification Roundの前日でしたが・・・。 - A : Snapper Chain 問題：長さNのビット列があって，初期状態では全ビットが0。1度のsnapでは，先頭から続く1が全て0となり，続く1つの0が1になる。Nビット…

問題 n(≦20)個のホラー映画を見る順番を決める Johnの初期HPは74。1分につき1ずつ減少し，-0.5になると眠りに落ちる。 映画iの時間scary[i]になるとHPが47回復する 眠りに着く前に見れる映画の数を最大化する順番を答える。同点なら辞書順最小を。 解法 メモ…

問題 n*mの座席から並んだ2席を予約したい 最大47席が予約済みなので，予約の仕方は何通りあるかを答える nもmも最大10億 解法 数え上げるだけの簡単なお仕事 答えがlong longになる事にだけ注意する #include <iostream> #include <vector> #include <map> #include <algorithm> using namespa</algorithm></map></vector></iostream>…

CodeforcesにICPCを控えた研究室の後輩たちが参戦。負けじと頑張ってみました。 - A. Numbers問題：数字Aを2進からA-1進で表した場合の各桁の数の和の平均を求める やるだけ。 結果は分数表示だけど，分子・分母をそれぞれ最大公約数で割れば良い。 やるだけ…

出張中だけどTopCoderは参加してみるテスト。今回はTCOの初戦。 - Easy(250) : GirlsAndBoys問題：GとBからなる文字列を"G...GB...B"または"B...BG...G"の形にソートするために必要なスワップ回数を答える 2通りやってみてスワップ回数の少ない方を返すだけ…