2008/Staff
野田久順 †
東京工業大学集積システム専攻博士課程2年
模擬練習会解答例集 †
模擬国内予選 2008 †
この問題の原案はもう少し内容が簡単だったのですが、
スタッフによる改変により複雑な問題となってしまいました。
この問題のポイントは「拍に分解して処理」と「文字列のまま処理」の
どちらを選択するかという点です。
どちらを選択するかによってコードの長さと難易度が変わってきます。
本解答では問題の内容に従い、「拍に分解して処理」を選択して実装いたしました。
実は「文字列のまま処理」の方がシンプルなコードが書けるようです。
この処理の選択にプログラマーとしてのセンスが出てくるのではないでしょうか？
夏合宿 2008 †
Day 2 - Problem A - PI is three 
pi.cpp †
簡単な問題として出題された問題です。
分母の値でfor文を回すだけというシンプルな解答です。
355/113の精度がとても良いというのが面白いですね。
Day 2 - Problem G - Time Trial time.cpp †
割と頻出な上下左右方向の幅優先探索問題です。
ただし通常出題されているものより若干実装量が多いかもしれません。
本番中でこの問題に手をつけたチームは予想より少なかったです。
なお、この問題の元ネタは"ドラ○エ3"で"かわ○のつぼ"を入手する際に解くパズルです。
Day 2 - Problem I - Memory Match memory.cpp †
確率×DPという比較的出題されやすいタイプの問題です。
サンプル入力が通ればほぼ間違いなくジャッジ入力も通るという、
安心二重丸の問題です。
場合分けを整理して考えればそう難しくはないでしょう。
Day 4 - Problem C - Adaptive Time Slicing Quantization adaptive.cpp †
ICPCではあまり出題されない信号処理分野の問題です。
中身は簡単な数値計算とDPですので、
慣れている人であれば難無く解ける問題だと思います。
各区間内のすべての値が等しい場合には
最小値と最大値が等しくなり、
"(hoge)/(max-min)"等と書くと0割が起こります。
注意しましょう。
Day 4 - Problem G - Do It doit.cpp †
タイトルでもめた問題です。
内容があまりにもシンプルなために驚いた方もいらっしゃるかもしれません。
この問題のポイントはsinの積の分解を思いつくかどうかです。
思いついた後もdivided by zeroでWAを食らうという罠もあり、
なかなか面白い問題だったのではないかと思います。
数値積分は無理だと思います。
模擬地区予選 2008 †
できれば開始10分以内に解けて欲しい問題です。
簡単な問題として出題したはずだったのですが、
計算量の見積もりができていなかったり、
計算式そのものが間違っていたりと、
誤回答が多く見受けられました。
Problem E - REST in PLAY rest.cpp †
ポイントは単純なDPでは間に合わないのを
どのように克服するかという点です。
いずれの解法もDPなのですが、解答が複数ある非常に面白い問題でした。
おすすめは解説スライドにあるチート^H^H^H改良版解法です。
英文が読みづらく、ほとんどのチームが手をつけられなかった問題です。
内容は木の構築とトポジカルソートという王道問題です。
N<=100000という点に注意して実装してください。
冬合宿 2009 †
Day 2 - Problem A - Adhoc Translation adhoc.cpp †
ライブラリを二つ組み合わせるだけのサービス問題のつもりだったのですが、
予想よりかなり成績が悪かった問題です。
レーベンシュタイン距離を見抜けなかったのが最大の原因だと思います。
Day 2 - Problem D - Dial Key dial.cpp †
元はDPとして出題する予定の問題だったのですが、
数論的な解法が発見されたことにより、
当初より大幅に入力上限を上げて出題されることとなりました。
詳細な証明より感で答えたほうがよい問題かもしれません。
Day 2 - Problem F - Exciting Bicycle exciting.cpp †
タイトルの元ねたはいわずと知れた名作レーシングゲームです。
子供のころによく遊んだという方もいらっしゃるのではないかと思います。
この問題はサービス問題として出題する予定だったのですが、
高橋さんにより誤差の大きさが指摘され、
若干難易度を上げての出題となりました。
着地点を二分探索で求めるか、二次式を陽に解いた後に誤差を少なく計算するか、
時間tをパラメータとして用いた式で計算するかが焦点となります。
この解答では着地点を二分探索で求めています。
方程式を解くのが面倒だったので・・・。
Day 2 - Problem J - Substring Expression substring.cpp †
ヒラメキ命の問題です。
この問題は解答ソースコードが出来上がった後に解法の正当性が確かめられたという、
少し変わったエピソードがあったりします。
Day 3 - Problem A - Cache Control cache.cpp †
釣り問題として出題されたサービス問題です。
LinkedHashMapを実装してしまった方、お疲れ様でした。
Day 3 - Problem C - Craftsman craftsman.cpp †
普段自分はフローの問題は担当しないのですが、
解法が完全に示されていたので書いてしまいました。
へたれでごめんなさい。
Day 3 - Problem E - Mickle's Beam mickle.cpp †
やっぱり問題のタイトルはその問題の命だと思うんですよ。
この問題はタイトル以外に重要なポイントはないです。
・・・といいつつ、境界条件に気をつけないとWAを乱発してしまうという
罠な問題になっています。
解く場合には特にx軸の負と接点を持つtankの扱いに注意しましょう。
Day 3 - Problem K - Trading Ship trading.cpp †
元はN<=10程度で出題される予定だったのですが、
グラフによる解法が見つかったことにより、
入力の上限を大幅に上げて出題されることとなりました。
誰かボロノイ図の解法を作ってみたいという方はいらっしゃいませんか？
