結果 ---(+0/-0) 0pts 353th 1768->1660 (-108) 大敗北 275 よくわからない…総票数kと仮定すると得票数vは k*(p[i]-0.5) 500 Greedyにやっていけばよい。こっちのほうが簡単じゃないか！訴訟！ 感想 人権less

結果 ooo--(+0/-0)2184pts 135th Rate:1501->1588 A 意外とめんどい。とりあえず10^9以下の三角数を列挙してsetに突っ込んで それらに対して入力からある三角数を引いたものが集合内にあるかどうかでやった。初め全列挙とかしてたら意外と時間かかった。 B …

概要 去年のGoogleDeveloperDayの15パズルもどきのときに、状態を管理するmapの要素数が多いのでC++11で追加されたunordered_mapにするとinsertもfindも早くなるんでね、と思って使ってみたのを思い出したので、ざっとどのくらいか試してみた。 やったこと 1…

結果 ooo- 20th A,B やるだけ C あるセルにいるときのパラメータとして、「それまでの経路の明るさ」と「時間」があるが、 経路の明るさは移動するごとに変化しないor減少するため、時間については考えずにセルごとの 経路の明るさの最大値だけBFSでメモって…

結果 A-small/large B-small 20pts,1225thで敗退。もうちょいA早く通してC-smallだけでも通せばよかったなー。 A 問題文が割と読みにくかった。 要はツルを掴んでターザンして通り過ぎたor到達したツルに乗り換えることができる。 ツルが短すぎて掴めないと…

結果 o--(+0/-0) 232.13pts(192nd) 1705->1768(+63) またもやhighest更新です。Petrとはじめて同部屋でした。 250 各bitごとに調べていった。 下から[a,b]のxorを取ったときの下からkbit(0-indexed)目は (([0,b]の下からkbit目が1の個数)-([0,a-1]の下からkb…

ソース http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=404152 方針 制約が大きい…JavaならBigIntegerを使えばよいかもしれない。 2^32より大きいmodを使うとlong longでもoverflowする可能性があるので 10^5((10^5)^2 >= 10^9.6≒2^32)程度のmodを素…

蟻本他を参考にした。 modの逆元 与えられたa,b,mから ax≡b(mod m) を満たすxを求めたいとする。 このとき ay≡1(mod m) なるyが求まれば y*ax≡y*b(mod m) x≡y*b(mod m)(∵ay≡1)としてxを求めることができる。 ay≡1(mod m)⇔∃k(ay=1+km)であるから変形して ay-m…

はじめに 前置インクリメントと後置インクリメント、どちらでもいい状況なら後者、みたいなのを たまに見かけるし、理屈は解るけど実際どうなるのか気になったのでちょっと試してみた。 (結構適当な計測です、指摘があればしていただけると嬉しいです) intの…

結果 o--(+0/-0) 184.32pts 444th 1671->1705(+34)Highest更新、1700台にのりました。 300-550-900とか0完フラグだろ…と思ったものの 300が解けてよかった。 300 場合分けでガンガン。 0がないときは明らか、 0がk個あるとするとき、 k箇所に1本ずつ当てたと…

結果 不参加でした。 250 xy平面上(0 a->b->c->aの道のり(移動は軸に並行のみ)がminT以上maxT以下になる a,b,cの置き方の総数を求めよ。という問題。a,b,cの道のりはa,b,cを内包(辺上を含む)する最小の長方形の周の長さに等しい。 ┌--A--┐ │ | B | └-----Cイ…

結果 oo--- (+0/-0) 1290pts 357th 1536->1501 敗戦…勝ちがTopcoderに、負けがCodeforcesに集中している気がする。 A 全探索やるだけ、とかいって4000^3投げる->TLE ですよねーといいつつ4000^2投げる->WA n-(a*i+b*j)>0のチェックを入れてなかった… >pretes…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2332 ソース http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=398012 方針 0のマスからはサイコロを振れるので+1〜+6のノードへedgeを張り、 それ以外は書いてある通りにedgeを張る。…

結果 A(small/large) C(small) 565th 40pts 1:36:15なんとか通過したよー。 Round2通過は無理だろうけど精一杯がんばります。 A Diamond Inheritance 全ての点からDFSして既にvisitedの点に当たったらYes、そうでなければNo。 C Box Factory ぱっと見でLCSっ…

ソース http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=391002 方針 2 0 >10^9で8秒なら間に合うかもしれない…? しかし、Nがある値以上ならば必ず到達でき、それより小さければ到達できないので 二分探索をすることができる。 >O(WHlogN)で充分間に…

ソース http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=390527 方針 dp[i] := (ビット表記で)iまでクリアしたときの所要時間の最小値とすればよい。 TSPと違うのは「いまどこにいるか」は関係ないので1次元配列で済む。 あとは再帰内で 次に(j-thス…

ソース http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=390516 方針 ハニカム構造の隣接は図より int dx[6] = {1,1,0,-1,-1,0}; int dy[6] = {0,1,1,0,-1,-1};とすればいい。 あとは制約が小さいので各ターンごとに 既にvisitedな場所からいける場所…