2014 情報オリンピック 予選 参加記
あとから見れるようにソースはっとく。
本番のソースそのままはるからとても見にくいと思われます。
競技前、風邪がやばいな～～と思っていた。
高校入試と同じように ももいろクローバーZの「行くぜっ！怪盗少女」を聞く。
この曲を聞くとなぜか緊張がおさまる。
一応言っておくと、別にももクロそんな好きじゃないです。嫌いでもないけど。
競技開始。
1
#include <bits/stdc++.h> using namespace std; int main(){ int a,b,c,d,p; cin >> a >> b >> c >> d >> p; int x = p*a; int y = b; if(p > c)y += (p-c)*d; cout << min(x,y) << endl; return 0; }
2
#include <bits/stdc++.h> using namespace std; int n,m,ans[300]; int t[300]; int main(){ cin >> n >> m; for(int i = 0;i < m;i++){ cin >> t[i]; } for(int i = 0;i < m;i++){ int ha = 0; for(int j = 1;j <= n;j++){ int y; cin >> y; if(t[i] == y){ ans[j]++; }else{ ha++; } } ans[t[i]] += ha; } for(int i = 1;i <= n;i++){ cout << ans[i] << endl; } return 0; }
3
#include <bits/stdc++.h> using namespace std; int h,w; char s[300][300]; int main(){ cin >> h >> w; for(int i = 0;i < h;i++){ cin >> s[i]; } for(int i = 0;i < h;i++){ for(int j = 0;j < w;j++){ int ans =0; for(int k = j;k >= 0;k--,ans++){ if(s[i][k] == 'c'){ cout << ans; goto out; } } cout << -1; out: ; if(j != w-1)cout << " "; } cout << endl; } return 0; }
4
#include <bits/stdc++.h> using namespace std; typedef long long int ll; const long long int INF = 1000000000000; ll n,m; ll d[1300],c[1300]; ll dp[2000][2000]; int main(){ for(int i = 0;i <= 1200;i++){ for(int j = 0;j <= 1200;j++){ dp[i][j] = INF; } } cin >> n >> m; for(int i = 1;i <= n;i++){ cin >> d[i]; } for(int i = 1;i <= m;i++){ cin >> c[i]; } for(int i = 0;i <= 1200;i++){ dp[i][0] = 0; } for(int i = 1;i <= m;i++){ for(int j = 1;j <= n;j++){ dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]+d[j]*c[i]); } } cout << dp[m][n] << endl; return 0; }
ここまでで大体40分ぐらい。さすがに簡単過ぎて4完では若干不安があったので、"絶対問題5解こうな"ってなる。
問題5見る。
なるほど、やるだけだな。
書く。
#include <bits/stdc++.h> using namespace std; int h,w; char s[1300][1300]; int d[1300][1300]; int ans = 0; int da[] = {1,1,1,0,-1,-1,-1,0}; int db[] = {1,0,-1,-1,-1,0,1,1}; bool flag; void ch(int a,int b){ int co = 0; for(int i = 0;i < 8;i++){ int na = a + da[i]; int nb = b + db[i]; if(na >= 0 && na < h && nb >= 0 && nb < w && d[na][nb] <= 0 && ans >= abs(d[na][nb]))co++; } if(co >= d[a][b]){ d[a][b] = 0; d[a][b] -= (ans+1); flag = true; } } int main(){ cin >> h >> w; for(int i = 0;i < h;i++){ cin >> s[i]; } for(int i = 0;i < h;i++){ for(int j = 0;j < w;j++){ if(s[i][j] == '.'){ d[i][j] = 0; }else{ d[i][j] = s[i][j] - '0'; } } } flag = true; while(flag){ flag = false; for(int i = 0;i < h;i++){ for(int j = 0;j < w;j++){ if(d[i][j] > 0) ch(i,j); } } if(flag == true)ans++; } cout << ans << endl; return 0; }
コンパイルして実行する。
あれ、テストケース2の計算がまったく終わらない・・・なぜだ。
ちょっと考える。
ちょっと無駄な計算を省いて書く。
#include <bits/stdc++.h> using namespace std; int h,w; char s[1300][1300]; int d[1300][1300]; int sa[1300][1300]; int ans = 0; int da[] = {1,1,1,0,-1,-1,-1,0}; int db[] = {1,0,-1,-1,-1,0,1,1}; bool flag; void ch(int a,int b){ int co = 0; for(int i = 0;i < 8;i++){ int na = a + da[i]; int nb = b + db[i]; if(na >= 0 && na < h && nb >= 0 && nb < w && d[na][nb] <= 0 && ans >= abs(d[na][nb]))co++; } if(co >= d[a][b]){ d[a][b] = 0; d[a][b] -= (ans+1); flag = true; } } int main(){ scanf("%d%d",&h,&w); for(int i = 0;i < h;i++){ scanf("%s",s[i]); // cin >> s[i]; } for(int i = 0;i < h;i++){ for(int j = 0;j < w;j++){ if(s[i][j] == '.'){ d[i][j] = 0; for(int k = 0;k < 8;k++){ int aa = i + da[k]; int bb = j + db[k]; if(aa >= 0 && aa < h && bb >= 0 && bb < w)sa[aa][bb]++; } }else{ d[i][j] = s[i][j] - '0'; } } } flag = true; while(flag){ flag = false; int ad[1200][1200] = {0}; for(int i = 0;i < h;i++){ for(int j = 0;j < w;j++){ if(d[i][j] > 0 && sa[i][j] >= d[i][j]){ flag = true; d[i][j] = 0; for(int k = 0;k < 8;k++){ int aa = da[k] + i; int bb = db[k] + j; if(aa >= 0 && aa < h && bb >= 0 && bb < w)ad[aa][bb]++; } } } } for(int i = 0;i < h;i++){ for(int j = 0;j < w;j++){ sa[i][j] += ad[i][j]; } } if(flag == true)ans++; } cout << ans << endl; return 0; }
結果変わらずテストケース2の計算がまったく終わらない。
若干あせる。
冷静に考察する。
あ、これ幅優先探索ｼﾞｬﾝw
書く。
#include <bits/stdc++.h> using namespace std; typedef pair<int,int> P; const int INF = 1000000000; int h,w; char s[1300][1300]; int d[1300][1300]; int ka[1300][1300]; int sa[1300][1300]; int ans = 0; int da[] = {1,1,1,0,-1,-1,-1,0}; int db[] = {1,0,-1,-1,-1,0,1,1}; bool flag; void ch(int a,int b){ int co = 0; for(int i = 0;i < 8;i++){ int na = a + da[i]; int nb = b + db[i]; if(na >= 0 && na < h && nb >= 0 && nb < w && d[na][nb] <= 0 && ans >= abs(d[na][nb]))co++; } if(co >= d[a][b]){ d[a][b] = 0; d[a][b] -= (ans+1); flag = true; } } int main(){ queue<P> que; scanf("%d%d",&h,&w); for(int i = 0;i < h;i++){ scanf("%s",s[i]); // cin >> s[i]; } for(int i = 0;i < h;i++){ for(int j = 0;j < w;j++){ ka[i][j] = INF; if(s[i][j] == '.'){ d[i][j] = 0; ka[i][j] = 0; que.push(P(i,j)); }else{ d[i][j] = s[i][j] - '0'; } } } while(que.size()){ P p = que.front(); que.pop(); int a = p.first; int b = p.second; for(int i = 0;i < 8;i++){ int aa = a + da[i]; int bb = b + db[i]; if(aa >= 0 && aa < h && bb >= 0 && bb < w && ka[aa][bb] == INF){ sa[aa][bb]++; if(sa[aa][bb] >= d[aa][bb]){ ka[aa][bb] = ka[a][b]+1; que.push(P(aa,bb)); ans = max(ans,ka[aa][bb]); } } } } cout << ans << endl; return 0; }
無駄な変数や関数などがありますが・・・
なんとか書いて全部答えが出て安心する。
あと残り一時間。どうする。
問題6とりあえず見る。
やばそう。解法わかりそうでわからなかった。
予選を確実に通過するのが目標だったため、問題1~5を確実にとれるように何度もソースや提出したファイルなどを確認した。
だから提出ミスなどはないと思う。
予選受ける前は「予選落ちはマジ笑えねぇ怖すぎ」と思っていたけどどうやらとおりそうなので安心する。
Youtubeで若干音楽を聞く。
競技時間終了。
twitterをすぐ見る。
ボーダー6完とかいうハラスメント発言に絶望。
以上です。
終わりに。
本選はがんばるし・・・
