ソース 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を二分探索で求めて計算する。 二分探索は割とすぐ思いつけ…

結果 ooox- +0 2514pts(90th) 1552 -> 1661(+109)Div.1まであと39! & Highest更新 問題 A 1 あとはすべて異なる整数であることを忘れずに。 (ソースがとても汚い) int main(){ int r1,r2,c1,c2,d1,d2; cin >> r1 >> r2 >> c1 >> c2 >> d1 >> d2; for(int i=1…

結果 oox-- +0 1428pts 216th 1423->1552(+129) 問題 A 実装ゲー、文字列連結してsortして比較、が一番簡単だったらしい。 普通にアルファベットの出現頻度を全部カウントして一致判定した。 B 同じく実装ゲー、境界上は含まない点に注意すればよい。 C 人数…

方針 N本のボトルを運ぶときの最小の本数==Nの立っているビットの数 なので、ビットカウントをしてそれがKより少なければ運ぶことができる。これを1本ずつ足していって調べてみればよい。 足す本数は、多く見積もっても2^k ビットカウントにO(logn)掛かると…

問題 整数nが与えられる。 0,1,...,n-1行にそれぞれn-1,n-2,...1個のスペースがあるとし、左詰めで箱を詰める。 ただし、i行目の箱の数a_はa_i>a_j(i 方針 要は下に行くほど少なくなっていけばよい。 n-1行は0個か1個なので dp[0][0] = 1; dp[0][1] = 1; と…

結果 o--(+0/-0) 157.5pts 461st(Div.1)レートは 1221->1256(+35) 何とか年越しを青で迎えることができました。 250 うなぎ切るよ！ 10nな長さのうなぎはn-1回切ると長さ10のうなぎがn本取れるのでお得、なので 長さが10の倍数のものを小さい順に、そうでな…

結果 oo- (+0/-0) 478.37pts 105th(Div.2) 1190->1221(+31)Div1復帰しました。 250 MagicStonesStore ゴールドバッハ予想を使うとちょっと楽になるらしい。 sieveしてから全探索、引数nに対して2*n個というのを初め忘れていて提出が遅れた。Passed System Te…

久々にDPを全部自力で解けた。 問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0232 方針 dp[i][j] := i-thマスに得点jで来る確率 としてDP。 マスに止まる確率のみだと期待値が計算できないので、得点をDPテーブルに 入れるという発想が出…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0230 方針 nが割と小さいのでDFSで間に合う。 これまでの最小値を保持しておいてそれが更新される場合 そこから再帰的に最小値を更新していく。グラフを作って最短経路問題にも落とせる気が…

結果 ooxo- 2576pts, 447th(Div2)レートは 1583->1547(-36) 内容 A,Bはまぁやるだけ C 数列{a_n}のいずれか1つを任意の数に変更して(変更しなければならない) ソートしたときのk番目の値としてとりうる値の最小値を全てのkについて求めよ。基本的には初めに…

[使い方] -単一始点の最短経路とその経路長 -重みが負のedgeがあると使えないvoid dijkstra(int s,vector &cost, vector &prev, vector > edges); s:始点ノードの番号(0-index) cost[i]:sからi-thノードまでの距離を入れるvectorを渡す。 prev[i]:sからの最…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0155 方針 1 すべてのビル間の距離を計算して50以下ならedgeを張ってdijkstraすればよい。前々からdijkstraは書いておきたいなと思いつつも 下手なライブラリ書いて使っていくことにためらい…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0203 方針 配るDP。貰うDPでも書けなくはないと思う。 下から二段目にジャンプ台がある場合に注意。以下ソースコード #include <iostream> #include <cstring> #include <algorithm> using namespace std; int dw[3] = {-1,</algorithm></cstring></iostream>…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0221 方針 シミュレートする。 (Fizz || Buzz || FizzBuzz)でないときの処理を自前tointに任せていると文字列のときにうまくいかないのに気づかず数回WAした。基本的にはやるだけ。以下ソー…

結果 ---(+0/-0) 0pts 1251->1191次回はDiv.2。 300 外側から切っていくということは残せるのは長方形なので、 任意の部分長方形についてその内側をカウントすればいいのだが、そこからそれを残すために移動する回数を求める方法を考えて迷走した。 任意の部…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0181 方針 本棚の幅で二分探索。 あとはn冊の本を詰めるシミュレートをして、lb/ubを更新していけばよい。 判定は必要な段数のみでなく、本の厚みの最大値 計算量はO(n*log(本棚の最大値))だ…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0191 方針 i回目に選ぶものを決めるために影響するのはi-1回目に何を選んだかのみで、それまでにどういう選び方をしたかは関係ないので dp[i][j] := i回目にjを選んだ場合の最大の長さ とし…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0120 方針 左から円を並べていくと考えると、右端の円の大きさと追加する円の大きさによって増加する長さが変わることが解る。n dp[state][back] := state使った右端がbackであるものの長さ…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1082 元ネタが解りません… 方針 配る系のDP。 5種類音のある子音列はループするまでは あ->ああ->あああ あい ->い ->いあ ->う というように、最後にa音を1文字つけるor最後の文字を1つ進め…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1079 方針 同一のマスに対するクエリは最後のものが有効であることに着目して クエリを逆順に見ていけばよい。逆順に見て既にクエリを処理したことがあればそのクエリは無視、 そうでなけれ…