上の記事の数式が壊れてて式を追うのに時間がかったから、忘れないようにメモ
で
をかけて
をかけて
初参加でした
CODE THANKS FESTIVALの会場で会ったことのあるomu さんと再会する。
一緒にチームを組もうという話になって組むことになる。div1:div2を1:2で組みましょうみたいなことを運営の人に言われる。div1の人を募集した結果Mi_Sawaさんがチームに加わることになる。チーム名は全員のHNを合わせた omu_sawa_dan になる。
チーム方針をどうするか話してる時にMi_Sawaさんは普段US配列のキーボードを使用していることがわかる。その結果、Mi_Sawaさんが解法考える人になると宣言する。
コンテストが始まる。
僕がテンプレートを打ち込み、その間に2人が問題を読むという形に。打ち終わる。
omuさんがAを書き始める。
Bを読む。sortして累積和取って二分探索すればいいのがすぐわかる。Mi_Sawaさんに考えた解法を伝えると、もっと簡単な解法があることを教えてもらう。
Aが通らないらしく、印刷してパソコンを交代する。Bを書いて投げる。WAをもらう。印刷してパソコンを交代する。
今の解法だと配列の大きさが64bit分ないとダメだから、sortして累積和取って二分探索の方でいこうと言われる。パソコンを交代する。境界条件面倒って言いながら書く。投げる。通る。
Cを読む。DFSして最小値見つけて掛け算すれば良さそうとわかる。それをMi_Sawaさんに伝えるとUnion-Findを使うほうが楽だと教えてもらう。
Aが通る。Cを書き始める。を投げたけど通らない。次数の下げ方を教えてもらって下げる。投げる。通る。
Dの解法をMi_Sawaさんに解説してもらう。第一段階としてTLE解法をomuさんが実装することになる。その後オーダーを下げる方法を教えてもらいながら僕が実装する。投げる。通る。
EもDPで解けると言われる。解説を聞くが頭が足りないので理解できない。言われるがままに実装する。バグを取る。終了30秒前になってて慌てて提出する。一発で通る。
Mi_Sawaさんプロだった。何度も同じことを質問したけど毎回優しく答えてくれました。人間的にもプロだった。
この日は5時間セットでdiv1とdiv2は混合しないようにチームを組むことになった。
くじ引きの結果、YuZakuroさんとししゃもさんとチームを組むことになる。チーム名はhopping_heartsになった。両方面識のある人だったから気が楽になる。
チーム方針を話している時にある問題が浮上する。それぞれの普段のプログラミング環境が
僕 | YuZakuroさん | ししゃもさん | |
---|---|---|---|
OS | Windows | Linux | OS X |
キーボード | JIS配列 | Dvorak配列 | US配列 |
と全く異なることがわかる。つらい。
コンテストが始まる。
マクロを打ち込む。打ち終わったあとにYuZakuroさんがBはやるだけ宣言をしたのでパソコンを交代する。
Cを読む。ワープする順番は関係ないから、まとめて右に行ったあとにまとめて左に行けばいいと思い、DPで解ける気がする。
Aを投げるけどREする。印刷してししゃもさんにパソコンを交代。ししゃもさんがAを実装する。
Bのコードを読んで配列外参照してるところを見つける。ここ直したら通るだろうってことになる。
Aが難しいらしい。印刷してパソコンを交代する。YuZakuroさんがBを修正して提出する。通る。
YuZakuroさんとししゃもさんにAを任せてCをDPで実装する。投げる。通らない。
印刷してYuZakuroさんにパソコンを譲る。Aが通る。
Dは実験して周期性を見つけて周期ごとにまとめれば良いってことになる。愚直に1日ずつ進める関数を書く。400年周期であることがわかる。実装をししゃもさんに任せて、YuZakuroさんとCを考える。
YuZakuroさんが大きく左右にワープするパターンで落ちることを発見する。
似たような問題を幅優先で解いたことを思い出す。これも幅優先ではと思い始める。
Dがなんかバグっててサンプルが通らないのでパソコンを交代する。Cを幅優先で書く。サンプルが合わない。YuZakuroさんにバグを直してもらう。投げる。TLEする。dijkstraと同じでpriority_queueを使えばいい気がしてくる。queueをpriority_queueにして投げる。通る。
ここで残り1時間ぐらい。
Dのバグ取りに残りを使うことになる。
printfデバッグでバグを探す。曜日判定を行っている
365*y+y/4-y/100+y/400+153*(m+1)/5+d-428;
でオーバーフローしてることがわかる。元々経過日数を計算する式だけど、欲しいのは経過日数の剰余だから途中で剰余とっても問題ないよねってことで式をいじる。サンプルが合う。投げる。通る。
自分が担当したCに時間をかけすぎた...。Eはローリングハッシュ使うんだろうなと思ってたら案の定だったから本番でもっと考えたかった。
チームの人にコード見てもらってバグを修正してもらうのはチーム戦って感じで良かったです。
懇親会のあと会津大の人と信州大の人と一緒に銭湯に行きました。色々お話して勉強になりました。
一日目と同じくdiv1,div2混合チームにしましょうということになる。
くじ引きの結果、わにさんとぬまさんとでチームを組むことになった。僕以外の二人がMacだったため、チーム名はMacLoversになった。わにさんとは二日目の夜に銭湯に行った時からチーム組めたらいいなと思っていたので組めて良かった。
コンテストが始まる。
わにさんがA、僕がB、ぬまさんがCを読む。
わにさんがAを実装する。投げる。通る。
Bを誤読してて解法がわからない状態だった。わにさんに相談した結果誤読が判明する。Bを実装する。タイプミスしまくる。30分かかる。サンプル一致する。投げる。通る。
Cをぬまさんが実装する。その間にわにさんとD,Eのについて話し合う。
ぬまさんがCを通す。
Dは拡張ダイクストラで解けると思い、実装する。サンプル一致しない(今思うと始点をデクリメントしてなかったせい)。
ぬまさんに、郵便物に関係する頂点について普通のダイクストラして、その後に配る順番を総当りすればいいと言われる。総当りパートをぬまさんが実装する。わにさんのEの解法を聞く。難しそうと感じる。
ぬまさんが総当りパートを実装し終えたので、ダイクストラパートとくっ付ける。投げる。通らない。
INFを10回以上足していることに気付く。intをlong longに変更する。投げる。通る。
コンテストが終わる。
Cは実装重たいって言いながらスッと通したり、Dの総当りパートを実装したぬまさん強いなあと思った。
わにさんがFについて正しい解法を思いついていて、時間があったら解けてた気がする。悲しい。
立命館合宿とても楽しかったです。運営側、作問側の方々ありがとうございました。
ちょっと勉強したのでメモ
を定数、長さの文字列をとすると で計算される値をローリングハッシュと言うらしい
での部分文字列のローリングハッシュの値は で計算できる
また、長さの文字列を後ろにくっつけた時のローリングハッシュの値は、で計算できる
ハッシュ値の衝突についてはハッシュを衝突させる話
衝突を起こらないようにするには、複数のmodで計算するのがいいらしい
AOJ2444
Codeforces Round0291 Div2 C
http://d.hatena.ne.jp/say_hello_to_okaoka/20140204/1391484891
http://algoogle.hadrori.jp/algorithm/rolling-hash.html
http://kmjp.hatenablog.jp/entry/2015/02/15/0900
あり本第二版には載ってるらしい。購入しないとなあ
来年は予選通らねば...
6完+部分点で630点7位
6完+部分点で630点7位でした
— odan (@odan3240) 2014, 12月 7
開始から5秒ぐらい問題が閲覧できなかったけどあれは何だったんだろう
int A,B; int main() { cin>>A>>B; cout<<A*4+2*B<<endl; return 0; }
A→B→Cの順に固定だと思ってた
マイナスにしてソートするの便利
int N; int A[3]; int main() { cin>>N; cin>>A[0]>>A[1]>>A[2]; int sum =0; int ans =0; int count=0; rep(i,3) A[i]=-A[i]; sort(A,A+3); rep(i,3) A[i]=-A[i]; while(1) { sum+=A[count]; ans++; count++; count%=3; if(sum >= N) break; } cout<<ans<<endl; return 0; }
int N,M; int P[102]; int S[102]; int main() { cin>>N>>M; rep(i,N) cin>>P[i]; rep(i,M) cin>>S[i]; int ans = 0; rep(i,M) ans+=P[S[i]-1]; cout<<ans<<endl; return 0; }
if書いてる途中でmax,min使えば出来そうなことに気付いたけどそのままifで提出した
int N,Q; int a[100005]; int b[100005]; int s[100005]; int t[100005]; int main() { cin>>N>>Q; rep(i,Q) cin>>a[i]>>b[i]>>s[i]>>t[i]; rep(i,Q) { int ans = 0; if(b[i]<=s[i]) ans=t[i]-s[i]; else if(t[i]<=a[i]) ans=t[i]-s[i]; else if(a[i]<=s[i]&&t[i]<=b[i]) ans=0; else { if(a[i]-s[i]>=0) ans=a[i]-s[i]; if(t[i]-b[i]>=0) ans+=t[i]-b[i]; } cout<<ans*100<<endl; } return 0; }
Eと比べて問題文短いし簡単そうだったのでこっちから解いた 初めはUnionFindかな?とか考えていたけど、上がって下がるパターンも数えることになってダメだと途中で気付く 辺貼って舐めた
int N,M; int a[55],b[55]; vector<int> G[55]; int dfs(int s,int t) { queue<P> que; que.push(P(s,0)); bool flag[55] = {}; while(que.size()) { P p = que.front(); que.pop(); int v = p.fr; if(flag[v]) continue; flag[v] = true; if(p.fr==t) return 1; rep(i,G[v].size()) { int e = G[v][i]; que.push(P(e,p.sc+1)); } } return 0; } int main() { cin>>N>>M; rep(i,M) { cin>>a[i]>>b[i]; G[a[i]].pb(b[i]); } int ans = 0; rep(i,N+1) { if(i==0) continue; if(dfs(i,1)==1) ans++; } cout<<ans<<endl; return 0; }
シミュレーションするだけではと思い込んでO(N2 RC)を投げてしまう
TLEする
累積和の部分をいもす法して投げたら通る
コンテスト後に1位の方が言っていたけど、ちゃんと計算量の見積もりしてからコード書かねば
int R,C,M; int N; int r[2][5050]; int c[2][5050]; int grid[55][55]; void init() { rep(i,55) rep(j,55) grid[i][j]=0; } void rote(int a) { grid[r[0][a]][c[0][a]]++; grid[r[0][a]][c[1][a]+1]--; grid[r[1][a]+1][c[0][a]]--; grid[r[1][a]+1][c[1][a]+1]++; } void imos() { rep(i,R+1) { rep(j,C+1) { if(j!=0) grid[i][j]+=grid[i][j-1]; } } rep(i,R+1) { if(i==0) continue; rep(j,C+1) { grid[i][j]+=grid[i-1][j]; } } } int count() { int res = 0; rep(i,R) rep(j,C) if(grid[i][j]%4==0) res++; return res; } int main() { cin>>R>>C>>M; cin>>N; rep(i,N) cin>>r[0][i]>>r[1][i]>>c[0][i]>>c[1][i]; rep(i,N) r[0][i]--,r[1][i]--,c[0][i]--,c[1][i]--; init(); rep(i,N) { rep(j,N) { if(i==j) continue; rote(j); } imos(); int c = count(); if(M==c) { cout<<i+1<<endl; } init(); } return 0; }
1つ前の席の状態を持ってDPかな?と思って書いたけど、サンプル段階でダメと気付く
よく考えて実装に移らないとダメ
部分点だけ取りにいった
この時点で4位で、この問題の部分点取れば5位以上にはなるかなとか思ってた
結果部分点すらバグった
計算量の見積もりとか、よく考えてから実装に移るとか、色々出来てないことがわかった
あと、普段のコンテストでは上位陣の正解状況を見て次の問題を選ぶってことができるけど、今回はそうは出来なくて精神的につらいなあと感じました
スタッフの方々本当にありがとうございました!
お昼休みにカントリーマアムを買ったり、図書館でC++の本を借りたりで気合十分でした
4限目が16:30に終了するため競技開始ギリギリに会場に到着することに
役割分担としては、2回生の先輩がA、3回生の先輩がB、僕がCを担当すると模擬予選の時に決まっていたので、国内予選もその形に
ここで15分ぐらい
2回生の先輩がA問題をAC
C問題を読んだ僕は二分探索すれば良いだろうと考えていました
ここで60分ぐらい
3回生の先輩がB問題をAC
C問題の方針を2回生の先輩に説明したり、D問題の方針を軽く聞いていたりしました
ARCで似たような問題を解いた事があり、紙コーディングも済ませていたので10分もあればACできるだろうと思っていました
しかしコーディングしてみるもののサンプルすらあわず、頭を抱えていたら図形と円の判定が間違っていると指摘を受ける
判定を色々いじっていたら、2時間が過ぎて競技が終了していました...
C問題は二分探索が必要ないらしく、完全に間違った方針を示した僕の責任でした
後から聞くとD問題は全列挙するだけらしく、C問題を捨てる判断も必要でした
そのためにも誰かがリーダーになって役割を分担するといいねーと終了後別の先輩から指摘されました
他の方の参加記をみると、PCを専有する人、専有する人にツッコミを入れる人、問題の方針を考える人に分担すると良い(?)
チームメンバーそれぞれが互いの得意不得意とするアルゴリズムを把握していなかったことも問題だったかも
チームの先輩方にグラフを勉強すると宣言したので夏休みはグラフを勉強します!!