2010/Staff

野田久順 †

社会人1年目

模擬練習会解答例+裏話 †

前年度模範解答集はこちら2010/Staff/野田

模擬国内予選 2011 †

Problem B: Brave Force Story -ブレイブ・フォース・ストーリー- †

原案を担当しました。 BFSを利用した別の問題を考えていたのですが、 模擬国内予選のB問題にしては難しすぎると却下され、 その場で新しい問題を作成しました。 プロローグはかなり適当にノリで作ったものですので、 間に受けないようにしてください。

Problem C: Fastest Route -最短ルート- †

CAPC○Mから発売されている○ックマンを題材にした問題です。 ニコニコ動画でTAS動画を見ていて思いつきました。 TSPだと思ったらTSPじゃなかったのであれれ・・・？ なお、この問題には多項式時間の別解があります。 ぜひ考えてみてください。あとで出します。

Problem F: Sakura Poetry -桜詩 〜願はくは花の下にて春死なむ〜- sakura.nodchip.cpp †

東方妖々夢の第6ステージの冒頭に出てくるロゴに書かれている和歌がテーマになっています。 元ネタの元ネタは西行法師の有名な和歌です。 この問題は昨年度の本番で出題された最強の呪文の立ち位置になるように出題しました。 模範解答を作った時点では微妙に計算量が読み切れていない部分があったのですが、 最終的には詳細に計算量を見積もり、出題しました。 たまにはこういった風流なタイトルもいいかなと思います。

夏合宿 2011 3日目 †

Problem A: Calender Colors -カレンダーの配色- †

原案を担当しました。 某カレンダーサービスを見ていて思いつきました。 原案はもう少し煩雑だったのですが、他のスタッフから本質的ではないと言われ、 いらない部分を削除しました。

Problem D: Marathon Match -マラソンマッチ- †

原案を担当しました。 タイトルで釣りたかっただけです。 確率の問題は自分は苦手なのですが、 優秀なスタッフに囲まれれば作る方はなんとかなるのだなぁと思いました。

Problem E: Reverse Roads -逆方向通行- reverse.nodchip.ss_dinic.cpp reverse.nodchip.ss_edmonds_karp.cpp †

模範解答を担当しました。 最大流問題の教科書的な問題です。 特筆すべき点はないと思います。

Problem I: White Bird -白い鳥- †

原案を担当しました。 Angry Birdにはまってしまったため作りました。 特に難しくないと思っていたのですが、 意外と正答数が少なかったのが意外でした。 周りのレベルが高すぎて感覚が麻痺しているのかもしれません。

Problem J: Vector Compression -ベクトル圧縮- †

原案を担当しました。 論文サイトで適当に漁り読みをしていた時に見つけたネタです。 元ネタでは貪欲法を使っていたのですが、 最適解を出せるのではないかと思って考えたのがこの問題です。 初めはただの最小全域木だと勘違いしていたのですが、 あとから最小有効全域木だと思い直し、この位置で出題することにしました。 予想より多くの方に解いていただけて嬉しい限りです。

模擬地区予選 2011 †

Problem A: Infinity Maze -無限の迷宮- †

原案を担当しました。 ただの幅優先に飽きてしまい、 歩数を固定で最後にどこにいるかをシミュレーションさせる形にしました。 周期を求めるだけの筈だったのですが、 予想より多くの誤答が出てしまっており申し訳有りませんでした・・・。

Problem B: Butterfly -私はあなたの小さな蝶々です- †

原案を担当しました。 コ○ミ枠として jubeat の問題を入れたかったのですが、 問題文を考えるのが面倒だったので、 コ○ミ -> D○R -> Butterfly と連想して問題を作ってみました。 Butterflyには"蝶々"の他に"移り気な女"という意味があるため、 彼氏が100人いるという訳のわからない設定になりました。 女性の名前は Veronica にしたかったのですが、 元ネタが分かる人はいるのでしょうか・・・？

Problem C: Chinese Classics -漢文- †

原案を担当しました。 返り点を習った当初全く理解できなかったため 恨みを込めて出題しました。 結果スタッフに恨まれ選手に恨まれ残念な感じになってしまって申し訳ありません。

Problem D: Revenge of Champernowne Constant -チャンパーノウン定数2- †

原案を担当しました。 2年前に出題した Champernowne Constant の改題です。 他の方から類題があるという事を聞いていたのですが、 あえて出題してみました。

Problem E: Full Text Search -全文検索- †

原案を担当しました。 自室サーバーで動かしているゲームで実際にあったバグ報告からの出題です。 非常に面白い問題だった、と他の方はおっしゃっているのですが、 正直に言うと解法が理解できていません。

Problem H: Sky Jump -新型ミサイル「遺憾の意」- †

原案を担当しました。 Angry Bird と放物線にハマりすぎて作った問題です。 自分で解法のアイデアは思いついたのですが、全く証明できず、 他のスタッフによって解法の正当性が証明されました。 個人的には本問題セットの中で一番好きな問題です。

Problem I: Mobile Network -モバイルネットワーク- (解答ソースコードは誤りが認められたため削除しました。大変申し訳ありません。) †

原案と模範解答を担当しました。 ただの最大流は飽きてしまったので 何かひねりを加えられないかと頭をひねっていたところ浮かびました。 自分の解答が思いのほか長くなってしまい、 少し残念です・・・。

Problem J: Blue Forest -碧の森- †

原案を担当しました。 都道府県名で１つずつ問題をつくろうと思っていたのですが、 青森で作って飽きてしまいました。 内容は実装系の幾何です。 今までに出題してきた問題に比べると解きやすいのではないかと思います。

冬コンテスト 2011 †

Problem D: Matrix Operation -行列操作- matrix.nodchip.cpp †

解答を担当しました。操作順番を整理するのが難しく、汚いソースになってしまいました。 第一線から離れて久しいため、仕方のない事なのかもしれません。

Problem G: Runaway Domino -ドミノ倒し- runaway.nodchip.cpp †

原案と解答を担当しました。 UTPCに出題された猫の問題にインスパイアされて作った問題です。 かなり手加減したつもりだったのですが、解けたチームが思ったよりも少なく残念です。

春コンテスト 2012 †

Problem E: Dungeon Creation †

原案を担当しました。 解法があやふやなまま提案したのですが、 他のスタッフによって効率の良い解法が提案され、 高めの難易度の問題として出題されました。 知識問題ですのでちょっと微妙かもしれません。

Problem F: Longest Lane †

原案を担当しました。 普通〜やや難程度の幾何問題として作成した問題のつもりだったのですが、 解けたチームが思ったより少なく、幾何補正の大きさをひしひしと感じています。

Problem G: Play in Basic †

原案を担当しました。 この問題は5年前に提案した問題です。解法は構文解析+DP×2問分という高難易度の問題です。 解法と問題文が作られた後、あまりにも難しすぎるという理由により封印されていました。 ある参加者から「なかった」とツイートされ、当時の担当者の判断が正しかったことを改めて認識しました。

Problem I: Three-way Branch †

原案を担当しました。 サイズが小さければ教科書的な動的計画法の問題なのですが、 サイズが大きくなると途端に難しくなるという問題です。 本番では自分が提案した方法よりさらに難易度を上げて出題されました。 JAGスタッフ怖いです。