デバッグに時間がかかりまくった。 セグメント木の応用かな。 #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>…

「何通りあるか」と「見ためが同じならば同じ解」っていう条件がいやらしい。 DP的な感じで解いた。 #include<cstdio> #include<algorithm> #include<map> #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; in</int,int></map></algorithm></cstdio>…

PKU解いてみた。 なぜこの問題をチョイスしたかというと、PKU Wiki*に載ってたから。 英語でも平気で読めるようになりたいものです。 「２分探索かな〜」とか「DPかな〜」とか思ってたら、 結局「２分探索＆DP」という結論に至った。 #include<cstdio> #define rep(i</cstdio>…

別に指摘されたとかじゃないけど、 #define pb push_back みたいなことするのって 変わってますかね？ 「push_back」ってよく使うわりに、打ちにくい気がするんですよね〜。 気のせいかもしれませんが。 追記 2/27 topcoderにて push_back を PB でdefineし…

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さんがおまけとして説明してた貪欲法かな〜、と思ったんですが割とすぐダメだと気…

本戦中、質問用紙使って２分探索でnaiさんの誕生日を調べる予定だったけど、 もちろんそんな余裕は無かった。 もしくは、 「あなたが"正しい"に○を付けない というのは正しいですか？」 みたいな質問でもしたかったけど、もちろんそんな余裕は無かった。

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

よくこんなに良問ばっかり出せるよなぁ JOIすげえ。

どんな問題が出るのか楽しみだ！ 終わったらなにか書きます。

昨日のスルメ、div2の1000悔しかったからage。 #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--) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ int minChanges(string S) { int n = S.size(), ans = 50, dp[50]; rrep(i,1,n){ rep(j,i) dp[j] = 0; rrep(…</n;>

あさってJOIの本戦だー！ というわけで明日東京に行く。 Aランクは余裕であって欲しい。 ってかそうじゃないといろいろ困る。 おやすみなさい。

あんまり記事書かないと思うけど、よろしく〜