Topcoder SRM579 Div2
気分がいいとカーテン巻き取り機がほしくなる
-easy(250)
int i=0;
sort(v.begin(),v.end());
while(i<v.size() && n>v[i])n+=v[i++]/2;
return i;
確定Passed.
-medium(550)
文字列長L<=50、文字列数N<=50
適当に全探索してもO(L*N^2)くらい？だったので全探索。
多分見積り甘いけど全然余裕
無事Passed.
-hard(1000)
幾何だけど三平方の定理さえ知っておけばやるだけ。
今回はmediumに時間をとられたので実装間に合わなくて死。
多分medium無視して解きに行けばいけた。
Compiled.
Topcoder SRM578 Div2
一度はアメリカを食べてみたい
eazy(250)
vector<int> a(2);
a[0]=max(N-K,0);
a[1]=N-(K+1)/2;
return a;
目をつぶって書けるレベル
medium(500)
幅優先してマンハッタン距離内の鳥を1つにまとめて組み合わせの合計をmod
後で気づいたけどUnion-Findのが早い
で鳥の集合の数nを求めたらあとはこの値を返すだけ
だけどコンビネーションは途中計算する値がどうしてもintの最大値を超えてしまうし
多分最大ケースだと余裕でlong longも超える
工夫してオーバーフローしないように計算しようと思うも最後までできずにアレ
前回に続きなかなか罪深いmedium
Hard(1000)
恥ずかしがり屋なので姿を見せてくれなかった。
次に会うときに告白しようと思う。
Topcoder SRM577 Div2
深夜テンションは恐ろしい
easy(250)
文字列から、a,e,i,o,u,yのどれか2つ以上が連続しているものをカウントして、
その長さ-1を文字列の長さから引いていったものを返すだけ。
文章で伝えにくいけどやるだけの問題。罪深い。
medium(500)
ページ開いて読解に30分くらいかかる。胸アツ。
実装に手間取って20分かかる。激アツ。
デバッグするもなぜか最後のケースで落ちる。頭フットー。
inputの姑息な罠に気づく。実装しなおす。激おこ。
通らなかったケース通ったので提出。罪深い。
以下解説。
文字列から数字を得て、全部vectorにつっこむ。
最初の要素Fを保存して降順ソートしたら、
部屋数R=（vectorの長さ+19）/20ごとに、vectorの最初から数字を振り分ける。
最大の要素と、Fが同じところに振り分けられる確率を出力する。
たとえば部屋数が3で、最大の要素,F,他の要素 のような順番で並んでいたら、
この3つは別の部屋に割り振られるので確率は0
こんな感じの問題だった。本当にやるだけ。激おこぷんぷん。
Hard(1000)
鑑賞用。問題の読解が終わったら残り数分なのであそぶ。
challengeは+1/-1で+25 mediumのinputの罠にかかった人を見つけたので。
今回はちょっとﾄｩｰｲｯｸ300ちょいの人間には厳しかった。
ラドズパ
昨日は我が部主催プチプロコンである
「ズンゴラド・ドンア・ルズパ」
略してラドズパに参加した。罪深い。
ラズドパはパズルゲームらしい。
高さH幅Wの盤面に敷き詰められた6種類のシンボルを上下左右に動かすことで、
同じ種類のシンボルを縦か横に3つ以上並べることで消すことができる。
つながった同じ色のシンボルが消えることで連鎖が発生するので、
その連鎖数を競う競技となるらしい。罪深い
このラドズパはパズルゲームのAIを対決させるものであり、
原則参加権は一人一つだった。罪深い。
しかし、偶 然 に もAIを2つもっていた私は
とっさに同級生を創造してそれに出場させることでことなきを得た。危なかった。
提出したAIの名前はそれぞれ、
「そう・・・人はそれを神のいたずらと呼ぶadvanced」
「真・ザ・裏限界突破完全ファイナル超回転完成版その4～陽炎の章～another_episode入浴」
だった。以下それぞれ「神のいたずら」、「超回転」と呼ぶことにする。
どんなことをするかまるわかりの名前なので、
ちょっとネタバレっぽくなってしまったことが悔やまれる。罪深い。
私名義で提出したのは神のいたずらのほうである。
このAI、実はsampleコードとして与えられたランダムな出力をするコードを
少し書き直しただけである。罪深い。
超回転のほうは、実は本命だったのだがなぜかすごく弱くなった。罪深い。
どう頑張っても乱数に勝てないのはおかしい。
一応説明しておくと、左下から反時計回りに盤面を移動しながら4*4の領域を見て、
よさげな手を探索して動かすだけの簡単なコードだった。
4*4の領域を見たらファイルから読み込んだパターンで動かすようにしていた。
そのパターンをファイルに書きだすのに3時間近くかかったのはすごく罪深い。
AIを二つ提出したまではよかったのだが、
神のいたずらがエキシビションマッチを1位通過してしまった罪深さのせいで
1回戦で神のいたずらと超回転が当たってしまった。罪深い。
結局超回転はあっさり敗北してしまった。深い悲しみを覚える。
その後、神のいたずらは2回戦を勝ち進んで決勝トーナメント（ベスト4）までいくも
準決勝で敗退、3位決定戦でも負けて4位になってしまった。罪深い。
優勝と準優勝のAIを見ると、1度消した後に長く連鎖を続けるのではなく、
初回でできるだけ多く消すように動いていたので、
そういう感じのほうが強いっぽいらしいっぽい。罪深い。
AIは負けてしまったがすごく楽しかった。
次回は優勝の上の上を目標にして頑張りたい。
Topcoder SRM575 Div2
easyとmedium解いた。Hard読んでない。
なんか灰から緑になった。エコい。
-easy(250)
読解が若干手間取った。
要するに数え上げ。
数列の内2つの要素をスワップしてできる配列がいくつになるか数える。
全く同じ数列は数えない。
数列の長さ2<=L<=47。
とりあえずスワップした数列は(L-1)*L/2個ある。
このうち同じものを消していけばよい。
数列中の同じ要素を数えて先ほどの数から引いていく。
最後に初期値より小さくなっていたら1を足してreturn。
多分穴あるけどsample全部通ったので提出。通る。激アツ。
-medium(500)
2人で交互に整数nの約数の1つを選んでnから引いていき、
引いたときに素数になった方が勝つゲーム。
互いに最善手を選ぶ。
つまり素数にできるときは必ず素数にするので、
深さ優先的に調べれば勝ち負けがわかる。
単純に数えるとTLEするのでメモ化する。
多分DPできるかもしれないけど実力不足で思いつかない。
実装に手間取って200点ちょい。激寒。