2014/10/3に下書きとして保存されていてなぜか公開されていなかったのでこのタイミングで公開する。たぶん全部解いてから公開しようとしていたんだと思う。同じ問題に二つの記事がある場合はpart2と書いています。 第6回日本情報オリンピック 本選 最大の和 …

座標圧縮 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>…

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

問題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>…

このブログがものすごくわかりやすいです。JOI2011本戦 第四問「歩くサンタクロース」 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ JOI2011本戦 第四問「歩くサンタクロース」 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ #incl…

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

解法：ダイクストラ＋少しの考察。 まずダイクストラ法で各町についてショッピングモールまでの最短距離を求める。 次にそれぞれの道について、関数calcで計算する。 関数calcは道の両端の町のショッピングモールまでの最短距離と道の長さからその道の間にあ…

問題文頭では解けていたけど実装していなかった問題。 自作アルゴリズムをゴリ押ししたら通った。 解法 まず、 サンプルデータの画像で考える。次のように各横棒に対して二つの整数値を保存しておく。(下のソースではcという配列）二つの整数値がなにを表し…

やるだけこういう問題嫌いです。 #include <bits/stdc++.h> using namespace std; typedef pair<int,int> P; int n,m; int d[1010][1010][5]; char s[1010][1010]; char joi[3][3]; int ans = 0; int ha[4][4]; int main(){ scanf("%d%d",&m,&n); for(int i = 0;i < m;i++){ cin >> s</int,int></bits/stdc++.h>…

解法は顕著でいもす法やるだけなんだけど、メモリの制限がやたらと厳しいと言う問題。ACしたあと、もしかしたらと思い、"解答例（元 IOI 日本代表選手が作成した C++ サンプルソース）"をAOJに投げてみたらなんと"MLE"だったのでAOJ側の問題なのか？？ #incl…

二次元累積和やるだけ。 #include <utility> #include <sstream> #include <cstdio> #include <string> #include <set> #include <iostream> using namespace std; char s[1002][1002]; int dp[1002][1002][3]; int main(){ int m,n,k; scanf("%d%d%d",&m,&n,&k); for(int i = 0;i < m;i++){ scanf("%s",s[i]);</iostream></set></string></cstdio></sstream></utility>…

ちょっと考えたら解法が浮かんでくるのではないだろうか。 解法： d[i]をi番目のつららの長さとする。 まず、一番長いつららd[i]が折れるのにかかる時間はL-d[i]である。 次に、二番目にながいつららについて、その両隣のどちらかに自分より長いつらら（つま…

ヤバ問 解説は後ほど #include <cstdio> #include <algorithm> using namespace std; const int INF = 10000000; int n,t[10003]; int dp[2][5101][2]; int main(){ scanf("%d",&n); for(int i = 0;i < n-1;i++){ scanf("%d",&t[i]); } for(int i = 0;i < 2;i++){ for(int j = 0</algorithm></cstdio>…

累積和 入門 #include <cstdio> #include <algorithm> using namespace std; const int mod = 100000; int main(){ int n,m,d[100003]={0},ans=0; scanf("%d%d",&n,&m); for(int i = 2;i <= n;i++){ int tmp; scanf("%d",&tmp); d[i] = tmp + d[i-1]; } int nau = 1; for(int i </algorithm></cstdio>…

頭が悪い。解法： priority_queueと、二分探索をもちいた。 おそらくJOI解説とほとんどおんなじ。 気が向いたら詳しく説明します。priority_queue、大きいほうからでてくるのすっかり忘れてましたね #include <cstdio> #include <utility> #include <queue> #include <vector> #include <algorithm> usin</algorithm></vector></queue></utility></cstdio>…

解法： それぞれの座標に行く回数をn-1回分まで記録しておき、その回数が奇数だったら最初の文字（東、西）を反転させ、偶数の場合なにもしない。 最後にn回目の散歩の終わる座標を求めて出力。計算量O(HW)。 #include <cstdio> using namespace std; int h,w,n; int</cstdio>…

顕著な二分探索。なんかにぶたん使わなくても解けるらしいのですがややこしそうなので二分探索を使うほうがいいと思います。 #include <cstdio> #include <algorithm> using namespace std; int nau; int t[100003]; int main(){ while(1){ int d,n,m; scanf("%d",&d); if(d == </algorithm></cstdio>…

m解法の詳細は、連続する"IOI"の数を計算する。（たとえば、IOIOIのとき2） その値をtとすると、ans += max(0,t-n+1)で答えが求まる。 少し考えればできる問題。 #include <cstdio> #include <algorithm> #include <iostream> using namespace std; int main(){ while(1){ int n,m; char s</iostream></algorithm></cstdio>…

難しい。解法についてはJOIの解法を見るよりこちらを参照したほうがいい気がします。AOJ 0531 : Paint Color - きままにものづくり AOJ 0531 : Paint Color - きままにものづくり #include <cstdio> #include <vector> #include <algorithm> #include <queue> #include <string.h> #include <iostream> using namesp</iostream></string.h></queue></algorithm></vector></cstdio>…

普通にDPするだけ。 INFがINFになってなくて辛い思いをした。 #include <cstdio> #include <algorithm> #include <string.h> using namespace std; const int INF = 1000000000; int k[153]; int d[153][11][2]; int dp[153][11][80]; int n,m; int main(){ while(1){ scanf("%d%d",&n,&m)</string.h></algorithm></cstdio>…

解法：半分全列挙 粘り勝ち。実際WA続いたのはAOJがサーバーの負担を減らすためにテストデータをまとめた結果初期化が必要になってそれを忘れていただけだからたぶん本番はﾀﾞｲｼﾞｮﾌﾞ。計算量はO(N^2logN).まあ典型のやつですね。蟻本を読もう。 #include <cstdio> #in</cstdio>…

解法は顕著。 もし文字a[i] == b[j]だったらdp[i][j] = dp[i-1][j-1] + 1;をすることによって連続する文字列を求める。常にdp[i][j]の値をチェックし、最大のものが解。計算量はO(N^2). #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int d</algorithm></iostream></cstring></cstdio>…

こういう系の問題一番苦手。 実装力がない。 オーダーから察するにO(N)問題。int s[i]; （i番目について、白の碁石の連続している数） int k[i]; (i番目について、黒の碁石の連続している数) で値をもっておきあとはいわれたとおりにやる。 #include <cstdio> #inclu</cstdio>…