参加しました。
結果から言うと、237+25点くらいで95位でした。
感想は、「Easy以外クソゲー」
Easy 250
ユニークな数字が書かれたカードが複数枚与えられる。
ターン毎に、あるカードを取り、そのカードの数字±1のカードも一緒に取り除く。
その操作を繰り返してカードが無くなったら終わりだが、出来るだけ長いターン数で終わらせたい。一番長いターン数を求めよ。
最初書かれていることをそのまま実装しようとしたけど、途中で貪欲解法でいけることに気づき修正。
そりゃ、「1,2,3」とかいうカードがあったとして、2を取るより、1か3を取った方がいいのは明らかだよね。「1,2,3,4,5」とかについてもこの方法で取っても、結局手数変わらないことを確認してsubmit。
やるだけじゃないEasyで面白かった。
プラクティスで通した少し綺麗なコード
#include <iostream> #include <vector> #include <algorithm> using namespace std; class SRMCards{ public: int maxTurns(vector <int> cards){ sort(cards.begin(),cards.end()); int ans = cards.size(); for(int i=0;i<cards.size()-1;i++) if(cards[i+1] == cards[i]+1)i++,ans--; return ans; } };
Medium 500
何この問題。マフィア？知らんしそんなゲーム。
10分くらい睨めっこしても題意掴める気しなかったので捨てる。
Hard 1000
あれ英文シンプル解ける気する！！
→・・・なにこれむずくね？
→入力5000,0000とか与えられるし数学的解法だろ・・・。
→(ひたすら悩む・・・)
→なぜかn=100500なことに気づく。
→あれ、列挙するの201000コだけじゃね。でも最大(5*10^8)^100049って普通の多長長じゃキツすぎる桁だろ。
→劣悪多倍長しか持ってなかったので剰余を用いた嘘解法しよう(ひとつじゃ不安だからたくさん余りに使う値を用いよう。)
という投げやりな方針に基づき、100コくらいINT_MAXから順にでかい素数生成してテーブルつくってTLEギリギリの回数回す作戦。
→提出。
Challenge
とりあえずjavaの多倍長なら通るんじゃねとかいう意味不明な推測に基づいてjavaを恨みながら過ごす。1000点はよく分からないので250の穴を探す。
→250で配列外参照してそうなコードを見つける。
→してみたらvectorの余分に値取る仕様によって失敗して死亡(笑) -25.0
→{1}で落とせそうなケース探す→あった→落とす。+50.0
自分の1000点が6回くらいブロック成功してることに気づく。
ここで初めて、もしかしてこの嘘解法通るかもという期待を抱き始めていた。
あと「pray for japan」とか言われた。ありがとう。
System Test
1000点落ちた、やっぱりな！
でも通ってる人のコード見てるとみんな嘘解法というかハッシュ解法で、「これ運ゲーじゃねクソゲーじゃね」とか愚痴りまくる。
多分javaの多倍長解法はTLEなんだろう。
それでもなぜか2桁順位。チャレンジが利いたかな。
Result
237.18 + 25.0 = 262.18 で division95位。部屋2位。←(あの配列外チャレンジなきゃ一位だったのに！！)
とりあえずこの回で部屋2位はとっても悔しいなって。
レート:1095→1162(+67)
ちなみに1000点、あとで部屋で同じソース提出してみたら、ケース200番目くらいで唯一落ちてました。かなり悔しい。
1000点の想定解が気になるところ。ハッシュだったらレベルを上げて物理で殴る。
何にせよ、結構今回のSRM不評で言っちゃ悪いけど500回目にはあまり相応しくないと僕は思いました。僕は。
(多分素因数分解解法が正しいらしいよ!id:JAPLJさんが解説書いてます。)
→TopCoder SRM 500 Div2 1000 -- GeometricProgressions - Wrong Answer -- japlj - TopCoder部
