読者です 読者をやめる 読者になる 読者になる

Topcoder SRM 500 Div2

参加しました。

結果から言うと、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位はとっても悔しいなって。

レート:10951162(+67)

ちなみに1000点、あとで部屋で同じソース提出してみたら、ケース200番目くらいで唯一落ちてました。かなり悔しい。

1000点の想定解が気になるところ。ハッシュだったらレベルを上げて物理で殴る。

何にせよ、結構今回のSRM不評で言っちゃ悪いけど500回目にはあまり相応しくないと僕は思いました。僕は。

(多分素因数分解解法が正しいらしいよ!id:JAPLJさんが解説書いてます。)

TopCoder SRM 500 Div2 1000 -- GeometricProgressions - Wrong Answer -- japlj - TopCoder部