id:JAPLJ回でした。今回で彼のSRMに参加するのは2回目ですが、彼は数学オリンピッククラスタとはやや違うタイプの良問を作ってくれますね。wrongだし高校生writerだし、すごい。
入室
「緑多い灰色少ない。まずいなあ」とか思う。
250 FoxProgression
少し不安になる250。
同じ値掛け算していくやつか、同じ足し算していくやつの数列に当てはまってるかどうかって問題。
それぞれ、「当てはまるような値の数を数えなさい。」みたいな。
まあ、項が1つなら-1で、それ以外定まるってのは自明で、とりあえず初項がseq[0]なものを全生成して照合するブルートフォースしました。
提出遅かったのに部屋で一番最初に提出とかしてて謎かった。
数学的な解法をしても良い気がしたけど値の範囲が小さいので。
与えられる数の範囲的に、明らかに無駄な範囲から回しているけど気にしない。
(03/31追加: 実はこのコードバグがあり、掛け算で余裕でオーバーフローしてますねごめんなさい。)
class FoxProgression { public: int theCount(vector <int> seq) { int ret = 0; for(int i=-1000;i<=1000;i++){ if(i==0)continue; bool f = true; vector<int> p(1,seq[0]); rep(j,seq.size()-1)p.push_back(p.back()*i); rep(j,seq.size()){ if(seq[j] != p[j]) f = false; } ret += f; } for(int i=-1000;i<=1000;i++){ if(i==0)continue; bool f = true; vector<int> p(1,seq[0]); rep(j,seq.size()-1)p.push_back(p.back()+i); rep(j,seq.size()){ if(seq[j] != p[j]) f = false; } ret += f; } return seq.size() == 1 ? -1 : ret ; } };
Passed System Test 224.73Pts.
500 FoxPlayingGame
とりあえず、ちょうどnA回足し算,ちょうどnB回掛け算して最大になるようなのを求める問題。
場合分け解法が一瞬思いついたけど、複雑な分岐になりそうだったのでDPしようと思った。
とりあえず[操作Aの残り回数][操作Bの残り回数][今の値がマイナスとプラスか]で状態分けて
- それぞれ最小(-の場合),最大(+の場合)になるようなDP
- とりあえず最大とりまくるDP
の二つをして、両方の最大値を取る感じでしました。DPの収束のさせ方がnA*nB回回すという超
強引な感じで、順番拘れば計算量減らせると思ったけど50^4*2なんでいいかと思いました。(※よく考えたら何もしなくても収束するので外側のnA*nBは無駄でした。)
強引に書いたのでかなり複雑になっている。読む気が失せる。
で、自分のdpだと、nAが0の時とかコーナーケースだったのでresubmitしまくって対策しまくった。(5回くらいした)
class FoxPlayingGame { public: double theMax(int nA, int nB, int paramA, int paramB) { long double ret = 0; long double sA = paramA/1000.0; long double sB = paramB/1000.0; long double dp[51][51][2]; bool done[51][51][2]; if(nB == 0)return nA * sA; else if(nA == 0)return 0; // 現在値がマイナスの場合最小を取り、現在値がプラスの場合最大を取るDP rep(i,51)rep(j,51)rep(k,2) done[i][j][k] = 0; rep(i,51)rep(j,51) dp[i][j][0] = 0; rep(i,51)rep(j,51) dp[i][j][1] = 0; dp[nA][nB][0] = dp[nA][nB][1] = 0; done[nA][nB][0] = dp[nA][nB][1] = true; long double ans = -1e20; rep(x,nA*nB){ for(int i=nA;i>=0;i--){ for(int j=nB;j>=0;j--){ for(int k=0;k<2;k++){ //その状態に今まで一度でもたどり着いたか。 if(done[i][j][k] == false) continue; // 操作Aが出来るならばする。操作後の値によって格納するところと、最大とるか最小とるかが変わる。 if(i){ long double next = dp[i][j][k]+sA; if(next < 0){ dp[i-1][j][0] = min(dp[i-1][j][0],next); done[i-1][j][0] = true; }else{ dp[i-1][j][1] = max(dp[i-1][j][1],next); done[i-1][j][1] = true; } } // 同様にしてBが出来るならする。 if(j){ long double next = dp[i][j][k]*sB; if(next < 0){ dp[i][j-1][0] = min(dp[i][j-1][0],next); done[i][j-1][0] = true; }else{ dp[i][j-1][1] = max(dp[i][j-1][1],next); done[i][j-1][1] = true; } } } } } } if(done[0][0][0]) ans = max(ans,dp[0][0][0]); if(done[0][0][1]) ans = max(ans,dp[0][0][1]); // とりあえずmax取るDP。 よくわからないけど書いたらサンプル通ったのでこれでいいかという感じに。 rep(i,51)rep(j,51)rep(k,2) done[i][j][k] = 0; rep(i,51)rep(j,51) dp[i][j][0] = -1e20; rep(i,51)rep(j,51) dp[i][j][1] = -1e20; dp[nA][nB][0] = dp[nA][nB][1] = 0; done[nA][nB][0] = dp[nA][nB][1] = true; rep(x,nA*nB){ for(int i=nA;i>=0;i--){ for(int j=nB;j>=0;j--){ for(int k=0;k<2;k++){ if(done[i][j][k] == false) continue; if(i){ long double next = dp[i][j][k]+sA; if(next < 0){ dp[i-1][j][0] = max(dp[i-1][j][0],next); done[i-1][j][0] = true; }else{ dp[i-1][j][1] = max(dp[i-1][j][1],next); done[i-1][j][1] = true; } } if(j){ long double next = dp[i][j][k]*sB; if(next < 0){ dp[i][j-1][0] = max(dp[i][j-1][0],next); done[i][j-1][0] = true; }else{ dp[i][j-1][1] = max(dp[i][j-1][1],next); done[i][j-1][1] = true; } } } } } } cout << dp[0][0][0] << " " << dp[0][0][1] << endl; if(done[0][0][0]) ans = max(ans,dp[0][0][0]); if(done[0][0][1]) ans = max(ans,dp[0][0][1]); return ans==-1e20 ? 0 : ans; } };
Passed System Test 150.0Pts.
1000 ???(名前覚えてない)
開くだけ開いたけどよく分かってない。
500解き終わった時点で残り20分くらいだったので、500のコーナーケース対策兼チャレンジケース生成をがんばっていました。
Coding Phase 終了
250遅かったなあとか、500はどうせ落ちるだろうし、点数かわんねえよとか気軽にresubmitした結果150Ptとかで、終了時420位でありゃりゃという感じでした。
たくさん500が落ちるのは分かっていたけど、さすがに100位くらいしか変わらないと思っていました。
Challenge Phase
とりあえずみんなの500見る。
→うわみんな数学的解法してる。誰もdpしてない・・・。nA=0ケース効かないやん・・・。
→自分数学的解法してないから間違ってるか間違ってないかとか分からない。
→分からないなーと思っていたら、ものすごい勢いで500点が落とされていく。
→最終的に自分を含めて3人くらいしか残ってなかったので泣きそうになる。(ソースが難解すぎて落とされないんだと思った。)
→さすがに250は落とさないだろうけど……と思いつつ、全員のソースを見る。
→みんな250を怪しい解き方しているが、目に見えて落としそうな人あんまいないなあ。みんなテストケースは通してるらしい。
→seq[0] == seq[1]なら無条件で1返してる人いるよ・・・
→{1,1,100}でチャレンジ成功。
→他はフラグとか使いまくって難解だったので、読めなかった。
System test
チャレンジ終了直後、順位が170位(+250位くらい)とかなっててひどく驚く。
そしてテストが始まり、続々と500が落ちる中、なぜか250も500もテスト通ってまた驚く。
そして、最終順位が55位になったところでもっと驚く。
55位って、350人近く500落としてるってことかよとか思う。
結果
予想に反しての良成績。
部屋順位: 2位/19人
Div2全体順位 : 55位/1003人
224.73 + 150.0 + 0.0 + 50.0 = 424.73
Rate:1164→1241
やったー。やっとDiv1復帰したー。(去年度末からずっと緑だった。)
感想
面白かった。500はもしかしたら典型問題なのかなとは思ったけど、やっぱり掛け算とか足し算とかで最大化しろみたいな問題は頻出なので、学ぶ必要があると思いました、まる。
今までdpとか全く出来なかったのに、去年のJOI予選以降少しずつ出来るようになっている気がする。(それでも今回、する必要のない実装ハードな適当DPで通ったのは運だと思ってるが。)
ていうか部屋見ると10人くらい250点落としてて変な気持ちになった。コーナーケースあったのかな、きちんとコード読んで落とせば良かったなぁと思うも後の祭り。
ちなみに部屋で唯一500通したっぽくてうれしいです^^v(ただし150.0Pt)
