すごく久しぶりに出てみた。 - 250. AliceGame 問題：{1, 3, ..., 2*n-1} の和がx+yになるようなnを選び、その部分和でxが作れるならそのときの要素数の最小値を求める問題。できなかったら-1を返す。 とりあえず Σ(2*i-1) を求めるぜ！って思ってたら n^2 …

この記事を書いてる時に1Bの記事が事故死してしまった…。まぁいいか。 - 250. SixteenBricks 問題：1*1*h[i]の角柱を4×4のグリッドに並べた時の最大表面積を求める問題。 greedyかなぁと思ったけどsample2が倒せなかった。 安全にbitDPとか出来ないかなと思…

今さらながら一応書いておくことに。 - 250. FruitTrees 問題：りんごをx間隔、キウイをy間隔、ぶどうをz間隔で植えるとき、異なるフルーツの最小距離の最大値は？ 各パラメータが2000以内 りんごの位置を固定し、キウイの位置とぶどうの位置の全探索を考え…

飲み会開けの酔拳チャレンジ。 - 300. TheLargestString 問題：同じ長さの文字列s, tから同じ位置の文字を抽出したものを繋げてできる辞書順最大の文字列は？ 文字列長を固定すれば、sからは辞書順が最大になるように選ぶのが最善 で、sからとった文字列が同…

時が流れるのは速いなあと(1個前の記事を見て)思いつつ。 - 250. NewArenaPassword 問題：与えられた文字列を、先頭からK文字とった文字列と、後ろからK文字とった文字列が一致するように書き換えたい。最小で何文字変えれば良いか。 文字列長nに対してn-K文…

2ヶ月ぶりくらいに参加してみました。 - 275. KingXNewCurrency 問題：A円とB円の組み合わせで払えるすべての金額を、X円とY円の組み合わせで払えるようにしたい。A, B, Xが与えられるとき、Yのとり方は何通り? ふおお…なんだか数学ゲーっぽいぞ…。 まずは、…

翌朝も仕事だったけど構わず参加した今年最後のSRM。 - 250. Cut 問題：決められた切断回数以内で10cmのうなぎをなるべくたくさん作る 最大で長さ10mのうなぎ…ごくり。 とりあえず、長さが10の倍数のうなぎはお得 (length/10-1)回の切断で、10cmのうなぎがle…

旅路の新幹線の中から更新。たまにはこんな日も良いですよね。 - 250. MagicDiamonds 問題：与えられた自然数nを、最小何個の合成数の和で表せるか求める 合成数なら分解しなくて良いので答えは1 素数だったら、1+(n-1) あたりに分解しておけば2個で表せるの…

良いするめセットでした。(何を言ってるんだという感じですが) - 250. SRMCodingPhase 問題：SRMの3問それぞれを解くのにかかる時間と、解く時間をluck分縮める権利が与えられるので、得られる最大の点数を求める 点数高い問題から貪欲にluckを使う感じ？ 解…

ちょっとした辱めを受けたSRM。 - 250. YetAnotherIncredibleMachinet 問題：落下してくるボールが一個もぶつからないような板の配置は何通り? ボールの落下を全て受け止める問題だと思い込んで、しばらく悶絶した 冷静になって問題文を読み直したら簡単だっ…

社会人になって初めて平日深夜SRMへと突撃してみた、記念すべき512回目のSRM。 - 256. MysteriousRestaurant 問題：曜日ごとに特定のメニューを注文しなきゃいけないレストランで、最大で何日めまで食事できるか求める問題 i日目まで食事してみると決め打ち…

最近のTopCoderは鬱展開多めです。 - 250. Zoo 問題：ウサギとネコが自分より背の高い同じ動物が何匹いるか回答した状況から、答えに対するウサギ・ネコの割り当てが何通りあるか答える 同じ数字の回答が2匹づついれば、その2匹には割り当ての自由度がある 0…

前夜は夜更かししてE3の中継を見てたので、だいぶ眠い感じで参戦。 - 300. LuckyRemainder 問題：与えられた数字の空でない全ての部分列の和を9で割った余りを求める 9で割った余りとか桁ごとに使う回数の和を取るだけじゃないかｗｗｗ と思ったものの、使う…

社会人としてのSRM初陣。 - 300. RectangleArea 問題：n×mに分割された長方形の各部分の面積をなるべく少ない回数聞いて、全体の面積を当てるクイズ。 300か。これ無理じゃね…。 しかし、思考停止したら終了なので何か考えてみる i番目の縦幅をR(i), j番目の…

赤い人として挑んだ最初のSRM。 - 250. FoxPlayingGame 問題：0に操作A(scoreAを足す)nA回と操作B(scoreBをかける)nB回を好きな順で行ってできる最大の数を求める。 タイトルだけ見て、日本人writerなんだろうなぁ…とか思う。 まぁ、操作Aと操作Bの残り回数…

記念&追悼SRMでした。 - 250. MafiaGame 問題：N人がいて互いに投票しあう。まず投票する人を決めているM人が投票をし、次に残りの人が得票数が最も少ない人から1人をランダムに選び投票する。最多票が同率のときは残り1人になるまで決選投票を行うとき、最…

信頼と実績の問題クオリティーで楽しめた回でした。 - 250. BunnyComputer 問題：n個の数字の配列から，K個間隔の2個のペアを取っていく。とれる数字の和の最大値を求める う…うさぎだと…。 とりあえずペアを取る操作で関係するのはK個離れた数字どうしなの…

密かにバースデーSRMだったので、妙な緊張感と戦う羽目に。 - 250. TheCoffeeTimeDivOne 問題：乗客のお茶orコーヒーのオーダーを全て消化するための最短時間を求める。 貪欲に後ろから配れば良いんだろうなぁ…と思いつつ，貪欲でやる勇気が出ない。 貪欲に…

なぜかRound3を通過してしまったので、ｶﾞｸﾌﾞﾙしながら参加してきました。 - 250. BankLottery 問題：n人がaccountBalance[i]ドルずつ銀行にお金を預けてて、週に一度、誰か1人を(預金額/全員の総預金額)の確率で選んでjackpotドル振り込む。自分が0番の人だ…

数時間後に演奏会を控えていますが、Round3に出ればTシャツをくれるというので参加してきました。 - 250. SieveOfEratosthenes 問題：エラトステネスのふるいで2からmaxNumまでの数を処理したときに、最後にふるわれる数は？ maxNumは4以上20億以下。素直に…

研究室の生き残りが自分だけとなってしまって若干心細いRound 2。 - 250. SnowPlow 問題：N個のノードからなる有向グラフがあって，i->jの枝がK本あればj->iの枝もK本ある。ノード0からスタートしてすべての枝を通るための最小コストは？通れない枝が存在す…

GoogleCodeJamが落ち着いたところで、今度はTopCoder Open。 ちょっと眠かったので寝オチだけが心配でしたが…。 - 250. EqualizeStrings 問題：文字列s, tそれぞれに，「1文字を選びアルファベット順で1つ進める or 戻す」という操作を加え、sとtを同じ文字…

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

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

問題 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>…

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

本番で解けなかった問題． 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>…