とこはるの問題
今までに作った(or原案に携わったレベルの)問題と簡単なコメント
2012年
簡単な問題を作りたかった
タイトルだけ。内容は関与せず。
基礎的なフローの問題を作りたかった
当時は列になってる数をうにょうにょするDPを作りたかったはず。
高評価をいただいて大変ありがたい問題です。
本番中はwatashi(=rejudge)さんとrngさんだけが解きました。
2014年
やっぱり簡単な問題を作りたかった
よすぽさんと話し合ってたらできた。
よすぽさんが筋のいい問題を投げてくれたのでいい感じの解法のある問題が出来た。
地味にgeneratorが面倒で、適当にやるとビームサーチが通ってしまっていた。つまるところ局所解が少なかった。そこでgeneratorではi個外食したときの最適解f(i)のようなものを考えてそれの差分を導出してこれがランダムウォークっぽい挙動をするように調整したりした。
題名だけで放り投げておいたらshimomireさんが筋のいい問題を提案してくれていたので、いい感じの解法を付けて出題された。お気に入り問題のひとつ
知識ゲーを出したかった
JAGで出そうとした問題の没問。ごく一部に知ってる人はいたけど高校生用だからいいでしょってことで出してもらいました。
2015年
- ぼくの学生証 A - ぼくの学生証
超簡単な問題を出したかった
- 麻雀 K - 麻雀
大昔uwiさんと似たような問題を議論した覚えがあるけど時効だし出してuwiさんが正解しても不公平にはならないと思ったので出した。
証明の仕方が競プロ的テク+ホールの補題なのがお気に入り。
- 何かグラフの問題 N - 何かグラフの問題
投げやり題名。組合せ最適化に書いてある問題だけど出してみた。手で解いたときは最小平均長閉路だと思ったけど、みんな牛ゲーで解いていたのでしくじったと思った。
- Live Programming I - Live Programming
原題はKaraoke Schedulingだった。（人より音が取れない下手くそではあるけど）カラオケにたまに行くのは楽しいなぁみたいな気分のときに問題を作った。
それから、簡単バージョンとしてコストが二乗でなくて絶対値になっている問題も同時に提案していた。
提案時はAOJ-ICPC換算で600-700くらいで、（アイデアは）蟻本にも書いてる内容だしで、ちょうどいいぐらいの典型問題だと思って出しだけど、人々を虐殺してしまった。
writer解を作るときに割とバグらせて時間がかかったのでそのときに気づくべきだったかもしれない？
XVII Open Team Programming Collegiate Cup. ロシアだといいぐらいに上位層を選別する難度の問題として機能していたかなあという感じ。
- Line Gimmick D - Line Gimmick
VectorFieldを1次元にすればええやん、というそれだけ。
ただ、まじめに考えるときれいにできるのでよい
- Shifting a Matrix E - Shifting a Matrix
なんか行列累乗みたいな感じの問題を作りたかった。
サンプルにすべてのクエリーを網羅してなかったので申し訳ない
- Longest Shortest Path J - Longest Shortest Path
ここに書いた : 2015 JAG Regional J : Longest Shortest Path - とこはるのまとめ
- Optimal Tournament K - Optimal Tournament
（ノックアウトな）トーナメント表みたいなのは好きな構造なのでそれを使って何かをしたかったという話。
こういう問題はなかなか説明しづらいので、問題文のwriterには感謝。
最初は区間DPで行けるだけかと思ったけど実験的にやるとMongeが成り立っていそうだったので、Mi_Sawaさんに投げたら証明が返ってきました。
2016年
豪邸と宅配便 , jfen : あまり仕事ができず。
2017年
- Librarian's work I - Librarian's Work
IOIで出た図書館系の問題が割と好きだったのでそういうのを作りたくなったので作りました。
- Revenge of the Broken Door D - Revenge of the Broken Door
昔の本家ICPCの問題 BrokenDoor http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1178&lang=jp をそのまま一般化したもの。
AOJ-ICPCにある難問を通勤中の電車で考えることを一時期やっていて、
BrokenDoorを考えているときになんとなく行けそうな気がしてきて、頑張って詰めた覚えがあります。
これを本番で通せるチームが複数いるあたり、やはり当時とはレベルが段違いであることを伺わせます。
昔のICPC勢と飲むときに酒のつまみにできる問題です。
- Farm Village J - Farm Village
問題の美しさは最高レベルだと思っています。
wataさんの資料からも参照されていてとても嬉しいです。
模擬地区に向けて問題が足りないということで必死こいて作りました。結構短期間で作った覚えがあります。
2019年
- All your base are belongs to us
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2972
JAG内部の問題Wikiに雑すぎる解法を書いたため埋もれていた問題です。
notさんがエレガントな証明を思いつくことで日の目を見ました。
