概要 去年の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な場所からいける場所…

結果 o--(+0/-0) 149.02pts 310th(Div.1) 1629->1671(+42)またもやhighest更新！ 250 n匹(n アリ同士が衝突すると消える。最終的に残るアリの数を答えよ。はじめは任意の異なる2匹のアリがぶつかるかどうかが解るので時系列順に出して 云々かなぁと思ったも…

Vol.12がだんだんきつくなってきたのでここらでVol.01の残りを掃除でもしようかと。 問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0145 ソース http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=385224 方針 solve(a,b):=a番目の山…

ソース http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=382916 方針 DP。 dp[i][j] := (i-1,j-1)を末尾とする最大の文字列 dp[i][j] = "" ((i,j)がアルファベット) dp[i][j] = max(dp[i-1][j] + (i,j), dp[i][j-1] + (i,j)) (左から来るか、上から来…

ソース http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=382422 方針 典型的なDP dp[i][j] := i回振った後にjマス目にいる確率を計算していけばよい。n番のマスに到達した場合それ以上の移動はせず、 答えとしては を出力すればよい。

ソース http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=382200 解き方 継子立てのバリエーション。(ヨセフスの問題とも言うらしい) http://ja.wikipedia.org/wiki/%E3%81%BE%E3%81%BE%E3%81%93%E7%AB%8B%E3%81%A61,2,...,nのn人を円形にclockwiseに…

結果 o--(+4/-0) 282.82pts 58th(Div.1) 1481->1665(+184)Highest更新 && 黄色到達 && Div.1初2ケタ！ 250 A[0]を決め打ちすればBを満たすAは一意に決まる。 またA[0]を1増やした時にA[k]が増加するか減少するかは 符号列によって決まる。例えば B: + - + 3 …

AOJ上でソースを公開できるようになったのでそのテストも兼ねてソース http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=376363与えられたN(1 2^15以下の平方数は181個しかないのでDPで dp[i][j][k] := i番目の平方数まででj個使った和がkになるような…

結果 oo- (+0/-0) 505.34pts 442nd 1436->1481(+45) Highest更新&&TCO Round1通過！ 250 しばらく問題文を正しく読めてなかった。 最大8ターンなのでシミュレーションすればよい。 vector <string> getWinners(vector <string> players) { set<string> ret; sort(players.begin(), pl</string></string></string>…

dir内の全文検索は find ./ -name "" -print | grep <hoge>とこの変化系でどうにかなる。 sortしたい場合なんかは find ./ -name "<pattern>" -print | sort -n | hogehoge...と書くとよい。</pattern></hoge>

随分空いてしまった。 結果 oo- 381.48pts 1344->1436(+92)Highest更新&&初midpassed(450だけど) 250 xy平面上にある点の集合に対し、(0,0)を出発点として全ての点 を任意の順で訪問するとき、歩数のparity(偶奇)が与えられたものと 一致するような訪問順が…

300-450-1000という変則セット。 結果 o--(+0/-0) 142.27pts 314th(Div.1) 1224->1320(+96) 300 DengklekMakingChains 300は怖いなぁと思いつつ問題読む。3つの{.|0-9}からなる文字列が与えられ、それを任意の順番でconcatしたときに できる連続する数字の和…

結果 ooo 887th Round.1は通過、次はむり。この形式のコンテストは(GCJとか) MLEとTLEをあんまり気にしなくていいのが楽である。 Checkpoint カタラン数(http://ja.wikipedia.org/wiki/%E3%82%AB%E3%82%BF%E3%83%A9%E3%83%B3%E6%95%B0)のような問題。 格子上…

いくつか通しました 1100 1132 幾何。幾何問題はcomplexを使うと非常に楽です。 1104 実装ゲー 1144 DFS。 10回の移動までなので最大でも4^10*20(盤面の広さ)なので間に合う。 結構実装戸惑った。しょぼい。

問題 xy平面上の(i,0)に高さh_i(i=1,2,...,n)のn本のビルがあるとき、あるビルから見える他のビルの屋上の最大数を求めよ 方針 あるビルに注目したときそのビルから左右方向に別々にループを回すのはめんどいので ビルiからビルjの屋上が見える場合その逆も…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1109 問題文通り。与えられたzについて z^3-max{x^3 + y^3| x>0, y>0, x^3 + y^3 を計算する。 方針 xを決めて条件を満たす最大のyを二分探索で求めて計算する。 二分探索は割とすぐ思いつけ…