ルールを変えたNimでAliceとBobのどちらが必勝かを判定する問題 ルール： 石が1個以上ある山がいくつかある。 プレイヤーは毎回、一つの山から石を1個以上とる。 山は順番に並んでおり、1個以上石が存在する山のうち一番左の山からしか石をとることはできな…

問題 http://poj.org/problem?id=2378 解法 適当な頂点を選んで根にしてDFSして子を数えてやるとできる。 #include <cstdio> #include <algorithm> #include <vector> using namespace std; int N; vector<int> T[10001]; vector<int> ans; int dfs(int p, int q){ int sum = 0; bool f = true; fo</int></int></vector></algorithm></cstdio>…

問題 http://poj.org/problem?id=2456 解法 距離で二分探索。はじめ再帰で書いたが終了条件がよくわからなくてWAになったのでループ回した。 #include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 100000; int N, C; int a[MAX_N]; bool c(int d){ /</algorithm></cstdio>…

問題 http://poj.org/problem?id=1989 (翻訳)K種類の整数N個からなる整数列が与えられるので、その部分列とならない整数列のうち最短のものの長さを答えろ。 解法 整数列の先頭から、K種類の整数が一通り出るところまで進み、さらにその場所からまたK種類の…

昨日の夜、解いた。漸化式むずかしい #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>…

第2回科学の甲子園に出場してきました。入賞できてよかった（小並感） 情報分野担当だったが、あまり力を出しきれなかった感があって残念。 実技3が事前公開だったはずなのに、自分たちのチームだけ知らなかった。そのプログラムを前日の夜に書いたが、バグ…

SPOJを始めました問題 http://www.spoj.com/problems/ABCDEF/解法 式を ab + c = (f + e)d と変形すると二分探索が使える。右辺の値を決めて、左辺の値をにぶたんするとやりやすいと思う。 計算量は O(N^3 log (N^3) ) = O(N^3 log N) となる。 #include <cstdio> #i</cstdio>…

742 -> 933 (+191) 緑色になりました。 easyをdoubleで計算していた人がいて、1000000000を49個ぐらい並べてオバーフローさせた後で0を入れるとinf*0=nanみたいになる仕様を利用して撃墜しました。easy 0があるかないかと、負の数の個数を数える #include <cstdio> #</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>…

2月9日 7時30分に起きる。電車余裕。荷物の確認とかをする 9時15分くらいに福井駅につく。東京へ出発。 東京駅。迷う 新宿駅。迷う 小田急線で沖縄高専の方々と会う。 オリンピックセンターへ向かう。 灘勢がいる。なんかいろいろ話している。これがハラスメ…

以前、どうしてもバグが取れなくてあきらめていた問題 実装難しすぎ 解法 強実装。 #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にたどり着くことになる。 よ…

解法 二部グラフの最大マッチングとみなせるので最大流問題をとけばいい ford-fulkerson法が使える #include <cstdio> #include <algorithm> #include <vector> using namespace std; const int MAX_N = 200, MAX_M = 200; int N, M; class edge{ public: int to, cap, flow, rev; edge(</vector></algorithm></cstdio>…

問題 http://poj.org/problem?id=1226解法 全探索したら通った。最小の文字列を選んで計算回数を落としたが別に必要ないっぽい。 #include <cstdio> #include <algorithm> #include <string> #include <iostream> using namespace std; int t, n; int main(){ cin >> t; for(;t > 0; t--){ cin >> </iostream></string></algorithm></cstdio>…

Haskellの練習 main = do input <- getContents let c = head . head $ lines input s = last $ lines input putStrLn $ filter (/=c) s

解法 ソートして中央値を適当にとる よくわからない #include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 10000; int X[MAX_N], Y[MAX_N]; int N; int main(){ scanf("%d", &N); for(int i = 0; i < N; i++) scanf("%d %d", &X[i], &Y[i]); sort(Y,</algorithm></cstdio>…

あけましておめでとうございます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>…

問題解法 最長増加部分列(LIS)をとけばよい spaghetti source みてLISをO(n log n)で解くアルゴリズムをみた #include <cstdio> #include <vector> #include <algorithm> using namespace std; const int INF = 1 << 29; const int MAX_P = 40000; int T, P; int a[MAX_P]; int solve_li</algorithm></vector></cstdio>…

2012年がもうすぐ終わるので振り返りを書きます。1月 蟻本でアルゴリズムを勉強する。 2月 JOI本選のことがツイッターでつぶやかれているのをみる。来年行きたいなーと思う。 3月 高校受験。やべぇ勉強全然していない。 →なぜか受かったのでよかった 4月 高…

問題解法 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本選過去問埋めをやっています

こどふぉ初参加でした ABCの3完 1516(青)だった。 codeforcesのルールがよく分からない。 1500以上だとdiv1?A 各行が黒白互い違いになっていればYES,そうでないならNO #include <cstdio> using namespace std; char a[8][8]; int main(){ char c; bool f = true; for</cstdio>…

問題解法 union-findを使う。 人数の2倍の大きさのUF木を作って、 「AとBが違う」を unite(a, b+N), unite(a + N, b) とする。 A,Bが同じ根を持つなら同じグループ、A,B+Nが同じ根を持つなら違うグループとなり どちらでもない場合は「まだ分からない」とな…

問題解法 Union-Find木を使って連結状態的なものを持っておく。 コンピュータpを修理したとき、他の修理されたコンピュータの中で距離d以内のものとuniteする 同じ根を持てば、通信可能である。 #include <cstdio> #include <algorithm> using namespace std; typedef pair<int, int> P; c</int,></algorithm></cstdio>…

4完 + 部分点4点 = 84 だと思う。 1 #include <cstdio> #include <algorithm> using namespace std; int main(){ int l, a, b, c, d; scanf("%d %d %d %d %d", &l, &a, &b, &c, &d); printf("%d\n", l - max((a+c-1)/c, (b+d-1)/d)); return 0; } 2 #include <cstdio> #include <algorithm> using n</algorithm></cstdio></algorithm></cstdio>…

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