第一回ニコ生オープン!! - simezi

第一回ニコ生オープンに参加した。
詳細は診断人さんのコミュニティ（http://com.nicovideo.jp/community/co78570）を参照。

6 rankalee 514.61

真ん中……くらい？250は問題なく解けたが、500で添字バグに20分以上はまってるあたり全然進歩がなくて鬱。
1000も単なるDPなのに結局書き終わらなかった。

みんな解くの凄くはやいなー。
僕は赤にもなれないまま一生おわるのかな。あぁ。。。

JingleとRingleという二つの通貨がある。二つの通貨の売買は以下のステップで行われる。

今、Jingleを0、Ringleを沢山もっているとする。
買い注文と売り注文が、1JingleのRingleにおける価格の形でいくつか与えられる、とき得ることのできる最大の利益を求めよ。

問題文の読解に手間取る。売買のステップがなかなか複雑だ……
というかどっちが買い手でどっちが売り手なのか混乱する。

Jingleを売って利鞘を得る為には同数のJingleを購入しなければならない。ということは……
安いJingleを買って、高く売ればいいんだな。
売り注文を昇順に、買い注文を降順にソートして、利益が出るだけ買うようにすればよい。

書く。サンプル通った。Submit.

ライフゲームにおいていくつかのセルが?に置き換わっている。
1ターン後に生き残っているセルの数が最大になるように?を置き換え、1ターン後に生き残っているセルの数を求めよ。
ただし、ライフゲームの盤の外側には更に死滅しているセルがあり、そこに新たに生物が生成しうると仮定せよ。

なお、あるセルが同時に2つ以上の?のセルに隣接するようなことはない。

問題を読む。
えーと……全探索かな？ボードのサイズが50*50のマスなので全探索では間に合わない。
同時に二つの?に隣接するセルがないんだから、greedyに求めてやればいい。

じゃあ実装。
書く。なんか実行時におちる……

ソースと問題文見直す。
うー。。。添字の順番間違ってる。

直した。
また実行時に落ちる。プリントデバッグ開始。

しかもサンプルあわないのは何故だろう。問題文を読み直す。
あ、盤の外側にも生物が生成しうるのかー。盤のサイズを拡張。
だがまだ落ちる。

20分ほどはまって結局添字に差分を足す足し方が間違っていたのを見つける。
なんかもう全然だめぽ。Submit.

まだ30分くらいある。解けますように……

badgesで与えられた数個の文字列を使って、与えられた文字列をできるだけカバーしたい。
例: HELLOを"E","HE","L"でカバーする仕方は、
"HE"-"L"-"L"や"E"-"L"-"L"などが考えられる。

各文字列は何回でも使え、隣り合わせることもできるが、文字列同士が重なってしまってはいけない。
このとき、スコアをA=(連続するカバーのうち最も長いものの長さ),B=(カバーできなかった文字)としてA^2-Bで表されるとき、最大のスコアを求めよ。

あからさまにDPっぽいけど、A^2-Bがスコアなのか。ちょっと変わってるな。
えーと？ある文字番目まで見たときに、「今までの最大連続カバー」「最後にカバーした文字」に対する最大スコアを覚えておけばいいんかなー？？

ちょっと書いてみる、いやお前それメモリも計算量もO(n^3)になって足りないだろ！

処理の終わった文字の番目と、今までの最大連続カバーだけ覚えておけばいいんだ。
書く。

サンプルめちゃくちゃ。
何が違うんだ。dpを更新する部分がおかしいと思うんだけど……
20分書き直したりして時間終了。頭わるい。。。