とこはるのまとめ

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

とこはるの問題

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

2012年

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

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

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

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

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

2014年

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

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

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

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

知識ゲーを出したかった

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

2015年

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

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

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

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

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

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

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

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

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

2016年

豪邸と宅配便 , jfen : あまり仕事ができず。

2017年

IOIで出た図書館系の問題が割と好きだったのでそういうのを作りたくなったので作りました。

昔の本家ICPCの問題 BrokenDoor A Broken Door | Aizu Online Judge をそのまま一般化したもの。
AOJ-ICPCにある難問を通勤中の電車で考えることを一時期やっていて、
BrokenDoorを考えているときになんとなく行けそうな気がしてきて、頑張って詰めた覚えがあります。

これを本番で通せるチームが複数いるあたり、やはり当時とはレベルが段違いであることを伺わせます。
昔のICPC勢と飲むときに酒のつまみにできる問題です。

問題の美しさは最高レベルだと思っています。
wataさんの資料からも参照されていてとても嬉しいです。

模擬地区に向けて問題が足りないということで必死こいて作りました。結構短期間で作った覚えがあります。