2015-01-01から1年間の記事一覧
予選落ちました。今年から本選会場が東京から筑波に変わるらしくて行きたかったけど残念です(チーン)。おひさしぶりです。JOI予選に参加して死んできました。結果はたぶん4完です。問5,6は頭で解けましたが実装力不足で面倒くさくなってやめました。ジュケン…
youtube見まくったし常勝
とうとう前日になっちまいましたね。 楽しみです。 去年は知ってる人とか誰もいなくて不安ありまくりだったけど今年は楽しみ感ありまくりですね。とりあえず楽しむのを目標にやってきます。 まあ結果はついてくるでしょ。 今日は早く寝よう。以上。 ※2015/2/…
明日やろう http://www.amazon.co.jp/%E6%98%8E%E6%97%A5%E3%82%84%E3%82%8D%E3%81%86%E3%81%AF%E3%83%90%E3%82%AB%E3%83%A4%E3%83%AD%E3%83%BC-NSK-MOOK-%E9%81%A0%E8%97%A4-%E4%BF%9D%E4%BB%81/dp/4930942977
座標圧縮 is 楽しい 趣味は座標圧縮です。 #include <bits/stdc++.h> using namespace std; typedef pair<int,int> P; int w,h,n,d[1004][4],so[2]; int m[2010][2010]; int kari[2][6010]; int di[4] = {-1,0,1,0}; int dj[4] = {0,-1,0,1}; int sea(int ban,int s){ int lb = 0,ub </int,int></bits/stdc++.h>…
二分探索の練習平均最小化小数の闇に注意割と平均最大(小)化好きかもしれない。 #include <bits/stdc++.h> using namespace std; struct edge{ int from; double time; int ren; }; const int INF = 1000000000; int n,m,c; double dp[10009]; bool flag[10006]; vector<edge> g</edge></bits/stdc++.h>…
n回もといているのでさすがに短時間で全完できた。第一問やるだけ #include <bits/stdc++.h> using namespace std; int n,ans; int sum; int d[100005]; int k; int main(){ while(1){ scanf("%d%d",&n,&k); if(n+k == 0)break; ans = 0; sum = 0; for(int i = 1;i <= n;i++</bits/stdc++.h>…
本選まで残り約一週間ですね。
普通にDPだった。 """IOI列車は闇"""とだけ昔から聞いて怖いなーと思ったけど割と普通に通ってしまった。 闇要素どこにあるんだろう・・・ #include <bits/stdc++.h> using namespace std; int n,m,ans; int s[2004],t[2004]; int dp[2004][2004][2]; int han(int x){ if(x </bits/stdc++.h>…
やるだけ。 実装。 #include <bits/stdc++.h> using namespace std; int n,co,ans; int ren[100004]; int ha[100004]; bool l[100004]; int main(){ scanf("%d",&n); ans = 1; for(int i = 1;i <= n;i++){ int tmp; scanf("%d",&tmp); if(tmp == 0){ l[i] = false; }else{ l</bits/stdc++.h>…
解法:Segment Tree(RMQ)セグツリやるだけUSACOの問題。Range Minimum QueryとRange Maximum Queryを同時に処理する。計算量O(Q lg N). #include <cstdio> #include <algorithm> #include <climits> using namespace std; typedef pair<int,int> P; int n,q,seg[2][121072],nn; P query(int a,int </int,int></climits></algorithm></cstdio>…
問題1-JJOOIIやるだけ。実装。ちょい面倒。 #include <bits/stdc++.h> using namespace std; int ans,sum[4];; char d[1000006]; void syokika(){ for(int i = 0;i < 3;i++)sum[i] = 0; } int main(){ scanf("%s",d); char mo[4]; mo[0] = 'J'; mo[1] = 'O'; mo[2] = 'I'; i</bits/stdc++.h>…
dijkstra法やるだけ #include <bits/stdc++.h> using namespace std; struct edge{int to,cost;}; typedef pair<int,int> P; int n,m,k,ans,d[3007],miti[100005][3]; const int INF = 1000000000; vector<edge> G[3007]; int main(){ scanf("%d%d%d",&n,&m,&k); for(int i = 0;i <= n;i++)</edge></int,int></bits/stdc++.h>…
DP頭悪すぎて謎な漸化式になったがなぜか通った。闇である。以前にも解いてたっぽい 第10回日本情報オリンピック 本選 「古本屋」 AOJ0561 (Books) - intさわだんのBlack History 第10回日本情報オリンピック 本選 「古本屋」 AOJ0561 (Books) - intさわだん…
想定解は二次元累積和なのですが二次元BITの練習のため二次元BITで解いてみた。 本番では絶対こんな手法は使わない。 計算量はO(K*logM*logN)でだいたいO(10^7)ぐらいなので間に合う。 #include <bits/stdc++.h> using namespace std; int bit[3][1010][1010]; int m,n,k; i</bits/stdc++.h>…
実装力も大事だけど効率のよい正しいアルゴリズムを設計する力もめっちゃくちゃ大事だと思った。 #include <bits/stdc++.h> using namespace std; typedef pair<int,int> P; typedef pair<int,P> PP; int n,l,ans,d[100004]; int main(){ scanf("%d%d",&n,&l); priority_queue<P,vector<P>,greater<P> > que</p></p,vector<p></int,p></int,int></bits/stdc++.h>…
しんちょくだめです
Solution of this task:DP(dynamic programming).the recurrence formula would be as follows.dp[i][j] := max(dp[i-1][j],dp[i-w][j-1]);dp[i][j] means the maximum achievable score when player threw j balls and knock over no more than i pins.comp…
CCC(Canadian Computing Competition)'s task.This problem is level three (a good grade 12 student MIGHT get this)I used typical DP(Dynamic Programming) to solve this problem. #include <bits/stdc++.h> using namespace std; int dp[30][30]; int r,c,k; bool ch[</bits/stdc++.h>…
JOI本選では、上位20名+地区別成績優秀者になります。前者をクリアしたらおそらく後者もクリアしたことになると思うけど。。。精進します。
結構昔に「わかんねっ」っていって放置してた問題。座標圧縮 #include <bits/stdc++.h> using namespace std; typedef long long ll; int n,m; ll ans; ll d[52][7]; ll sx[110],sy[110],sd[110]; int main(){ scanf("%d%d",&n,&m); for(int i = 0;i < n;i++){ for(int j = </bits/stdc++.h>…
貪欲法 計算量がO(NM)でNM = 10^7だから「計算量ちょっとやばいかなー」と思ってできるだけ高速に実行できるように頑張ったけど実際そんなことやる必要なかった問題。 #include <bits/stdc++.h> using namespace std; int n,m,co,ans,yaruki[10003],ruisekiyaruki[10003],oy</bits/stdc++.h>…
難しかったけど解ける気がしたのでめっちゃがんばって無理やり解いた。WAとRE大量発生しまくってとてもつらい思いをした。生のソースはっつけます。解法とか書く気力がおきない。 #include <bits/stdc++.h> using namespace std; const int INF = 1000000000; int n,c; int </bits/stdc++.h>…
このブログがものすごくわかりやすいです。JOI2011本戦 第四問「歩くサンタクロース」 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ JOI2011本戦 第四問「歩くサンタクロース」 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ #incl…
以前バケット法でも解けますとか言ってたので解いた。第7回日本情報オリンピック 春合宿 1日目 「インフルエンザ」 (Flu) - intさわだんのBlack History 第7回日本情報オリンピック 春合宿 1日目 「インフルエンザ」 (Flu) - intさわだんのBlack Historyバケ…
解法:トポロジカルソート過去の自分のほうが頭いい気がする。↓ 第7回日本情報オリンピック 春合宿 1日目 「色紙」 - intさわだんのBlack History 第7回日本情報オリンピック 春合宿 1日目 「色紙」 - intさわだんのBlack History #include <bits/stdc++.h> using namespace</bits/stdc++.h>…
なんか前解いたことある気がする。解法:DPコーナーケースがある。 #include <bits/stdc++.h> using namespace std; const int INF = 100000000; int n,ans=-INF,sa[100004][2],am=-INF,dp[100003]; int main(){ scanf("%d",&n); for(int i = 1;i <= n;i++)scanf("%d%d",&sa</bits/stdc++.h>…
DP解説は下を参照してください。 http://www.ioi-jp.org/joi/2013/2014-ho/2014-ho-t2-review.pdf #include <bits/stdc++.h> using namespace std; const int INF = 1000000000; int m,n,ans; int ma[10003]; int ha[503][2]; int dp[503][10003]; int main(){ scanf("%d%d"</bits/stdc++.h>…
DPdp[i][j]:=ジャンルiまでの本をj冊売るときの買い取り価格の最大値.各ジャンルについてソートしてi冊売ったときの値段を記録しておきます。 #include <bits/stdc++.h> using namespace std; int n,dp[2003][2003],b[11][2003],k,co[11]; int main(){ scanf("%d%d",&n,&k);</bits/stdc++.h>…
#include using namespace std; typedef pair P; int n,k,dp[2003][2003],ans; P d[2003]; int nau[2003][11],pre[2003][11];int main(){ scanf("%d%d",&n,&k); for(int i = 1;i scanf("%d%d",&d[i].first,&d[i].second); } d[0].first = 100000000; sort(d,…