第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>…