予選
去年予選落ちして今年通過できるかわかんないなあ状態で予選はドキドキだった
JAG夏合宿で二分探索の問題を解いたおいたおかげか、予選AのD問題で方針が立って全完出来て無事通過できた
1日目
早めに会場入りして交通費精算列を回避した
去年のCODE THANKS FESTIVALで会った人と会場で再会する。予選通過できてよかったですね、みたいなことを言い合ってた
パーカーラインは5完で5完したいなあと思う
ネットワークのトラブルがあって開始が延期したものの始まる
A問題
やるだけな問題があって安心する
int main() { string S,T,U; cin>>S>>T>>U; if(S.size()==5&&T.size()==7&&U.size()==5) cout<<"valid"<<endl; else cout<<"invalid"<<endl; return 0; }
B問題
解法がピンと来なくて焦る 多分どこかに偏るだろうから実験すればいいみたいな気持ちになって実験したら規則性が見えて投げる
int main() { cin>>N; int ans=7; if(N==1) { cout<<"1"<<endl; return 0; } rep(i,N-2) { if(i%2==0) ans+=3; else ans+=4; } cout<<ans<<endl; return 0; }
C問題
多分貪欲？みたいな気持ちになって貪欲を書くけど通らない
落ち着いて自分のやりたいことを整理して書き直すと通った
int N; int cnt; string s; int main() { cin>>N>>s; rep(i,s.size()-1) { if(s[i]==s[i+1]) { //cout<<i<<endl; cnt++; } else i++; } cout<<(cnt+1)/2<<endl; return 0; }
D問題
結構すぐに区間加算と区間最大値を計算出来たらいいことに気付いてkagamizさんのブログからソースを引っ張ってくるけどサンプルが合わない
原因は[r,l)の初期値ミスだった。ちゃんと理解していないとダメだなあって感じ
using lint = ll; const ll MAX_SIZE = 1<<20; lint segMax[MAX_SIZE - 1], segAdd[MAX_SIZE - 1]; // http://kagamiz.hatenablog.com/entry/2012/12/18/220849 //区間[a, b)に値xを加算する. void add(int a, int b, int x, int k = 0, int l = 0, int r = 1<<19) { if (r <= a || b <= l) return; //もし交差しない区間であれば終える. if (a <= l && r <= b){ //もし今みている区間[l, r)が[a, b)に完全に内包されていれば segAdd[k] += x; //区間[l, r)にkを加算する. while (k){ k = (k - 1) / 2; //親の区間の最小値は, 子の区間の最小値 + 自分に一様に加算されている値 である.一様に加算される値は更新しなくて良い. segMax[k] = max(segMax[k * 2 + 1] + segAdd[k * 2 + 1], segMax[k * 2 + 2] + segAdd[k * 2 + 2]); } return; } add(a, b, x, k * 2 + 1, l, (l + r) / 2); //子の区間に(必要があれば)xを加算する. add(a, b, x, k * 2 + 2, (l + r) / 2, r); //〃 } lint getMax(int a, int b, int k = 0, int l = 0, int r = 1<<19) { if (r <= a || b <= l) return (0); if (a <= l && r <= b) return (segMax[k] + segAdd[k]); //完全に内包されていれば,その区間の最小値を返す. lint left = getMax(a, b, k * 2 + 1, l, (l + r) / 2); //子の区間の最小値を求める. lint right = getMax(a, b, k * 2 + 2, (l + r) / 2, r); //子の区間の最小値を求める return (max(left, right) + segAdd[k]); //親の区間の最小値は, 子の区間の最小値 + 自分に一様に加算されている値 である (大切なので2回書きました!!) } ll s[100005],t[100005]; int main() { int N; cin>>N; rep(i,N) cin>>s[i]>>t[i]; ll s1=s[0]; ll t1=t[0]; rep(i,N) { add(s[i],t[i],1); s1=min(s1,s[i]); t1=max(t1,t[i]); } ll ans=getMax(s1,t1); rep(i,N) { add(s[i],t[i],-1); ans=min(ans,getMax(s1,t1)); add(s[i],t[i],1); } cout<<ans<<endl; return 0; }
E問題
貪欲に縮約していけばいいのかな？→C問題と同じような発想だけど大丈夫か？？みたいになる
WAもらう→1から書き直す→WAもらうみたいなことを繰り返した後に3ケースだけWAになってそこからサブミットデバッグして通した
void ope1(string &s) { string t; int cnt=0; rep(i,s.size()) { if(s[i]=='-') { cnt++; } else { t+=string(cnt%2,'-')+s[i]; cnt=0; } } s=t; } int cnt_s(string s,char c) { int ret=0; rep(i,s.size()) if(s[i]==c) ret++; return ret; } int main() { string s; cin>>s; int cnt=cnt_s(s,'!'); if(cnt<1) { int cnt2=cnt_s(s,'-'); s=string(cnt2%2,'-'); cout<<s<<endl; return 0; } string ans; rep(i,s.size()) { if(s[i]=='!') { ans=s.substr(0,i); if(cnt%2==0) ans+="!!"; else ans+=string(cnt%2,'!'); break; } } ope1(ans); cout<<ans<<endl; return 0; }
残り30分ぐらいでG問題を考えてたけど全く方針が立たず終わり
5完136位でギリギリパーカーゲット
ペナルティなしだったからか雑にコード書いて投げてWAもらって結果的に時間がかかるみたいなことがあったからもうちょっと慎重にやるべきだった
あと半年ぐらい前から同じような雰囲気の壁を感じているのでどうにか打ち破りたい
トークライブ
けんしょーさんと秋葉さんのを聞いた
AtCoderは普段利用はしていたけど内部事情は全然知らなかったんだなと感じられた
秋葉さんのペアプロは、オイラーツアーという単語は聞いたことあったけどどういうテクニックでどう使うかは知らなかったので勉強になった
エキシビションマッチ
Mi_Sawaさんのvimがライブラリを自動的に挿入する機能があったりUndoの履歴を見ることが出来たりしてすごいなあと思った。1時間で全完するrngさんがヤバだった
夜
去年、CODE THANKS FESTIVALで会ったmatsu7874 さんに晩ご飯に行きましょうと誘われる。ご飯食べながら今日の問題とか作問について話した。
学校の人とそこまでコアなことを話す機会がないからとても楽しい時間だった。
スタンプラリーでギリギリタンブラーを狙える位置だったらしく明日はスタンプを集めようと決める
2日目
朝プロ
すごい雑になっていてA問題からWAを連発してつらかった。D問題のLCSも全く見抜けず3完59位で終了。
悔しい90分でした...
トークライブ
ちょくだいさんとりんごさんのトークライブに行った
最近問題に対してどういうアプローチをして解くかみたいなことを意識するようにしていて、ちょくだいさんのトークライブはそれと被っていて後ろ盾を得たようでよかった
りんごさんのトークライブは、流石という感じでとても楽しく聞かせてもらいました
早解きリレー
順位のmod 20が16だったので、チーム16だった。チーム名は16にちなんで2^2^2になった
問題の担当はD問題で、問題文を読んだけどいまいち解法がわからずcatupperさんに解法を尋ねると、「等差数列だから2n」だと一瞬で返ってきてレベルの差を感じながらもそれが正しくAC
チームとしては最後の問題が1ケースだけ通らずサブミットデバッグしてギリギリ通せた。通した瞬間はとても盛り上がった
閉会式
色んな人が表彰されていた
きゅうりさんのフリー素材がまた増えるなあと思った
このオンサイトをするためにたくさんお金がかかっているだろうなあと参加中ずっと思ってた
来年も開催されるなら絶対に参加したいと思うし、運営の方々ありがとうございました。
