強連結成分分解初めて書いた。（蟻本見ながらだけど） 分解して、どの人からも電話がかかってこない人数を数える。 #include<cstdio> #include<vector> #include<algorithm> #define rep(i,n) for(int i = 0; i < n; i++) #define rrep(i,n) for(int i = 1; i <= n; i++) #define pb pus</algorithm></vector></cstdio>…

縦方向と横方向でそれぞれDPして、後で掛け合わせる。 結構ややこしい。 #include<cstdio> #include<algorithm> using namespace std; typedef long long ll; const int mod = 10000000; int dp[2][1001]; int main(){ int w[2], n, o = 0, p = 1, q = 1; char a; scanf("%d%d%d</algorithm></cstdio>…

貪欲法でおk。 「削除」をするよりも、「挿入」もしくは、２文字増やして「入れ替える」方が良い。 端に注意。 #include<cstdio> #include<algorithm> #define rep(i,n) for(int i = 0; i < n; i++) using namespace std; int main(){ bool f = true; int n, len = 0, x = 0, y </algorithm></cstdio>…

奇数＝true、偶数＝falseで周期性を見つければ良い。 #include<cstdio> #include<vector> #include<algorithm> #define rep(i,n) for(int i = 0; i < n; i++) #define pb push_back using namespace std; typedef long long ll; ll n, ki; vector<bool> s; ll cnt(ll x){ ll r = x/n*ki, l = x</bool></algorithm></vector></cstdio>…

ファレイ数列ですね。 エジプト→ファラオ→ファレイっていう発想だったりして・・・ #include<cstdio> #include<algorithm> #define rep(i,n) for(int i = 0; i < n; i++) #define fi first #define se second using namespace std; typedef pair<int, int> P; int m, k; P farey(P a, P b)</int,></algorithm></cstdio>…

どうしてもよく分からなかったので、id:JAPLJさんのソースを見た。 予想以上に短くてびっくりした。 うーん座標圧縮いらないとは・・・ 勉強になりました〜。 #include<cstdio> #include<map> #include<algorithm> #define rep(i,n) for(int i = 0; i < n; i++) #define pb push_back</algorithm></map></cstdio>…

うん、変わった問題ですね。 ざっくり説明すると、左上と右下に1、右上と左下に-1を書き、 縦と横に一回ずつ総和を取るといいらしい。（ざっくり過ぎか。） nが小さく限られているので、この方法が上手くいく。 #include<cstdio> #include<algorithm> #include<queue> #define rep(i,n)</queue></algorithm></cstdio>…

二分探索にしか見えない。。 思った以上に簡単だった。 汚いソースですが。 #include<cstdio> #include<vector> #include<algorithm> #define rep(i,n) for(int i = 0; i < n; i++) #define pb push_back using namespace std; int main(){ int n, m, a, b, ld = 0, rd = 1000000000, d,</algorithm></vector></cstdio>…

一発で通ったから気持ちよかった。 まぁ、DP臭しかしませんね。 #include<cstdio> #include<algorithm> #define rep(i,n) for(int i = 0; i < n; i++) using namespace std; const int INF = 100000000; int dp[6000]; int main(){ int n, d, a, wm = INF, nm; scanf("%d%d",&n,</algorithm></cstdio>…

JOI春合宿2011が中止となったようだ。 こんなのぜったいおかしいよ！ とか言ってみたいところだけど、この状況では仕方がないよね。

円を切って伸ばして直線にする発想はすぐ思いついたけど、そこからなんか詰まった。 が、なんのこっちゃない単なるDPだったorz #include<cstdio> #include<vector> #include<algorithm> #define rep(i,n) for(int i = 0; i < n; i++) #define rrep(i,n) for(int i = 1; i < n; i++) #def</algorithm></vector></cstdio>…

シンプルな問題だけどかなり難しい。 セグメント木ばっかり。 #include<cstdio> #include<vector> #include<algorithm> #define rep(i,n) for(int i = 0; i < n; i++) #define rrep(i,o,n) for(int i = o; i < n; i++) #define drep(i,n) for(int i = n; i >= 0; i--) #define pb push_b</algorithm></vector></cstdio>…

「面白い」としかいいようがないかな？ #include<cstdio> #include<algorithm> #define rep(i,n) for(int i = 0; i < n; i++) #define rrep(i,n) for(int i = 1; i <= n; i++) using namespace std; int d[1001][11][2], p[11], ans[1001]; int main(){ int n, m, t, x, y, a, b</algorithm></cstdio>…

デバッグに時間がかかりまくった。 セグメント木の応用かな。 #include<cstdio> #include<vector> #include<algorithm> #define rep(i,n) for(int i = 0; i < n; i++) #define pb push_back using namespace std; struct wall{int y, a, b;}; struct seg{int k, a, b;}; struct rem{int </algorithm></vector></cstdio>…

問題文を取り違えて悩んでた... プリムやらクラスカルやらで最小全域木を求めて、そこから料金の高い辺から順に引いていく。 #include<cstdio> #include<vector> #include<queue> #define rep(i,n) for(int i = 0; i < n; i++) #define rrep(i,n) for(int i = 1; i <= n; i++) #defi</queue></vector></cstdio>…

２分探索。 調べるときは葉からしなければならない。 #include<cstdio> #include<vector> #include<queue> #define rep(i,n) for(int i = 0; i < n; i++) #define rrep(i,n) for(int i = 1; i <= n; i++) #define pb push_back #define fi first #define se second using namespace </queue></vector></cstdio>…

trieなるものを使えばいいらしい。 多分 O(20 * 150000) ぐらいかな〜 #include<cstdio> #include<vector> #include<algorithm> #include<string.h> #define rep(i,n) for(int i = 0; i < n; i++) #define rrep(i,o,n) for(int i = o; i <= n; i++) #define pb push_back using namespace std; int</string.h></algorithm></vector></cstdio>…

面倒と言わざるを得ない・・・ stackでやりました。 #include<cstdio> #include<stack> #define rep(i,n) for(int i = 0; i < n; i++) #define fi first #define se second using namespace std; typedef long long ll; typedef pair<int, ll> P; stack<P> ans; void in(int a, ll l){ i</p></int,></stack></cstdio>…

累積和的なDP 結構シンプルにまとまって気持ちいい。 僕は、DP萌え ですね^^ #include<cstdio> #define rrep(i,n) for(int i = 1; i <= n; i++) using namespace std; const int mod = 1234567; int dp[500002], h[500001]; int main(){ int n, p, l = 0, sumh; scan</cstdio>…

なかなかにめんどくさい。 #include<cstdio> #include <cstdlib> #include<queue> #include<set> #define rep(i,n) for(int i = 0; i < n; i++) using namespace std; typedef long long ll; int main(){ int l, n, inx, iny, z, c, j; ll ans = 0; set<int> sx, sy; set<int>::iterator it; priorit</int></int></set></queue></cstdlib></cstdio>…

ウォーミングアップ。 ただ、出力データのでかさがぱない。 #include<cstdio> #define rep(i,n) for(int i = 0; i < n; i++) using namespace std; int main(){ int n, k; scanf("%d%d",&n,&k); if (n == 0){printf("J\n"); return 0;}; for(int i = 1 << (n-1); i ></cstdio>…

JOI本戦恒例の真のラスボス。 id:qnighyさんに 「最後にナップサック問題をもってくるあたり、さすがJOIだな」 的な事を言われたけど、一瞬何のことか分からなくて、ちょっとして分かったんだけど、そのときにはもうすでに遅かったっていう。 本戦競技で疲れ…

JOI本戦のラスボス。 セグメント木を出してくるとは、さすがJOI。 （qnighyさんはpriority queue＋しゃくとり法みたいな感じで解いたそうな） まずはセグメント木で実装し、次にBITでやってみます。 う〜ん、今回はソースコード見て理解して欲しいかも。 考…

今回から「負け惜しみの解説講座」みたいになるんじゃないかとヒヤヒヤしてたんですが、大丈夫でした(汗 問1 (20点) 内訳 ○○○○○○○○○○ 問2 (20点) 内訳 ○○○○○○○○○○ 問3 (14点) 内訳 ○○○○××○○×○ 問4 (0点) 内訳 ×××××××××××××××××××× 問5 (4点) 内訳 ○○×××××××…

本戦では迷走してしまった問題orz 町 or 道路上 にある家から一番近いショッピングモールまでの距離の最大値を求めろ、 って問題。 町 まずは各町からショッピングモールまでの最短距離をそれぞれ求めよう。 ○が町で、中に書いてある数字は町の番号。 数字が…

はい、今日もちょびちょび書いていきますよ〜 絶対DPは出るだろうと思ってたら案の定、出たっていう話ですね。 ただ、DPに至るまでにワンステップありましたね。 最初は、naiさんがおまけとして説明してた貪欲法かな〜、と思ったんですが割とすぐダメだと気…

JOIの本戦が終了した。 フィードバックたんは「４問正解だよ〜」って言ってるけど、正直５番はO(n^2)だから甘く見積もっても20点だし、３番はpriority_queue使うべきところで単なるqueue使っちゃったから分からん。 上位陣との差を改めて痛感した。 せっかく…