半群なら使えるんじゃね。 でも行列の掛け算が半群になるためには半環とか必要そうな気がするけどどうだろ？

今、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>…

※あくまでメモ・信頼性は全くない N文字のK種類の文字からなる文字列strで、「i番目以降に文字cが出てくる最初のインデックスを各i,cについて全て求める」は後ろからやるとO(NK) int dp[K][N+1]; for(int c = 0; c < K; c ++) { dp[c][N] = INF; for(int i =…

頻繁にやってしまう。警告も何も出ない。 そして意味不明なバグとなって混乱させる。 また、今回はたまたまExample通ったからFailedした。 g++に-Wshadowというオプションがあるようだ。これと-Werrorつけてやるか

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

http://codeforces.com/contest/222 本番 A ふつう B 少し複雑に書いてしまった C 問題の意味がわからない D 最後までやり続けたけどできなかった Hack Aで単純なミスをHack。+100 System Testing 2つは通った。 B解くのは速かったんだなー CをHackしまくっ…

※TopCoderの環境の場合。C++0xだとlonglongのコンストラクタがあるらしい bitsetで気軽に2進表示とかよくやる。 でもbitsetはintしか対応してない？らしく、long longを使うと何の警告も無しに切り詰められちゃう。 さらに悪いことに、gccのバージョンによっ…

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)…

vpii v; //... v.pb(mp(hypot(xi - xj, yi - yj), j)); 的なことをやってしまった。 double直接でなく、pairのvectorというのがわかりにくくしていたか。 警告は出てたが無視してしまった。 警告は無視するな！

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

250Challengeされて0ptで死んだ！ コメント Medium、シミュしたら法則性が。しかし時間切れ。もっと早くシミュしてみるべき Easy落とすのはひどい Challenge、明らかに間違ってる回答があったのに、そのケースを考えたのに、それ用のケースを作ってなかった…

http://apps.topcoder.com/stat?c=problem_statement&pm=11463&rd=14439 問題 10進法表現に4と7のみしか現れない数をlucky numberと呼ぶ。 今、positive上に[a,b] (1区間がある。 初めに、Johnは[a,b]に含まれ、長さがjLen(1区間[ja,jb]を選ぶ。 次に、Brus…

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