JOI参加記をさぼっていますが。UTPC2011参加しました。無理ゲーだった。いつもの形式で書く。
問題文はこちら: 404 Not Found
(ネタバレいやな人は見ないように)
[00:00] コンテスト開始
A読む。やるだけ過ぎて不安になったので念入りに入力制限等をチェック。
[00:02] A Accepted.
これは埼玉の大学ではなく東京の大学のコンテストだったということを改めて認識する。
B読む。
→O(n)やるだけ？
→奇数の時だけ気をつけよう。
→ややバグ取りに苦労しながらも提出。遅かった・・・。
[00:06] B Accepted.
C読む。
→条件を満たしていて作れるstringの数か。←ちがう
→どうしようかな・・・悩む。
→2^15やん！全探索やん！
→iwiが複数ある場合とかiとかwが他にある場合めんどいな←問題文読め
→実装バグりまくって泣きそうになる。ここで時間掛けまくる。
→出来たと思ったらサンプル合わない。一番長いものの長さだということに気づく。
→ちょこっと弄って提出。
[00:34]C No - 0 % Scored
バグ死しまくった上の提出かつ、ケース別全部WAして絶望する。
→問題文勘違いしていることにここらへんで気づきまくる。
→それでも問題ないプログラムだったので、悩みまくる。
→適当なケース作ってみても正しく動作している感じがする。
→デバグコードがそのままだった・・・・っ。
[00:50] C Accepted.
出遅れた感はんぱないと思いつつも、Dを開く。
→うわなんか面倒くさそう。
→Eを読んで解けそうだったのでそっちに。
→まずB[i]でソートするのは良いとして、そこからどうするか悩んでいた。
→上手いDPが思いつかず時間だけが立っていくので、手計算するならどうするかを考える。
→O(n^2)のナップザックっぽいの思いついて書く。
→提出。
[01:27]E No - 0 % Scored
ACが少しとほとんどがRE(実行時エラー)している！なぜだ！悩む。
→制限はオーバーしていないっぽいので悩む。
→DPが間違っているのか不安になるが反例が見つからないので別の原因探す。
→それっぽいのは見つからない。
→とりあえずlong longに書き直してreturn 0;してみる。
[01:33]E No - 0 % Scored
REは消えてACも増えました。がWAが1/3くらい発生する。悩む。
→DPの実装少しだけ間違えていることに気づく。
→修正。
[01:39] E Accepted.
やったー。Dやろう。
→実装思ったより大変じゃないような。
→とりあえず全く同じ状態(座標,メモリ,方向)が再び訪れてかつ'@'にたどり着けないならNOなので実装。
→'?'の存在に気づく。
→あわてて幅優先に書き直す。
→サンプル通った！提出。
[02:00]D No - 0 % Scored
マジかよ。1/2くらいWA。実装問題でこれはヤバイ。
→幅優先のノード追加間違えていることに気づく。修正して提出。
[02:01]D No - 0 % Scored
あいかわらずのWA。しかもケース別WA減らず。別の原因を考える。
→座標の余りのとり方を間違えている!( (x+w+1)%wってしたいのに(x+h+1)%wとかしてた。
[02:11]D No - 0 % Scored
くそったれー！
→|の時の動作が逆ということに気づく。修正。
[02:14] D Accepted.
ぽぽぽぽーん。
→F読む。
→難しい気がする。
→いろいろ考えた末に適当に貪欲にぐちゃぐちゃしていく嘘解法を1時間くらいかけて書く。
[03:14]F No - 0 % Scored
部分点すら取れなかった。
→ここでn≦8ケース埋め込みしようかと思ったけど、諦めて別の問題へ。
→H読む。
→貪欲法とか出来そうな気がしてきて実装。
→サンプルで早速反例が発生。
→長時間いろいろ考えたけど思いつかないので適当にダイクストラをして20点取る作戦に出る。
[04:36]H No - 20 % Scored
まあ、満足。
→Gとか読む。三角形・・・？
→n=100,超ただの総当りでいけない感じなので悲しい。
→発想ゲーなんだろうけど時間無いし思いつかないので諦める。
[05:00] コンテストいずおーばー。
UTPCむずかしい・・・。
結果
5完+オマケで、
得点520 / ペナルティ690分
39位/159人
最悪でもないけど、決してよくもない感じ。
感想
- Hは簡単そうに見えて最小費用流とか必要らしくて難しいらしかった。
- 手を出していない他の問題はコード生成したり、無茶サイズの巡回セールスマン(ただ解けるように制約はある)だったりぱなかった。
- 問題文がだんだんとおかしい方向に進んでいくのが面白かった。
- 良問多かった。
教訓
問題を読みましょう。
ソースコード
解けたやつだけ。
A
int main(){ int n,m; int ans = 0; cin >> m >> n; rep(i,m){ int sum = 0; rep(j,n){ int a = 0; cin >> a; sum += a; } ans = max(sum,ans); } cout << ans << endl; }
B
int main(){ string s; cin >> s; int n = 0; rep(i,s.size()/2){ if(s[i] == ')'){ if(s[s.size()-1-i] != '(')n++; }else if(s[i] == '('){ if(s[s.size()-1-i] != ')')n++; }else{ if(s[i] != s[s.size()-1-i])n++; } } if(s.size()%2){ if(s[s.size()/2] == ')' || s[s.size()/2] == '(')n++; } cout << n << endl; }
C
string t1 = "iw({[]})"; string t2 = "iw)}][{("; bool check(string s){ if(!~s.find("iwi"))return false; int pos = s.find("iwi"); string sub = s.substr(0,pos) + s.substr(pos+3); assert(!count(all(sub),'w')); assert(!count(all(sub),'i')); rep(i,s.size()/2){ if(s[s.size()-i-1] != t2[t1.find(s[i])]){ return false; } } return true; } int main(){ string str; cin >> str; int mx = 0; for(int i=0;i<(1<<str.size());i++){ string s; rep(j,str.size()){ if(i>>j & 1){ s += str[j]; } } if(check(s)){ mx = max<int>(s.size(),mx); } } cout << mx << endl; }
D
struct NODE{ int mem,dir,x,y; NODE(int a,int b,int c,int d){mem = a , dir = b , x = c , y = d;} }; int memo[16][20][20][4]; string data[100]; bool isdigit(char c){ return c >= '0' && c <= '9';} int main(){ int h,w; cin >> h >> w; rep(i,h) cin >> data[i]; int dx[] = {1,0,-1,0}; int dy[] = {0,-1,0,1}; queue<NODE> Q; Q.push(NODE(0,0,0,0)); while(Q.size()){ NODE q = Q.front(); Q.pop(); int mem = q.mem; int dir = q.dir; int x = q.x; int y = q.y; //cout << x << "," << y << " : " << mem << " ["<< dir << "]" << endl; if(memo[mem][y][x][dir]) continue; else memo[mem][y][x][dir] = true; char c = data[y][x]; if(c == '@'){cout << "YES" << endl; return 0;} if(c == '<'){dir = 2;} if(c == '>'){dir = 0;} if(c == '^'){dir = 1;} if(c == 'v'){dir = 3;} if(c == '_'){ if(mem) dir = 2; else dir = 0; } if(c == '|'){ if(mem) dir = 1; else dir = 3; } if(c == '.'){} if(isdigit(c)){mem = c-'0';} if(c == '+'){mem = (mem+1) % 16;} if(c == '-'){mem = (mem+15) % 16;} if(c == '?'){ rep(i,4) Q.push(NODE(mem,i,(x+dx[i]+w)%w,(y+dy[i]+h)%h)); }else{ Q.push(NODE(mem,dir,(x+dx[dir]+w)%w,(y+dy[dir]+h)%h)); } } cout << "NO" << endl; return 0; }
E
int main(){ int n; cin >> n; rep(i,n) cin >> a[i] >> b[i]; // bubble sort for(int i=0;i<n;i++){ for(int j=0;j<n-1;j++){ if(b[j] > b[j+1]){ swap(b[j],b[j+1]); swap(a[j],a[j+1]); } } } //rep(i,n) cout << a[i] << " " << b[i] << endl; rep(j,2)rep(i,1001) dp[j][i] = INF; dp[0][0] = dp[1][0] = 0; int p = 0; rep(i,n){ rep(j,n+1) dp[p][j] = dp[p^1][j]; rep(j,n+1){ if( dp[p^1][j] + a[i] <= b[i]) dp[p][j+1] = min(dp[p^1][j+1],dp[p^1][j]+a[i]); } p^=1; } //rep(i,n+1) cout << dp[p^1][i] << endl; int ans = 0; rep(i,1001){ if(dp[p^1][i] != INF)ans = max(i,ans); } cout << ans << endl; return 0; }
H
(部分点解法です。)
class NODE{ public: int cost,cur; vector<int> v; NODE(int a,vector<int> d,int c){ cost = a , v = d , cur = c; } }; bool operator < (const NODE &a,const NODE &b){ if(a.cur != b.cur) return a.cur < b.cur; return a.v < b.v; }; bool operator > (const NODE &a,const NODE &b){ return a.cost > b.cost; }; int main(){ int n,m,k; cin >> n >> m >> k; vector<int> w(m) , x(k); rep(i,m) cin >> w[i]; rep(i,k) cin >> x[i] , x[i]--; vector<int> s(n,-1); map<NODE,bool> done; priority_queue<NODE,vector<NODE>,greater<NODE> > Q; Q.push(NODE(0,s,0)); while(Q.size()){ NODE q = Q.top(); Q.pop(); if(done[q])continue; else done[q] = true; //rep(i,n) cout << q.v[i]+1 << " ";cout << " [cost:" << q.cost << ":" << q.cur << "=" << x[q.cur] << endl; if(q.cur == k){ cout << q.cost << endl; return 0; } if(count(all(q.v),x[q.cur])){ Q.push(NODE(q.cost,q.v,q.cur+1)); }else{ rep(i,n){ NODE next = q; next.cost += w[x[q.cur]]; next.v[i] = x[q.cur]; next.cur += 1; sort(all(next.v)); Q.push(next); } } } }
