AOJ 0039 (Roman Figure : ローマ数字)
【問題】
https://onlinejudge.u-aizu.ac.jp/problems/0039
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0039
【解説】
ローマ数字の値を求める行う問題。
あらかじめ、アルファベットに対応した値のDictinaryを用意しておく。
あとは、「大きい数字の前にあって引き算を表す小さな数字は一回の引き算あたりひとつしかありません。」との制約から、与えられた文字列を先頭から順にみていき、次の文字よりも値が小さければその文字に対応する値を答えから引き、そうでなければ答えに足していくことで、答えを求めることができる。
最後の文字を足し忘れないように注意。(最後の文字は無条件に加算してよい)
【コード】
AOJ 0038 (Poker Hand : ポーカー)
【問題】
https://onlinejudge.u-aizu.ac.jp/problems/0038
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0038
【解説】
ポーカーの役判定を行う問題。以下の優先順位に従って判定していけばよい。
- 同一のカードが4枚あればフォーカード
- 同一のカードが3枚がある、かつ同一のカードが2枚あればフルハウス
- "ストレート判定"結果がtrueならストレート
- 同一のカードが3枚あればスリーカード
- 同一のカードが2枚ある数字が2組あればツーペア
- 同一のカードが2枚あればワンペア
- それ以外はノーペア
ストレート判定については、カードを昇順にソートし、組み合わせが{1,10,11,12,13}、または各カードの差が1であれば、trueを返すようにすればよい。
上記の判定のため、カードのナンバーをインデックスとしたコレクションを用意して起き、度数表のようにカードの数を格納しておくと、Linqを使用して簡単に判定できる。
【コード】
AOJ 0037 (Path on a Grid : 格子上の経路)
【問題】
https://onlinejudge.u-aizu.ac.jp/problems/0037
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0037
【解説】
原点に戻ってくるまで、順番にルートを辿っていく。右手を壁に着け、壁伝いに進むため、以下のルールに従って進んでいけばよい。
- 進行方向に対して左手にルートがあれば、左手に進む。
- 進行方向にルートがあれば、進行方向に進む。
- 進行方向に対して右手にルートがあれば、右手に進む。
- いずれもなければ逆側に進む。
上記については、各交点ごとに壁の伸びている方向を東方向を0°として、反時計周りに正となるよう(ちょうどxy平面のように)に格納しておき、進行方向に対して、-90°、0°、90°、180°のルートがあるかを順にみていけばよい。
【コード】
AOJ 0036 (A Figure on Surface : 平面上の図形)
【問題】
https://onlinejudge.u-aizu.ac.jp/problems/0036
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0036
【解説】
二次元のパターンマッチングの問題。二次元の配列にてローリングハッシュを用いて、パターンと一致するかどうかを判定している。
【コード】
AOJ 0035 (Is it Convex? : 凸?)
【問題】
https://onlinejudge.u-aizu.ac.jp/problems/0035
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0035
【解説】
凸多角形において、任意の内角は 180° 以下である。すなわち、多角形の各辺に対し、その多角形の内点は全て、その辺を延長して得られる直線に対して同じ側にある。
よって、各辺を巡回していくように各辺のベクトルを求めると、各頂点へのベクトルと各頂点からのベクトルの外積の正負がすべて一致することとなるので、これを判定すればよい。
【コード】
AOJ 0034 (Railway Lines : 鉄道路線)
【問題】
https://onlinejudge.u-aizu.ac.jp/problems/0034
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0034
【解説】
すれ違う地点の位置を求めればよい。
区間1側の終端駅から出発する列車をA、区間10側の終端駅から出発する列車をBとする。両者がすれ違うとは、両者の進んだ時間が等しいということなので、速さを\(v\)、距離を\(s\)、全体の長さを\(L\)とすると、 $$ \frac{s_A}{v_A} = \frac{L-s_A}{v_B} $$ として表せる。
あとは、\(s_A\)について解いていくと $$ \begin{align} {s_A}{v_B} & ={(L-s_A)}{v_A} \\{s_A}{v_B}+{s_A}{v_A} & ={L}{v_A} \\{s_A}{(v_A+v_B)} & ={L}{v_A} \\{s_A} & = L \frac{v_A}{v_A+v_B} \end{align} $$ となる。(AとBが時間当たりに進む距離の比は、\(v_A:v_B\)となるため、当たり前っちゃ当たり前。)
上記の値を計算し、その値が何番目の区間に位置するかを判定してあげればよい。
【コード】
AOJ 0033 (Ball : 玉)
【問題】
https://onlinejudge.u-aizu.ac.jp/problems/0033
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0033
【解説】
筒Aに入ってる球を、球は昇順にしか積み上げられない制約下で、筒Bまたは筒Cに移していくことができるかどうかを判定する問題。球の数は10個のため、シミュレーションすればよい。
筒Aの球がBまたはCのどちらか一方にしか移せない場合は、必ず移せる方向に積み上げるしかない。どちらにも移せる場合は、BとCのうち値が大きい方に積み上げる方が明らかに最適である。
【コード】