ちょっとライブラリ風になった。 過去問からコードひっぱってくるときは、210みたいな数をちゃんと見てバグらないようにコピペすることが大事。 というか最小有向全域木は結構厄介なのでライブラリ化しましょう。 #include<stdio.h> #include<algorithm> #include<vector> #include<queue> #incl</queue></vector></algorithm></stdio.h>…

ついに2011本選が追加され始めたので。0251: 要は各連結成分が直線かどうかを聞いている。 #include<stdio.h> #include<algorithm> #include<vector> using namespace std; int deg[110000]; int UF[110000]; int FIND(int a){ if(UF[a]<0)return a; return UF[a]=FIND(UF[a]); } void UN</vector></algorithm></stdio.h>…

"ambigious", "ambigous"の元ネタはこれではなくBroken Audio Signalのほう。 行列累乗して連立方程式するやつ。 #include<stdio.h> #include<algorithm> using namespace std; int b[510][510]; int c[510]; int tmp[510][510]; int A[510][510]; int main(){ int a; scanf("%d"</algorithm></stdio.h>…

久しぶりにPKUクオリティのオンラインジャッジ環境。(問題と呼べる条件を満たせない典型例)1日ごとに全部売るのが最善であることが結構わかりにくい。 データが修正されたと書いてあるのに未だにデータに不備がある。AOJは機能もついているし何も損しないん…

解説スライドの2ページ目の図を見るだけ。*1 #include<stdio.h> #include<algorithm> #include<queue> using namespace std; const int INF=999999999; int ver[510][510]; int hor[510][510]; char dir[6]="UDLR"; int dx[]={0,0,-1,1}; int dy[]={-1,1,0,0}; char str[1100]; int dist</queue></algorithm></stdio.h>…

ハッシュやるだけ。 理想的ハッシュを使ったらWAしたのでダメなハッシュを使った。 というよりも、どうやらこのコードにある'P'も結構ハッシュの衝突具合に影響を及ぼすらしくて、小さいとかぶるっぽい。仕組みがよく分からないので数学の人なんとかして #in…

気がついたら簡単だった。 二つの1000000より大きい素数modで答えを求めてから二つのmodどちらにも当てはまるものを答えるだけ(中国剰余定理から当たり前) 負が入力に入るのがちょっと厄介。だけど、どうやってデータセットを作っているのだろう。気になる。…

問題の解法としては面白いのですが、問題の準備に雑さが目立ちます。・問題文 同じチケットは2回以上使えるのか？ 徒歩で戻ることはできるのか？・制約 制約の数が10^11以下で、これを何も横に書かずにただ100,000,000,000と書かれてもちゃんと気づけないと…

この問題、全AOJ-ICPC勢に嫌われてそう。 やっぱり変なコーナーケースとかもあるしなんか知らないけどオーバーフローしたのでごまかした #include<stdio.h> #include<algorithm> #include<string.h> using namespace std; char str[110]; int b[110]; long long pow10[17]; char to[110]; c</string.h></algorithm></stdio.h>…

dp[i]: 最後にiを使って行ったケース(この値そのものが行き方の総数ではなく、総数になるように上手く補正する(可能な行き方が減る)のをdp[j]->dp[i]やdp[i]->ansで更新するときに計算する)なかなか見ないタイプのDPで結構難しい。 #include<stdio.h> #include<algorithm> using </algorithm></stdio.h>…

明らかに問題文に不備があるので、AtCoderから実際にコンテストが行われたときのclarをさがしてきましょう。下の角のマスの隣(下線と同じy座標で盤面の外)はゴールではありません。 #include<stdio.h> #include<algorithm> #include<map> using namespace std; char str[31][31]; int </map></algorithm></stdio.h>…

あの変な式から二分探索を察する。 無駄に要素詰め込み感が満載だけど、影の秘密を解く足がかりにはなると思います。Time Limitが改善されるのを願ってやまない。 #include<stdio.h> #include<algorithm> #include<queue> #include<vector> #include<string.h> using namespace std; namespace MCF { } int</string.h></vector></queue></algorithm></stdio.h>…

計算量の解析が難しそうだがたぶん例のLCAテクでO(N^2)になるやつのそれぞれでO(N)かかってるからO(N^3)になるんだろうな～と予想がつく。コンビネーションで上手く数えるだけ。 #include<stdio.h> #include<algorithm> #include<vector> using namespace std; int mod=1000000007; int C</vector></algorithm></stdio.h>…

2点間の距離の計算がなんかやたら場合わけ漏れしやすいことに定評のある京都旅行。 もはやこのくらいの問題は45度すぐ見えるよね・・・ #include<stdio.h> #include<algorithm> using namespace std; int x[11000]; int y[11000]; int X[11000]; int Y[11000]; int ABS(int a){re</algorithm></stdio.h>…

やるだけだけどどうやるか考えた なんかこのやり方はだいぶ失敗な気がするんだけどループの段数が入力によって可変だと変なソースになるのはどうしようもないと思う。 #include<stdio.h> #include<string> #include<algorithm> #include<vector> using namespace std; int dice[6][6]={ {0,1,2,4,</vector></algorithm></string></stdio.h>…

残余グラフとか最小カットとかを真面目に考察しないといけない。かなり難しいと思う…。 #include<stdio.h> #include<algorithm> #include<vector> #include<map> #include<queue> using namespace std; const int D_MAX_V=2002; const int D_v_size=2002; struct D_wolf{ int t,c,r; D_wolf(){t=c=r=0</queue></map></vector></algorithm></stdio.h>…

上半分の点の集合が変わるのはO(N^2)回ある。2点を通る直線とy軸の交点を列挙すればこの区間を左側で分けられる。 左側がy=tのときの右側が取れる範囲の大きさは1次式で、上半分の点の集合が同じなら同じ式となるはず。 ということは、この領域の中央に代表…

まったく面白みのない最短路。 本当につまらない。 #include<stdio.h> #include<algorithm> #include<vector> #include<queue> using namespace std; int c[110]; int d[110]; vector<pair<int,int> > g[110]; vector<pair<int,int> > rev[110]; vector<int>h[1100]; int e[110]; int ijk[51][51][1<<10]; int v[51][51][1<<10]; i</int></pair<int,int></pair<int,int></queue></vector></algorithm></stdio.h>…

幾何してグラフ作って最短路というありがちなつまらないやつ。 線分が多角形に入ってるかどうかの判定も面倒で有名。 550なのに心が折れそうになった。というかこれはこんな問題で心が折れそうになる最近の自分が悪いと思う。だけど550の実装量じゃないよね…

robustness-hard。いい練習になる。 気をつけないといけないことは、 ・点が少ないときのMany ・平行のとき(中点を結んで線を作ろうとすると長さが極端に短くなって誤差る) ・交わるとき(点をいいかげんに選ぶとargを取るときに長さが極端に短くなって誤差る…

まあケースあたりO(N^2)くらいのDPをするだけ。 ケースがたくさんあるから最初に全部前計算をtotal O(N^3)未満でやるのかなと思ったら、ケース数が全然なかった。(このせいで無駄に時間を消費した) テストケース数に強く依存する計算量の問題はケース数とか…

英語を読むだけ。*1 1145148108931919364回くらい誤読すると自然とコードが汚くなる。 #include<stdio.h> #include<math.h> #include<algorithm> #include<queue> #include<map> #include<vector> using namespace std; int G[510][510]; int L[510][510]; int x[510]; int y[510]; int cnt[510]; vector<int>g[510</int></vector></map></queue></algorithm></math.h></stdio.h>…

これがこれで通るのは知識ゲーだと思う。 と思ったけど前にも木上でシュタイナー木作る問題は見たことがあるような…(非自明)Greedyです。 #include<stdio.h> #include<algorithm> #include<vector> #include<queue> using namespace std; vector<pair<int,int> > g[11000]; pair<int,pair<int,int> > edge[11000]; int v[11000]; </int,pair<int,int></pair<int,int></queue></vector></algorithm></stdio.h>…

文字ごとに桁数と(2桁なら)一の位が制約つきかを決めて(3^n通りある) 場合わけをひたすらがんばって数えるだけ。 まあ、解いてる人数が少ないだけあってつまらなかった。 #include<stdio.h> #include<algorithm> using namespace std; char str[1100]; char in[2]; int u[110]; i</algorithm></stdio.h>…

双対とって最小費用流。なかなかいろいろなものが得られた。 ・双対のやり方…知らないとどうしようもない。 ・出てきた形…フローを表す式も知らないとわかりにくい ・特殊な形の最小費用流…負コストがあり、最小流量制限があり、そして全体として流す量には…

これらの一部または全部を適当に並べて数字を作ることを考えます。 答えを1,000,000,007 で割ったものを出力してください。問題文がガバガバすぎる。 #include<stdio.h> #include<algorithm> #include<vector> using namespace std; int mod=1000000007; int b[210]; int kt[210]; int c[</vector></algorithm></stdio.h>…

最小有向全域木。 勉強がてら書いてみました。変な幾何パートもあるし、初書きはこういう問題ではやるべきでないと確信。 あと、こういう問題で英字配列の練習をするべきでないというのも確信。 #include<stdio.h> #include<algorithm> #include<vector> #include<math.h> using namespace std; d</math.h></vector></algorithm></stdio.h>…

こういうやるだけ全力疾走系好きなのでこういう問題だけでコンテスト開いてくれませんか。 20分くらい #include<stdio.h> #include<algorithm> #include<queue> #include<vector> using namespace std; char str[60][60]; int dx[]={0,1,0,-1}; int dy[]={1,0,-1,0}; int bfs[60][60]; int ijk[6</vector></queue></algorithm></stdio.h>…

←この人らもういいんじゃないかな…ということで難易度表収録を願って解きました。サッカーの順位表を日ごろから見ていると、ソート基準は問題文を読む必要がなくなるので、確率の式と入力の何文字目が数字なのか数えるくらいしかやることがないです。 #inclu…

二次元になっているものを一列にしてFFTをする。後は重複回数をよく考えつつうまくFFTの表から答えを出す。実行時間がかなりかかった。なぜだろう。 #include<stdio.h> #include<algorithm> #include<complex> #include<vector> #include<math.h> #include<map> using namespace std; const double PI = 4.0*ata</map></math.h></vector></complex></algorithm></stdio.h>…