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

Marathon Match 93

縦横隣接でグループ化、同じ頂点複数回通れる巡回セールスマンと捉えて(正確には違うが最低二回は通れる)近傍を2.5-optとinsert/eraseで焼きなましした。

順位は今の所38位でなんか思ったよりスコア伸びんなあと思ったけどよくよく考えると

o.o

oo

が同様に遷移コスト1なのを見落としていた。これは致命傷では?
これを考慮するためにはグループ化しないで焼きなました方が良かったかも。

全体的に見落としてることが多すぎてダメダメだった。
次はもっといい順位を、と言いたいところだが時間作れるかわからないのでなんとも。
まあバイトも辞めたしなんとかなりそうではあるが。

あと焼きなまし法のパラメータ調整めっちゃむずいなあと思った。
今回は診断人さんのブログとか見て見よう見まねでやってしまったが、次回に備えてもっと自分で考えてできるようにしておきたい。次も焼きなましとは限らないけど、まあTCOで一回は出るだろうし。

AGC011

またダメだった……

Cはもとのグラフの連結成分に閉路がなければ二部グラフになると思ったんだけど何が違うだろう……

と思ったら閉路が遇数長だと戻ってこれないのね……
想 定 誤 答って感じで辛いなあ。




今回は考察が甘かった。
反省。

[追記]
http://agc011.contest.atcoder.jp/submissions/1160296
これが95ms
VecDequeのpop_front&push_backをpop_back&push_frontに変えると138ms
usedの宣言をlambda内で行うとなんとTLEした。
Rustはメモリ確保速い印象あったから以外だ。
まあ最大100000 / 3回くらい呼び出されるので仕方ない気もするが、TLEするほど遅いとはね。

Wine2.1以降でBaldr Sky DIVE2が起動できない問題

※これは症状をメモしただけで、現時点では何も調べていないので何の参考にもならないと思う

fixme:win:RegisterDeviceNotificationW (hwnd=0x128000, filter=0x64e8bc,flags=0x00000001) returns a fake device notification handle!

の後
「入力デバイスを初期化できません」
というモーダルが出る。

恐らく内部でAPIの呼び出しが失敗したら終了、としているのだろう。
wine1.7.55では動作すること、wine2.1以降のすべてのバージョンで動作しないことを確認している。
とりあえずバグ報告のためにはどのバージョンから動かないのか確認しなくてはいけないが、面倒なので暇になったらやろうと思う。
バージョンが多すぎるから正直辛い。
ちなみに、(上述の通り動作するバージョンは詳しく確認していないが)1.7.55等では
・Dive1 & 2を同時インストール
・公式パッチを適用(なくてもプレイはできるが、あった方がいい)
・Dive2のreg.exeをnodisk化
・Dive2のBaldrSky.exeを起動(dive1の内容もdive2からプレイできる)
という手順を踏むことで普通にバルドスカイをプレイすることができる。キーボードに限界を感じたので途中からXbox360の有線コントローラーを導入してみたが、これも普通に動作する。windowsで遊ぶときの3倍くらいの頻度で落ちるのと……。
Dive1のreg.exeはwineで動かすと信じられんくらいバグるのでDive1だけ遊びたいという場合は少々キツいかもしれない。
また、wineから起動したreg.exeがdvdromをきちんと検出したのを僕は一度も見たことがない。製品コードを入力すれば起動時のディスク確認が回避できるゲーム以外はたいていnodisk化が必要になる。

SRM 710 div1easy

例のごとくeasyしか開いていないが全くわからなかった。
http://codeforces.com/blog/entry/50572にwriterさんがヒントとかを書いてくれたので見たが、一箇所に集めるというのは全然思いつかなかった。
x[0]以外のところで操作してたらそのうち集まるっていうことらしいが。
むう。

コンテスト中は辛い思いをしたが、面白い問題だった。