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

はい。 coqとかやってる。 やらないとしょうがないでしょ

http://tenka1-2012-qualc.contest.atcoder.jp/assignments Coding まずはA やるだけ…だけど… なんか速く解きたくて、入力欄にそのまま書いて一回も実行せずに提出したらRE。もういっかいは"より小さい"を"未満"だと勘違いしてWAで-2 うーん…これがなければ……

Coding 250 最初なんか方程式を解こうとしてた。 なんかpからb,dの数が求まるという自明なことになんか気づいてなかった。 だいぶ時間がたって焦ったが、まあ普通に全探索書いた。 205.41pt 500 足し算だけだし、使ったか使ってないかを保存しとけばいいんじ…

2012/08/21 22:30 から"SRM521 DIV1"で模擬練習 まとめ Challengeケースは柔軟に、単にTLEとか場合分け漏れとかじゃなくて、思考をしてみて考える return typeのlong longに惑わされるな。考えてみたら、値は小さいことがある 早解き次第で順位が150位くらい…

本番風に模擬練習してみることにした Coding Phase 75分間 +00:00〜+01:15 問題を初めて開き、Submitする。 他人の回答は見ず、Practice System Testも行わない。 時間いっぱいまで考え続ける メモ Intermission 5分間 +01:15〜+01:20 この時間になったらも…

http://apps.topcoder.com/stat?c=problem_statement&pm=11566&rd=14547 コメント Editorial http://apps.topcoder.com/wiki/display/tc/SRM+522 を見て、感動した。 これはDIV2MediumでもRowAndManyCoinshttp://apps.topcoder.com/stat?c=problem_statement…

0完-1 … WAで-1はしちゃいけないかなー 結果 Rank: 338/349 Rate: 1703→1646 コメント 今回答を見ると、なんで解けないかなーと。 Aはunion-findして数えるだけらしい Bは逆からやる。 逆からやるのは定石だろう… まあ次がんばろう。練習しないと

http://tenka1-2012-qualb.contest.atcoder.jp/ A 全探索するだけ、なのに問題読み間違えて1WA B これも問題読まないうちに、ステートマシンでやろうとしたが、合わなくて問題読んだら全然違った。 単語列であるかの判定をしなきゃいけないのね。 C なんかい…

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)が同じ…

本番 A シミュもしてみたりした。 まあやるだけなんだろうけど、 無駄にバグらせたりして結構時間がかかってしまった。 14:43 B 結構考えて、なんとなく方針が立つ。 でも上下とかループ構造とかよくわかってなくて、何度も書き換えたりしてるうちにコピペミ…

TopCoder 灰色 #999 0-899 <span style="font-weight: bold; color: #999">0-899</span> 緑 #00A900 900-1199 <span style="font-weight: bold; color: #00A900">900-1199</span> 青 #66F 1200-1499 <span style="font-weight: bold; color: #66F">1200-1499</span> 黄色 #DC0 1500-2199

Method signature: long long theMax(long long R, long long G, long long B, int N) だったとしても long long theMax(long long R, long long G, long long B, long long N) { ... } とかに変えても、通っちゃうらしい

Coding Easy 時間かかりすぎ。r,cの説明がわからなかった。n Medium ぱっと見簡単そう。 でもNの意味がわからない。何を数えるのかが読めない。 そのまま書けず Hard まずシミュしてみる 最初シミュが間違ってて変な戦略できて、これ簡単じゃんとか思ってた…

間にスペースや"$"などを入れること

偶数の素数が1つあって、それは2。 いろいろな定理で"奇素数"とか"n以上"とかで回避されてることがある。 場合分けするように注意

DPは最終的な評価のみが要素になるわけじゃない。 最小化したかったりしたいものが有ればそれがDPになる。 逆に、最終的な評価などをインデックスにできる。 最後には全部とかを舐めて、Validであるインデックスのmaxを取ったりすれば良い SRM 451 DIV1 Medi…

練習でも、 問題を読む 制約を見る 〜10: O(n!) 15〜20: O(2^n) 30〜40: O(2^(n/2)) 50: O(n^4)程度, DP, グラフ 〜10^14: O(√n) 考えて 適当に分割してみる サブ問題に再帰的に分割できる？ 小さな場合を制約式のようなものに展開する 一旦考えなおす さら…

不等式の場合、それは順序関係で、 順序関係で有向グラフにするという考え方はありだ。 循環があるかの判定(dfs/bfsでおｋ)で矛盾があるかが判定できる 矛盾がない場合それはDAGということなので、DAGとして色々考えられる グラフにしよう

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へ向かいた…

DAGの最小パス被覆 パス被覆(path cover)とは、あるグラフのパスの集合であって、そのグラフの全ての点がそのパスに含まれているものをいう。 最小パス被覆とは、パス被覆の中で、パスの数が最小のものをいう。 DAGの最小パス被覆は二部グラフの最大マッチン…

頂点被覆(vertex cover)とは、あるグラフの点のサブセットであって、全ての辺がその点に接しているものをいう。 最小点被覆とは、点被覆の大きさをできるだけ少なくするもので、一般の場合では(決定問題に"グラフCに大きさk以下の頂点被覆があるか"として変…

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分になる程度まで使…