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通りやってみてスワップ回数の少ない方を返すだけ…

2回目のCodeforces。前回よりは良い結果となりました。 - A. Increasing Sequence問題：与えられた数列を単調増加列にするとき，1つの要素に値dを加える作業は何回必要？ 先頭から順に，増加列になるようにdを最低限加えるだけ。 さすがにWAは出さなかった。…

本番で解けなかった問題． DP中で，飛行機を使う最適な区間は…とか考えてて意味不明な事になってたものの， 飛行機でK回目のフライト中 K回のフライトを終えて陸地を移動中 という状態だけ保存してDPすれば良かった．この手の問題はまだまだ訓練が必要そう……

問題 SuperSum(0, n) = n SuperSum(k, n) = SuperSum(k-1, 1) + … + SuperSum(k-1, n) で定義されるSuperSum(k, n)の値を求める．kは50以下，nは10億以下 解いてみた kが小さい場合を考えてみると SuperSum(1, n) = n(n+1)/2 SuperSum(2, n) = n(n+1)(n+2)/6…

Div1 500 SuperSumの簡単バージョン．kもnも14以下． 無駄にメモ再帰で書いてみた． #include <iostream> using namespace std; class ShorterSuperSum{ private: int mem[15][15]; public: int calculate(int k, int n, bool call = true){ if(call) memset(mem, -1, </iostream>…

作業してたらいつの間にかSRMの時間を過ぎてたので，あとから解いてみる．問題 時間0に来たJohnがwaitTimeだけ教室で待ちwalkTime散歩するループを繰り返す 教授が時間bestTimeからworstTimeの間に来て，教授の到着からlateTime以上遅れると遅刻 Johnが遅刻…

せっかくはてなのIDを取得したので、コンテストの参加記録でもつけてみる事に。 今日は研究室の先輩からおススメされ、Codeforcesに参加してみました。 - A. Train and Peter問題：3つの文字列s, a, bに対し，sとsRがそれぞれa, bをこの順で含むか判定する …