University of Aizu Programming Contest 2010
17REとかなんなの？呪われてるよ。もう僕は疲れました。
result
23位 rankalee 4AC penalty 302
6/1 10/0 97/2 0/5 - 0/2 0/9 - - 67/3 -
A Citation Format
問題
論文の引用ページのリストが与えられたとき、それらを以下の記法で出力せよ。
- aページからbページまで連続して引用した場合a-bと出力する。
- 無駄な表現は認められない(1,2,3,4が与えられたときに1-2 3-4など）
- 連続しないページはそのまま番号を出力する
試行錯誤
次のページが現在のページ+1だったら出力保留で、そうでなくなった時点で出力すればいいよな。
連続した数が2以上だったらa-bの形式で、1だったらaを出力。
書いた。送信。WA.
え？あ、出力した後連続数のカウントリセットし忘れた。送信。AC.
B Old Bridges
問題
1...n番のn個の島が島0からそれぞれ橋で繋がっている。
それぞれの島にはw[i]の財宝があり、島0と島iを結ぶ橋はl[i]の重さまで耐えられる。
w,lが与えられたとき、島の財宝を全て担ぎながら回収することは可能かどうかを求めよ。
試行錯誤
脆い橋の島から順に財宝を回収していけばいいよね。
送信。AC.
C Accelerated Railgun
問題
原点を中心とする半径1の円の内部の点(px,py)から方向ベクトル(vx,vy)の向きにプロジェクタイルを発射する。発射されたプロジェクタイルは距離Dだけ進むことができ、原点を中心とする半径1の円に触れると入射角と反射角が等しくなるよう跳ね返る。
このとき、プロジェクタイルが原点に到達できるかを求めよ。
試行錯誤
うげ。幾何。しかも円上での反射をシミュレート？とばす。
D-Fを見た後でもどってきた。
図をかいてみよう。入射角と反射角が等しいなら、結局原点から出た弾が(px,py)を通過しないといけないから、(px,py)と(vx,vy)が平行もしくは半平行かどうかを調べればいいだけだ。
書いた。送信。WA.
あれ、平行の場合って1+|P|じゃないの？
ちがう2-|P|じゃん……送信。WA.
出力のほうだけ訂正して場合わけのほういじってなかったorz.送信。AC.
D Distorted Love
問題
各ページの情報と、ブラウザの操作が与えられたときに、ブラウザの動作をシミュレートせよ。
各ページの情報は次のように与えられる。
- ページの名前
- ボタンのリスト（リンク先のページの名前とボタンのx1,y1,x2,y2座標）
ブラウザの操作は次のように与えられる。
- "click x座標 y座標"
- "forward" バッファの次がある場合そのページへ移動、ない場合は何もしない
- "back" バッファの前のページがある場合移動（上に同様）
- "show" 現在のバッファのページの名前を出力
また、バッファは一次元上の無限に長いリストで、clickによりページを移動した場合、その後ろのバッファは全て消去される。
E Huge Family
例が良くわからなかったので飛ばした。
F Ben Toh
問題
n日間の間弁当を買う。i日目の弁当の入手確率をp%とすると、i+1日目の入手確率はi日目に弁当の入手に成功した場合p/2,入手に失敗した場合は100%である。
また、一日目の入手確率は100%である。
このときn日間で買える弁当の個数の期待値を求めよ。
試行錯誤
紙上で解いてみる。あれ？n=3のときの例がよくわからない（←普通に期待値の計算を間違えていた。もうだめぽ）
G Rolling Dice
問題
h*wのグリッドのそれぞれに数字が書かれている。このグリッドの上をスタートからゴールまでサイコロを転がして移動させる。
サイコロ一回転がすごとに、グリッドに書かれている数字×サイコロの底面の数のペナルティが加算されるとき、ペナルティを最小にしてゴールするときのペナルティを求めよ。
サイコロがグリッドからはみ出してはいけない。
H Winter Bells
解いてる人が殆ど居なかったので飛ばした。
I Mysterious Onslaugh
解いてる人が殆ど居なかったので飛ばした。
J No Story
問題
LCM(a,b)=Lとなるような正の整数a,b(a≦b)の組み合わせの個数を求めよ。
