練習です。 250 ColorfulChocolates 文字列が与えられて、隣接する2つをmaxSwap回swapしたときの 連続する同じ文字の最大の長さを求める。方針は2つ 同じ文字に注目して、中央にあるものに寄せるときのコストといくつくっつけられるかを計算 区間を決めて、…

SWoPP(http://www.hpcc.jp/swopp/ )に参加して喋ってきました。 やってるのは分散並列ではないのですが、まぁそれはそれ。 1日目 9時から会場で、羽田6:30発とかいう飛行機を取ったので 朝初電で羽田に行くはめに。三田から京急で行こうと思ったら げ、三田…

すごいH本 すごいHaskellたのしく学ぼう!作者: Miran Lipovača,田中英行,村主崇行出版社/メーカー: オーム社発売日: 2012/05/23メディア: 単行本（ソフトカバー）購入: 11人 クリック: 464回この商品を含むブログ (24件) を見る を買ってIOまで一通り読んだ…

AOJ1179から1182までを解きました(先日のICPCの問題) 1179 Millennium やるだけ。 xxxx/yy/zzから1000/01/01までの日数を求める。 ただし1年は10ヶ月で、うるう年もどき(mod 3 == 0)だと全ての月が20日、 そうでない場合は20と19が交互。(1月は20日) 1000/01…

Win8RPを実機に入れたらMBR書き換えられてLinuxが起動できなくなった。 修復手順のメモ。 環境 MBRにはNTLDRが書き込まれている /dev/sda4が元のLinux(Fedora15)の/boot 元はgrub(grub2ではない)を使っていた。 手順 1. FedoraをLiveCDから立ち上げる 2. dme…

諸事情によりRHELをインストールする必要ができた。 手元にDVD-RがないのでUSBメモリからインストールしようと思ったときに 1点躓いたのでメモ。isoをUSBメモリに展開するのには LinuxLiveUSB Creator(http://www.linuxliveusb.com/ )というのを使っている。…

結果 o--(+0/-0) 224.08pts 60th 1782->1886(+104)Highest更新して初の1800台到達！ 600 Magical Hats Medも解けるようになっていかないといけないのでMed Openしてみた。 英文が読みづらい…要はコインが入っている場所を絞り込んでいくみたいだけど コイン…

結果 o--(+2/-1) 318.87pts 53rd 朝SRMで人が少ないけど、最高順位更新。レートは1594->1731で1700台復帰。 250 Pillers 問題 2本の棒が距離wで立っている。 棒の高さはそれぞれ[1,x],[1,y](1 棒の先端同士の距離の期待値を求める。 解法 高さが等しければ距…

はてダからimportしました。 いくつか表示がおかしいところがあるなぁ。

結果 ---(+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な場所からいける場所…

結果 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番のマスに到達した場合それ以上の移動はせず、 答えとしては を出力すればよい。