http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1142&lang=jp D言語らしいコードが書けた mutableじゃないとreverseできない（当たり前）とかimmutableだと~が使えない（なんでだろう？）で引っかかった 例えば，下の解答の一部で char[] v = st…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2317 二分探索。場合分けを冷静にしてオーバーフローに気をつける import std.stdio; import std.string; import std.conv; import std.algorithm; import std.range; import std.typecons; int a…

センター試験まで1週間です。 気分転換に解いた http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2600 解法 imos法を使ってカバーできているかどうか調べる。 コーナーケースがあって、マスの辺はカバーできているけど中身がカバーできていないと…

解いた．後ろから，最終的に一番上になるものだけ見るテクニックを使うと計算量が小さい． while True: n,r = map(int,raw_input().split()) if n == 0 and r == 0 : break p = [None] * r c = [None] * r for i in range(r): p[i],c[i] = map(int, raw_inpu…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2235 クエリを平方分割する問題．平方分割した後にいらない頂点をつぶすのが超大変． Union-Find treeでがんばってつぶす． 以前からあった辺が，今みている区間のなかで破壊されるとき，あらかじ…

いもす法を排他的論理和でやるみたいな方法で解きました。 長方形に番号をふります。 グリッドのマスの、2進数のある桁が1になっているとき、そのマスには(その桁数)番の長方形が存在する、という風に対応させます。 いもす法みたいに配置して累積XORをとる…

以前まったく分からなかったが、久しぶりにやってみると解法がすぐ思いついて驚いた。問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0542解法 ある事務所で認証レベルを順番にあげていって、入れる部屋の総数とレベルの表をつくる 最初の…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0519解法 トポロジカルソートする。 途中で候補の頂点が複数あらわれた場合、順位表が複数ありえる。 O(V+E)だけど実装下手なせいでO(V^2)になった #include <cstdio> #include <vector> #include <algorithm> using nam</algorithm></vector></cstdio>…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0270 解法 去年のパソコン甲子園の問題。去年の本選のとき解けなかった。 解説にのっているやり方とはちょっと違うやり方でやった。 アルゴリズムは解説のものより log N 倍ぐらい遅いはずだ…

D言語を使う練習として解いた D言語っぽいことはやっていない import std.stdio; import std.array; import std.conv; void main(){ bool[60000] p; p[0] = false; p[1] = false; for(int i = 0; i < 60000; i++) p[i] = true; for(int i = 2; i * i < 60000…

昨日の夜、解いた。漸化式むずかしい #include <cstdio> #include <algorithm> using namespace std; const int INF = 1<<29; const int MAX_N = 10000; int N; int a[MAX_N]; int dp[2][MAX_N][2]; int main(){ scanf("%d", &N); a[0] = 0; for(int i = 1; i < N; i++) scanf("</algorithm></cstdio>…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0580解法 3次元空間での座標圧縮。圧縮後と圧縮前の値の変換が出来るようにして圧縮する。 #include <cstdio> #include <algorithm> #include <vector> #include <set> using namespace std; typedef long long ll; int N, K;</set></vector></algorithm></cstdio>…

以前、どうしてもバグが取れなくてあきらめていた問題 実装難しすぎ 解法 強実装。 #include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 10000; int N; int main(){ while(scanf("%d", &N), N!=0){ int a[N]; for(int i = 0; i < N; i++) scanf("%d</algorithm></cstdio>…

JOI本選まで一週間を切っています 動的計画法の問題を安定して解けるようになりたい 解法 dijkstra法使う #include <cstdio> #include <algorithm> #include <vector> #include <queue> using namespace std; const int INF = 1 << 29; const int MAX_V = 3000, MAX_E = 100000; typedef pair<int, int> P</int,></queue></vector></algorithm></cstdio>…

解法 あみだくじにおいて、ある横棒をたどる回数はちょうど2回だから、その横棒を取り去ると2つの縦は交換されない。 つまりa,bがそれぞれc,dにたどり着いている、とすると、a,bがとおる横棒を一つ取り除けば、a,bはそれぞれd,cにたどり着くことになる。 よ…

あけましておめでとうございますDFSやるだけなのにWAをかさねて新年そうそうに絶望。 #include <cstdio> #include <vector> #include <algorithm> using namespace std; int N; bool used[101]; vector<int> rings[101]; int dfs(int p){ int ret = 1; for(int i = 0; i < rings[p].size(); i</int></algorithm></vector></cstdio>…

問題解法 10^7回も散歩する太郎君の問題 解説みた。動的計画法を使う。 #include <cstdio> #include <algorithm> using namespace std; const int MAX_HW = 1000; int N, H, W; int a[MAX_HW + 2][MAX_HW + 2]; int dp[MAX_HW + 2][MAX_HW + 2]; int main(){ while(scanf("%d %d</algorithm></cstdio>…

解説みた。 最大値の伝搬を使った #include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 5000; const int MAX_M = 500000; int N, M; short nail[MAX_N][MAX_N]; int main(){ scanf("%d %d", &N, &M); for(int i = 0; i < M; i++){ int a, b, x; sca</algorithm></cstdio>…

Bから新しい山を作るとき、下から取り除く分は考えずに、 上からn枚取り除いたときのことを考える。 この時できた新しい山とAとの最長の共通列？はO(N)で求まる。 よって全体としてはO(N^2)で計算できる。 #include <cstdio> #include <algorithm> using namespace std; const i</algorithm></cstdio>…

文字列を圧縮(文字の種類+その文字が何個あるかの情報に)する 圧縮した文字列にJOIがあったら、JOI列の条件を満たしているか確認してレベル計算 O(N) #include <cstdio> #include <cstring> #include <algorithm> using namespace std; char s[1000010]; char t[1000010]; int tn[1000010</algorithm></cstring></cstdio>…

84点Aランクで本選行きます。AOJのJOI本選過去問埋めをやっています

今日はJOI予選です。5完を目指します 問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0530解法 動的計画法をつかう 横の列の個数分の配列をとるとTLEしそう。 そこで、一つの行には石がたかだか10個しかないという制約を利用するとはやくな…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0536解法 やるだけ問題なんだけど実装キツい カードの数字なんて気にしなくてよいので、最初に、r以下のカードを白い碁石、rよりおおきいカードを黒い碁石にでも置き換えると、ちょっと実装…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0123解法 やらないだけ #include <cstdio> #include <algorithm> using namespace std; const double t500[7] = { 35.50,37.50,40.00,43.00,50.00,55.00,70.00 }; const double t1000[7] = { 71.00,77.00,83.00,</algorithm></cstdio>…

明日、PCK本選です。 がんばります!問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0223解法 地道に幅優先探索する。 #include <cstdio> #include <algorithm> #include <queue> #include <vector> using namespace std; typedef pair<int,int> P; typedef pair<int , pair<P, P> > T; const int INF = 1 </int></int,int></vector></queue></algorithm></cstdio>…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0124解法 ソートするだけ ”勝ち点が同点の場合は入力順に出力してください。”を読み間違えて1WA 入力順を記録するための値をpairに持つと便利 #include <string> #include <iostream> #include <algorithm> using namespac</algorithm></iostream></string>…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0557解法 動的計画法 状態は [i][j] = i番目の数字までを使ってjを作る+-の入れ方の総数 とした。 #include <cstdio> #include <algorithm> using namespace std; typedef long long ll; int a[101]; ll dp[101]</algorithm></cstdio>…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0547解法 動的計画法。 #include <cstdio> #include <algorithm> using namespace std; const int MOD = 100000; typedef pair<int, int> P; typedef pair<P, P> PP; PP dp[101][101]; int main(){ int h, w; for(int i=0; i < 1</p,></int,></algorithm></cstdio>…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0538解法 動的計画法を使う。 Oの数を数えることを意識して、 a[i] = if(s[i-1]=='I' && s[i]=='O' && s[i+1] == 'I') a[i-2] + 1 else 0 という漸化式を作り、aの中に何個N以上の数があるか…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0539解法 二分探索。 店の距離を小さい順にソートして宅配先がどこの店の間にあるかを二分探索して求める。 環状になっているので宅配先の距離が一番距離の大きい店より大きいなら、本店とど…