日記
見た問題の表 - antaの競技プログラミング練習日記 解けてないものや、Editorialがないので解法がわからないものなどもあるが、77問は解法を見る見ないにかかわらず自分でコードを書いた。 Hardは新たなテクニックを知ることのできるからいいね。 とりえあず…
数を長さNで循環シフトさせて、その後の偶奇を知りたかった。 if((x - shift + N) % N % 2 == 0) ... としなければいけないところを if((x - shift) % 2 == 0) ... とかしていた。 当たり前だが、((x mod m) mod n = x mod n)は一般には成り立たない。 例え…
rep(j, a.size()) aa[a[j]] = 1; とすべきところを rep(j, a.size()) aa[j] = 1; としていた。 解法がMaximumFlowであって、そっちがバグってるんじゃないかと思っていたが単純なミスだった。解法・ライブラリ・変な所が間違ってるんじゃないかと思って確認…
見た問題の表 - antaの競技プログラミング練習日記 最近練習してなくて惨敗し続けていたのでむしゃくしゃしてやった。 さらにSRM400〜のHardをやろう。
(p - str)とかしてインデックスを求めることはそれなりにある。 しかしこれ(p - str)を(str - p)としても何の警告も出ない！(もしかしたらstrが配列の時は何かあるかも？) (node - nodes)とか紛らわしい名前を使っていると、(nodes - node)としてしまっても…
非常に雑多かつ自分用です。 TopCoderというものを知る 2011/05/23 TopCoder部のカレンダーを見ていた。 2011/05/27、 ttp://d.hatena.ne.jp/cou929_la/20091005/1254725798 を見ていた。 2011/06/22 にはTopCoderのArenaをダウンロードしていた。 Practice…
だいぶ解くことから逃げた問題もあるが、そのうち89問を一応(所見/解答見て)提出できたようだ。 一応http://d.hatena.ne.jp/anta1/20121209の時からやっているので、3ヶ月弱かかってしまったことになる。 問題数で割ったら1日1問とかそんな感じで、サボりま…
https://github.com/anta-/kawigi-tekito-
SRM、DIV1のEasy,Mediumを(抜けはあるが)200番まで見終わった (見た問題の表)。 SRM200番台のMediumの難易度と今のEasyの難易度同じくらいじゃね？というほどに、今のSRMは昔と比べて難しくなっている気がする。 これからは200番台から昇順に、Hardを解いて…
TopCoder Arena pluginのKawigiEditをいじってみた。 よくわかんないけど取りあえず動くようにはできた。 色々よくわかってない。 eclipse使ってみたけどよくわかってない。 https://github.com/anta-/kawigi-tekito- Unused Code Cleanerは使うことにした。…
http://community.topcoder.com/tc?module=Static&d1=help&d2=ratedEvent#extracoderuleには、#include以外で、300文字、30%以上だとだめだと書いてある。 これはテンプレートを使うには、特に問題自体のコードが少ない場合、非常に厳しい。 Googleで検索し…
三分探索は、ある1つ以下の点で傾きの正負が入れ替わる場合に、その点(最小値/最大値)を求めるアルゴリズム。 また、その分割を黄金比にすると多少効率がよくなるらしい。 たまに想定解でなくてもこれで解ける時があると思う。 二分探索は、ある1つ以下の点…
もう、速度の問題とかオーバーロードの問題とか無い時は、基本的にはlong longを使うようにする。 そのためにテンプレートのtypedefを変えてみた。 ついでにvectorもいれてみた 旧 typedef long long ll; typedef vector<int> vi; typedef pair<int,int> pii; typedef vect</int,int></int>…
は、「すべてのi
半群なら使えるんじゃね。 でも行列の掛け算が半群になるためには半環とか必要そうな気がするけどどうだろ？
今、bfs力が非常に足りない。問題を見てbfsだとわからないし、書けない。それを直そう。 とりあえず色々列挙してみる。 状態の管理には、queueを使う。イテレーションが少ない時には、配列でヘッドとテイルのポインタやインデクスを持つ形にしてもいい。 cur…
行列累乗がよくわからない。どうしたらその遷移行列を見つけられるのか？ とりあえず制約からヒントを得よう。 n k nはアルファベットの数など、見えにくい形のものも多い。 そもそも行列の掛け算とは、 C_ij = Σk (A_ik B_kj)というシンプルな形。 新しい状…
今やっていた、SRM 430 DIV1 Medium TwinTowns。 このrng_58さんの解答を参考に書いた下のコード。 typedef long long ll; typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pii> vpii; const int INF = 0x3f3f3f3f; const ll INFL = 0x3f3f3f3f3f3f3f3fLL; </pii></int,int></int>…
頻繁にやってしまう。警告も何も出ない。 そして意味不明なバグとなって混乱させる。 また、今回はたまたまExample通ったからFailedした。 g++に-Wshadowというオプションがあるようだ。これと-Werrorつけてやるか
※TopCoderの環境の場合。C++0xだとlonglongのコンストラクタがあるらしい bitsetで気軽に2進表示とかよくやる。 でもbitsetはintしか対応してない？らしく、long longを使うと何の警告も無しに切り詰められちゃう。 さらに悪いことに、gccのバージョンによっ…
vpii v; //... v.pb(mp(hypot(xi - xj, yi - yj), j)); 的なことをやってしまった。 double直接でなく、pairのvectorというのがわかりにくくしていたか。 警告は出てたが無視してしまった。 警告は無視するな！
はい。 coqとかやってる。 やらないとしょうがないでしょ
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として色々考えられる グラフにしよう
データ構造はまずはそれを使う！という問題や、それの頻出の使いかたの問題をやるべきか。 SRMではそういう問題はあまり出ないと思うから、他のところか。 そして使える時に使えるようにならなければいけない。 例えばRangeMinimumQueryはDPの加速に使えるが…
モチベ重要 回答に感動すること・さらには自分の(回答・アイデア)に感動することは非常にモチベになる
ステップに分け、それぞれのステップごとを関数にする。 逆関数などを求めたかったら、それぞれについて考え、それを合成する
酷いミス。確認しろ 本当に
タイトルは、SRMの場合"SRM 123 DIV1 Medium ProblemName"のように書く 一番上に、元の問題文が読めるページへのリンクを置く "問題"小見出しに、問題の概要を書く "回答"小見出しに、自分の考えたこと・考え方を書く "コメント"小見出しに、雑多な、反省点…
