思い出の問題を解いた
ICPC2013国内予選Cの 階層民主主義 ( Hierarchical Democracy | Aizu Online Judge )を解きました。
2013年7月 ICPC国内予選
興味本位で出たICPC国内予選でこの問題を読み、全くもって意味がわからなかった。*1
当時は プログラミングチョットデキル と天狗になっていただけに衝撃で、なんかもやもやしたので競技プログラミングを始めることにした
問題について
問題概要は省略。
解いてからググったら深さ優先でやるのが一番スマートみたいだったけど、思いつかなかったからゴリ押しで地獄のようなコードを書いた。ゴリ押しの手順を以下に雑に示すが、おそらく読む価値はない。※括弧内は一例
- はじめ ( [[[1][3][5]][[11][9][7]][[15][17][13]]] )
- "]["を" "に置き換える ( [[[1 3 5] [11 9 7] [15 17 13]]] )
- 一番深い階層の選挙区それぞれを有権者数でソートする ( [[[1 3 5] [7 9 11] [13 15 17]]] )
- それぞれの選挙区で勝つために必要な票の最小を求め、置き換える ( [[3] [9] [15]] )
- 空白をつめる ( [[3][9][15]] )
- 2~5を繰り返し、'['や']'が無くなったらそのときの結果を出力する ( [[3][9][15]] → [[3 9 15]] → [12] → 12)
手もつけられなかった問題が、ゴリ押しではあるが一応通せるようになって少しうれしい。
string pre(string s){ // "][" を空白に置き換え string b=""; rep(i,s.sz-1){ if(s[i]==']' && s[i+1]=='['){ b+=' '; i++; } else{ b+=s[i]; } } b+=s[s.sz-1]; return b; } string solve(int n,bool check,string s){ n++; string tmp[10000]={}; int count=0; REP(j,n,s.sz){ if(s[j]!=']'){ if(s[j]!=' '){ tmp[count]+=s[j]; } else{ count++; } } else break; } vi a; rep(i,count+1){ a.pb(stoi(tmp[i])); } sort(ALL(a)); int sum=0; rep(i,count/2+1){ if(check==false) sum+=a[i]/2+1; else sum+=a[i]; } return to_string((sum)); } string delSpace(string s){ // "] [" を "][" に置き換え string ret=""; rep(i,s.sz-2){ if(s[i]==']' && s[i+1]==' ' && s[i+2]=='['){ ret+="]["; i+=2; } else{ ret+=s[i]; } } ret+=s[s.sz-2]; ret+=s[s.sz-1]; return ret; } int main(){ int t; cin>>t; rep(times,t){ string s; cin>>s; int check=false; s=pre(s); while(1){ if(s.find("[",0)==-1)break; string n=""; rep(i,s.sz){ if(s[i+1]>='0' && s[i+1]<='9'){ n+=solve(i,check,s); while(s[i]!=']')i++; } else{ n+=s[i]; } } s=n; check=true; } cout<<s<<endl; } return 0; }
*1:A問題とB問題は一緒に出ていた先輩が解きました。