2010/Staff

野田久順 †

東京工業大学集積システム専攻博士課程3年

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

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

模擬国内予選 2010 †

Problem A Sum of Consecutive Integers -連続する整数の和- †

原案を担当しました。 元ネタは研究室に置かれていた冊子に乗っていた問題そのままです。

Problem B Moonlight Farm -ムーンライト牧場- †

原案を担当しました。 元ネタは一世を風靡したmixiアプリ『サンシャイン牧場』です。 自分はかなりハマりました。 ソートが書ければ解けると思います。

Problem C Differential Pulse Code Modulation -差分パルス符号変調- adaptive.nodchip.cpp †

原案と解答を担当しました。 自分の所属する研究室に関係のある題材から 動的計画法の問題として出題しました。 Problem Cとして動的計画法の問題を出題するのは スタッフの間では難易度の観点から難しいのではないかという意見もあったのですが、 予想より多くのチームが正解していてほっとしました。 解答は[nサンプル目][振幅]という表を先頭から埋めていくものとなっています。 ただしメモリを節約するため2つのメモリを切り替える形で実装しています。 なお、本番で使用した入力データには、ある音声メッセージが含まれています。 是非聞いてみて下さい。

Problem E Immortal Jewels -不死の宝石- immortal.nodchip.cpp †

原案と解答を担当しました。 早坂さんによる改題により、とても良い難易度の問題になりました。 円の共通接線を求めるライブラリがあり、 かつ解法のアイデアに至れば、 比較的簡単に実装することができると思います。 元ネタは竹取物語よりかぐや姫が求婚者に出題した5つの難題の1つ、 蓬莱の玉の枝です。

Problem F Canal: Water Going Up and Down -閘門式運河: 上下に動く水面- †

原案を担当しました。元ネタはパナマ運河です。 この問題は当初はイベントドリブンのシミュレーション問題として出題する予定だったのですが、 Acceptedした回答は全て動的計画法で書かれていました。 スタッフ一同驚きました。

Problem G Magical Island 2 -魔法島物語2- †

原案を担当しました。 元ネタは以前のもぎコンテストで出題された『Magical Island』という問題です。 厨二病設定前回でお送りしております。 問題内容は他のスタッフにより最終問題に相応しい難易度に改題されました。 この場を借りてお礼申し上げます。

夏合宿 2010 †

4日目 Problem A: Alien's Counting -エイリアンの数え方- †

原案を担当しました。 なんとなくグワシとか長寿と繁栄をとかキラッ☆とかやっていたところ、 この問題を思いつきました。なぜ思いついたのかは分かりません。

4日目 Problem D: Dungeon Wall -ダンジョンの壁- †

原案を担当しました。普通の幅優先探索の問題が欲しかったので入れました。 とは言っても壁の持たせ方が少し特殊なので普通というほど普通ではないかもしれません。 意図せずREしてしまった件は申し訳ありませんでした。

4日目 Problem E: Psychic Accelerator -とある超能力の物体加速器- accelerator.nodchip.cpp †

原案・解答・英文を担当しました。 一番始めの原案は電車でGOを題材にしたもので、 カーブの制限速度が与えられたときの最速タイムを求めるというものでした。 その後、最大加速度を与えた方が問題としてきれいになると思い、 このような形になりました。 問題変更に伴い、問題背景も差し替えています。

4日目 Problem F: Bouldering -ボルダリング- †

原案を担当しました。 TwitterのTL上でボルダリングをする人が増えてきたため、 流行に乗るために出題してみました。

4日目 Problem H: Ropeway -ロープウェイ- †

原案を担当しました。 原案ではシーソーにおもりを載せて傾けすぎないようにするというものでした。 特に特筆すべきことはありません。

4日目 Problem I: How to Create a Good Game -おいしいゲームの作り方- game.nodchip.cpp †

原案・解答を担当しました。 3年位前に提案して誰も解法が分からないまま放置されていたのですが、 他のスタッフによって解法が与えられました。 かなりレベルの高い問題です。自力では解けそうにありません・・・。

4日目 Problem J: Cruel Bingo -BINGO大会の悲劇- †

原案を担当しました。 元はDPとして出題する予定だったのですが、 他のスタッフによって数論解法が与えられ、 大幅に難易度を上げての出題となりました。 正直なところ、解法が理解できません・・・。 元ネタは某ネタサイトのネタです。

模擬地区大会 2010 †

Problem A: Era Name -元号- †

原案を担当しました。 模擬コンテスト1問目レベルの簡単な問題が欲しいと思って作った問題です。

Problem B: Step Step Evolution -ステップ・ステップ・エボリューション- †

原案を担当しました。 簡単なDPの問題が欲しいと思い、自分の好きなDDRをパクってから着想を得て作成しました。 問題担当者が4方向だけではあまりにも簡単になりすぎると考えたため、 8方向に変更となりました。 8方向でも割と簡単だそうです。

Problem D: Dice Room -ダイス・ルーム- †

原案を担当しました。 ニコニコ動画のサイレントヒルのプレイ動画に登場した 仕掛けを見ていて思いつきました。 サイコロを題材にした問題は日本の地区予選には頻出ですので、 ぜひ解けるようにしておきましょう。

Problem E: Alice and Bomb -アリスとボブム- †

原案を担当しました。 以前作成した"Alice and Bob"という問題の内容を少し変えたものです。 元のタイトルは"Bomb Explosion"だったのですが、 "Alice and Bomb"というタイトルのほうが面白いと思い、改題しました。 それに合わせて問題文の一段目も"Alice and Bob"を意識したものに変更しました。 以前の模擬コンテストに出られた方の中には元ネタが分かった方もいるかも知れません。

Problem F: Two-Wheel Buggy -二輪バギー- wheel.nodchip.cpp †

解答を担当しました。 今回出題された3問の幾何の中では最も簡単な問題です。 しかし、見た目が非常にいやらしいため、 なかなか手をつけられなかったというチームも多いのではないかと思います。

Problem G: Camera Control -カメラ・コントロール- camera.nodchip.cpp †

原案を担当しました。 モーニング娘。のライブ映像をフランス人カメラマンが絶賛する動画を見て作ろうと思いました。 初期の問題案では問題中に登場するグループ名は"Mars"だったのですが、 もっと一分に受けるグループ名が良いと考え"ACM48"にしました。 ACM48はどんな歌をうたうグループなのでしょうか？

Problem I: Operator -テレホン・オペレーター- †

原案を担当しました。 DDRの曲のタイトルで問題をつくろうと思い、 いくつか原案を作成したうちの一つがこれです。 演算子の方ではありません。 後ろの方にあるので難しい問題だと勘違いしたチームもいるかも知れません。

Problem J: Merry Christmas -メリー・クリスマス- †

原案を担当しました。 大分前に作った問題で、作ったものの自分では解くことができませんでした。 想定解法は他のスタッフにより与えられました。

冬合宿 2011 †

4日目 Problem B: Bubble Puzzle -水玉潰し- bubble.nodchip.cpp †

原案と解答を担当しました。元ネタは一時期流行したFlashゲームです。 原案では盤面のサイズは6x6だったのですが、計算量的に厳しかったため4x4に変更しました。 問題セットの中では簡単な方だったと思います。

4日目 Problem D: King Slime -キングスライム- slime.nodchip.cpp †

原案と解答を担当しました。元ネタはドラクエです。 選手の方から「普通すぎて野田さんが作ったとは思えない」と言われてしまったのですが、 最近ネタがた尽きてきてこのような普通の問題しか作れなくなってしまいました。 精進したいと思います。

4日目 Problem I: Tampopo Machine -今日もまた、刺身の上にタンポポのせる仕事が始まるお- †

原案を担当しました。 "i刺身LITE"というiPhonアプリの事を思い出したので作ってみました。 問題を作っては見たものの、あまりにも難しすぎて他のスタッフに丸投げしてしまいました。 上がってきた解法を見たところ、自分の頭では概要しか理解出来ないものすごい解答でした。 解法を考えてくださった某スタッフには頭が上がりません。

4日目 Problem J: Top of the Hill -タ◯ヤＲＣカーグランプリ- hill.nodchip.cpp †

原案と解答を担当しました。 タイトルの元ネタはネット小説 『魔王「この我のものとなれ、勇者よ」勇者「断る！」』の英語タイトル 『the over side of that hill』です。 昨年度の冬合宿に出題したMagnum Tornadoの類題です。 難易度はこちらのほうが若干簡単だと思います。 平面最短路は難易度が高いのでボス問題として入れやすいです。 一方、解答作成者の負担が高くなるので安易に入れるのは考えものです。