DIV1なのでNon rated。 Cで、二分探索ミスった。 見つからないかを確認したい時は、最後にlをチェックするのがいい。 Eは最後に最小費用流っぽいなと思えた。が、時間切れ。 まあ今回はいいけども、本番ではしっかりしたいね。 Spaghetti Source さんの最小…

Coding A 最初k以上ならおｋと勘違いして完全グラフでよくね？とかして1WAする。 グラフを作るのが、どうやったらいいんだ…と普通にわからない。 とりあえず適当にやればいいだろーとランダムに辺を追加/削除するのを書いてみる。 そのコードは動かなかった…

三分探索は、ある1つ以下の点で傾きの正負が入れ替わる場合に、その点(最小値/最大値)を求めるアルゴリズム。 また、その分割を黄金比にすると多少効率がよくなるらしい。 たまに想定解でなくてもこれで解ける時があると思う。 二分探索は、ある1つ以下の点…

SRM 360 DIV1 Easy のこのhttp://community.topcoder.com/stat?c=problem_statement&pm=7875&rd=10772問題で。 想定解ではないらしいが、何回かSystem Testをやっても通る。 コードのメイン部分 #define N 1000000 int t[55][55]; struct SumOfSelectedCells…

DIV1での挑戦となった。部屋はふつう。 Easyはふつう解いてあわよくばMediumも…と思っていた Coding 250 やるだけ 500 DP？と思った。 適当に考えると、 rec(i, j, b) = i番目のdigitを最終的にj番目とみたときに、bが2ならlowerより大きい最小、1ならlower…

DIV2とかやだー Coding 255 Brute Forceするだけ 555 遅い。瞬殺すべき 5^nは埋め込む。状態数そんな多くないしメモ化しないでもsubstrしても十分間に合う 955 うーん…色々考えたけど時間切れ Challenge 適当に考えたケースとして、Easyでrow,colごとにgreed…

http://apps.topcoder.com/stat?c=problem_statement&pm=10782&rd=14245 解答 この中の時間を基準に考えたら、時間の分岐が木になることがわかった。分岐がタイムトラベルポイントで、葉が訪れる街。 その木を左右に分割して探索していく。 この解法はO(n^5)…

http://apps.topcoder.com/stat?c=problem_statement&pm=11154&rd=14435 問題 都市がいくつか(N 都市が1つになるまで、それらの任意の2つを選び合併、 新しい都市の人口は2つの都市の和で、新しい都市の名前は元の人口が多かった方、ただし同数の場合はどち…

http://codeforces.com/contest/221 本番 A やるだけ。 少し試せば法則性が分かる。 最初、関数の値を返す問題と思い込んで、その値を求めて1WAしてしまった。 B やるだけ。 約数を試すだけ。 なんかi*iがオーバーフローするとか勘違いしてResubmitしてしま…

http://apps.topcoder.com/stat?c=problem_statement&pm=11484&rd=14536 問題 0〜511の数値が書かれたカードが何枚か(1 値を記録できるメモリがあって、最初は0である。 プレイヤー2人がいて、交互にカードの中から一枚選び、そのカードの数値とメモリの値を…

http://k2pc-hard.contest.atcoder.jp/tasks/k2pc001_h3 回答 greedyに、大きい数のsqrtの道を辿ってく。 nが平方数じゃないなら-1、n コメント 今見ると不要な場合分けがあるようだ。 この問題のwriterいわく、違う方法(根本的な解き方は同じように見えるが…

http://k2pc-hard.contest.atcoder.jp/tasks/k2pc001_h2 問題 深さK(1 深さがiで左からj番目のノードのことを(i, j)と表し、それがN(0 この時、この木のノードのうち、与えられた座標のうちどれも通らないでルートノードにたどり着けるノードの数を数えろ。 …

http://k2pc-hard.contest.atcoder.jp/tasks/k2pc001_h1 問題 ab = concatMap (\i-> map (\n-> (i - n, n)) [1..i-1]) [1..] a = map fst ab b = map snd ab という数列がある。 入力i j (1 回答 まず、任意のi番目のa,bを求めたい。 これには、(a+b)が同じ…

http://apps.topcoder.com/stat?c=problem_statement&pm=11704&rd=14729 問題 命令列が与えられる "right X", "left X" (X: nat, X 右・左にX度回転する。 "forward X", "backward X" (X: nat, 1 現在の方向に対して前・後にX進む。これらの命令を入れ替える…

http://apps.topcoder.com/stat?c=problem_statement&pm=11808&rd=14729 問題 整数座標が何個か与えられる(1(0,0) /\ (i <> j -> (X_i, Y_i) <> (X_j, Y_j)))。 上下左右の整数座標にのみ進むことが出来る。 このとき、点(0,0)から出発し、与えられた座標を…

http://apps.topcoder.com/stat?c=problem_statement&pm=11805&rd=14731 追記: (コメント/Editorialより) 想定解(とこの解答)は間違っているらしい Editorial読んでたのに、そのことに気づかない程度の英語力！ 問題 N(1 i番目の兵士は砦0から砦iへ向かいた…

http://apps.topcoder.com/stat?c=problem_statement&pm=11855&rd=14731 回答 全列挙し、そのlowerとuppperを取り、それを[9001,∞]の範囲にする。 そのあとそれらをlowerでソートすると次のようになる。 この時、求めたいのは被覆している長さの和である。 …

http://codeforces.com/problemset/problem/216/D 回答 数えるのに、全てを試すとO(n^2)で駄目なので、二分探索する。 コメント lower_boundやupper_bound関数できれいになると思う コード

http://codeforces.com/problemset/problem/216/C 問題 従業員はn(2 つまり働いている日は、x日目に雇われたとして、 {d | ((x-1) + (d-1)) % (n+m) < n}である。 この時、常に店に従業員がk(1 ただし、店には鍵がかかっており、鍵は一つしか無く、従業員の…

本番 まずAを A なんとなーく適当に数えてみる。実際間違ってるかも なんとなくDへ D ぱっと見よくわからんかったけど、よく見たら簡単そうだった。 しかしlower_boundとかの関数忘れてて二分探索の実装がなかなかできなくて時間を残り55分になる程度まで使…

http://apps.topcoder.com/stat?c=problem_statement&pm=11888&rd=14733 コメント 他の人の回答を見た。 レート上から見ていったのだが、その中でKankuro氏の回答がシンプルでわかり易かった。 接頭・接尾だけを保存、とすると複雑になりがちだが、単に、「…

http://apps.topcoder.com/stat?c=problem_statement&pm=10516&rd=13900 問題 重み付き有向グラフ(V 今、点0に蟻が居る。 蟻は1秒間にstepsPerSecond( 最大timeLimit( 蟻は最終的に点1に行きたい。 ここで、蟻が通った辺の重みの合計を最大化したい。 もし点…

http://community.topcoder.com/stat?c=problem_statement&pm=10054&rd=13510 回答 後ろから見てって、undoがあったらそのtimeまでiをデクリメントする コード

http://community.topcoder.com/stat?c=problem_statement&pm=9958&rd=13506 回答 他の人の回答を見た。 まず、持ってるものは売ってから買っても同じなので、まず全部売ってから考える。 ナップザック問題にできて、値の範囲的にDPはできないので指数時間が…

http://community.topcoder.com/stat?c=problem_statement&pm=6415&rd=9986 回答 一度動かした奴をもう一度動かす意味は無い。 だからそれぞれは前に動かす,後ろに動かす,動かさないの3種類にわれるが、小さいものを前に、大きいものを後ろに動かしたほうが…

http://community.topcoder.com/stat?c=problem_statement&pm=12138 回答 典型的なDP dp[最初の色][前の色][Aの数][Bの数][Cの数]で コメント 本番で通せよ。これは解ける。 本番はもっと冷静になるべき。 本番では状態がわからなかった。種類数が少ないのは…

http://apps.topcoder.com/stat?c=problem_statement&pm=10190&rd=13904 回答 何番目か、1にしたかどうか、でDP コメント メモ化を忘れるミスが酷かった。 コード

Problem Statement for SalesmansDilemma 問題 重み付き(負の重みもある)有向グラフのある点からある点へ向かい、その途中で通った辺の重みの総和を最小化したい。 ただし到達できない場合は"IMPOSSIBLE"を返し、無限に小さくなる時は"ENDLESS PROFIT"を返せ…

問題 最初の数値をXとした時、 最下位ビットが1なら subtract 1 最下位ビットが0なら (`shiftR` 1) とした時、[A,B]の範囲のXの中で途中にKが出てくる数の数を答えよ 回答 他の人の回答を見た。また、ほとんどその人の写し。 [A,B]という範囲を考えるのには…

C: 敵対的引用 - 天下一プログラマーコンテスト2012 予選A | AtCoder 問題 有向グラフA(V ある一ノードpとbool配列x[N](N pから出発してi番目(i x[i]がtrueならAを進むことができ、 x[i]がfalseならBを進むことができる。 この時、到達可能なノードの数を答…