とこはるのまとめ

多分考えたことがまとまっているはずです。きっと。おそらく。

とこはるの問題

今までに作った(or原案に携わったレベルの)問題と簡単なコメント

簡単な問題を作りたかった

タイトルだけ。内容は関与せず。

基礎的なフローの問題を作りたかった

当時は列になってる数をうにょうにょするDPを作りたかったはず。

高評価をいただいて大変ありがたい問題です。
本番中はwatashi(=rejudge)さんとrngさんだけが解きました。

やっぱり簡単な問題を作りたかった

よすぽさんと話し合ってたらできた。
よすぽさんが筋のいい問題を投げてくれたのでいい感じの解法のある問題が出来た。

地味にgeneratorが面倒で、適当にやるとビームサーチが通ってしまっていた。つまるところ局所解が少なかった。そこでgeneratorではi個外食したときの最適解f(i)のようなものを考えてそれの差分を導出してこれがランダムウォークっぽい挙動をするように調整したりした。

題名だけで放り投げておいたらshimomireさんが筋のいい問題を提案してくれていたので、いい感じの解法を付けて出題された。お気に入り問題のひとつ

知識ゲーを出したかった

JAGで出そうとした問題の没問。ごく一部に知ってる人はいたけど高校生用だからいいでしょってことで出してもらいました。

超簡単な問題を出したかった

大昔uwiさんと似たような問題を議論した覚えがあるけど時効だし出してuwiさんが正解しても不公平にはならないと思ったので出した。
証明の仕方が競プロ的テク+ホールの補題なのがお気に入り。

投げやり題名。組合せ最適化に書いてある問題だけど出してみた。手で解いたときは最小平均長閉路だと思ったけど、みんな牛ゲーで解いていたのでしくじったと思った。

原題はKaraoke Schedulingだった。(人より音が取れない下手くそではあるけど)カラオケにたまに行くのは楽しいなぁみたいな気分のときに問題を作った。
それから、簡単バージョンとしてコストが二乗でなくて絶対値になっている問題も同時に提案していた。

提案時はAOJ-ICPC換算で600-700くらいで、(アイデアは)蟻本にも書いてる内容だしで、ちょうどいいぐらいの典型問題だと思って出しだけど、人々を虐殺してしまった。
writer解を作るときに割とバグらせて時間がかかったのでそのときに気づくべきだったかもしれない?
XII Open Team Programming Collegiate Cup. ロシアだといいぐらいに上位層を選別する難度の問題として機能していたかなあという感じ。

VectorFieldを1次元にすればええやん、というそれだけ。
ただ、まじめに考えるときれいにできるのでよい

なんか行列累乗みたいな感じの問題を作りたかった。
サンプルにすべてのクエリーを網羅してなかったので申し訳ない

ここに書いた : 2015 JAG Regional J : Longest Shortest Path - とこはるのまとめ

(ノックアウトな)トーナメント表みたいなのは好きな構造なのでそれを使って何かをしたかったという話。
こういう問題はなかなか説明しづらいので、問題文のwriterには感謝。
最初は区間DPで行けるだけかと思ったけど実験的にやるとMongeが成り立っていそうだったので、Mi_Sawaさんに投げたら証明が返ってきました。

履歴

  • 11/3 : LiveProgrammingと最長増加列問題の話に加筆
  • 12/16 : 2015模擬地区予選の分を追加