MM 117

Typical pseudointellectual @Nuke_name

@FakePsyho @Topcoder @CodinGame @Google @atcoder You may be able to solve it well with NNs if you make a test generator, but I'm uncertain if that's going to be the winning solution. Or if it's going to be something more heuristic. icecuber who topped the scoreboard for a long time seems to be more of a C++ rather than NN guy.

Shuichi Tamayose @_simanman

パン焼きコンテスト、1週間とは思えない問題文の量でつらい

1 @komori3_

MM117 で嵌った罠で for(auto c : {'L', 'R'}) は大丈夫だけど for(auto c : "LR") はなんか最悪なことになるやつがあった

やほーbb @yahoobb_th

@komori3_ これc="LR"で一回動いて終わりになるんですか？

1 @komori3_

@yahoobb_th { 'L', 'R', '\0' } になります……

koyumeishi @koyumeishi_

@komori3_ これは "LR" だと末尾に終端文字が入って実質 ['L', 'R', '\0'] になっているからだと思います。 string("LR") にすればおｋ ideone.com/ZFqkzl

やほーbb @yahoobb_th

@komori3_ えぇ……(ありがとうございます)

Psyho @FakePsyho

@SomeNickName2 @Topcoder @CodinGame @Google @atcoder Sure, you can do heuristics, but that's against the spirit of the contest (based on what I understand). While breaking the system is a form of problem solving it's not exactly what I'm looking for right now :)

1 @komori3_

@koyumeishi_ ですよね　これで n 時間溶かして虚無になりました…

koyumeishi @koyumeishi_

@komori3_ ひえー… ちなみに C++ には "LR"s と書くと string 型で扱ってくれる機能があってたまに使うんですが、これは C++14 からなので MM では CE になってしまい -1 点になる罠にハマったことがあります

1 @komori3_

@koyumeishi_ ウ　そういう話を聞くとバージョン揃えた環境を用意しようかなと思いますね… 初参加の MM98 で topcoder judge の unsigned long が 64bit だったせいで xorshift を破壊された記憶が蘇る…

1 @komori3_

いやどうなんだろう　unsigned long が 8byte なことってありえるんだろうか

koyumeishi @koyumeishi_

twitter.com/tomerun/status… twitter.com/komori3_/statu… twitter.com/iwashi31/statu…

tomerun @tomerun

ビームサーチするとき、いつも （評価値、前状態のポインタ、操作）を全部作ってvectorに入れてから最後に nth_element で上位W件を取ってるけど、都度優先度付きキューで上位W件を管理するのとどっちが速いだろう

2020-04-30 22:36:18

iwashi31 @iwashi31

今回のマラソン、枝刈りダイクストラするために要素数制限有りの優先度付きキュー（溢れた要素は見ない）みたいなのが欲しくなって set で代用して遅くて捨てたんだけど、ちゃんとやればまともな速さになるのかなぁ

2020-04-30 16:54:36

koyumeishi @koyumeishi_

速い優先度付き両端キューが求められていそう

iwashi31 @iwashi31

そっか、ビームサーチするとき遷移に対する評価値が求められるなら次の状態のインスタンスは次で使うやつだけ後で作れるのか…

tomerun @tomerun

@iwashi31 iwashiさんレベルの人がこれ使ってなかったのちょっと驚いた。こういう高速化手法をまとめるのけっこう需要ありそうですね

kosakkun @kosakkun

ビームサーチで次の状態あとから計算できるの全然気付いてなかった...

koyumeishi @koyumeishi_

焼き鈍しとかビームサーチとかで状態 S から状態 T を (in-placeで) 生成した後 T を S へ戻したいときがある。 状態のコピーコストが小さければ S を保存しとけばいいんだけど、(問題の文脈上で)遷移が不可逆だったり逆変換が計算量的/実装コスト的に高コストな場合の扱いに悩む

koyumeishi @koyumeishi_

変数の代入履歴を記録しておけるようなもの作っておけば嬉しいのか…？ データ構造に依存してる場合がかなりしんどそう (結局コピーコストを受け入れて S を保存が一番楽なのかなぁ)

Yoichi Iwata @wata_orz

@koyumeishi_ 途中まで戻して枝分かれとかが不要なら透過方式どうでしょう？ 例えば状態が配列a[N]ならb[N]とid[N]と変数ID(バージョン番号)を用意しておいて、状態書き換え時にb[i]を書き換えてid[i]=IDにし、状態参照時はb[i]==IDならb[i]を参照してそうでなければa[i]を参照、巻き戻しは単にID+=1