AOJ-ICPC 2016.10.1
問題
Texas hold 'em | Aizu Online Judge
問題概要
それぞれのプレイヤーは2枚ずつ非公開のカードを持っていて、場に3枚のカードが公開されている。
ここからさらに2枚のカードを公開し、自分のカードと場のカードの7枚から5枚を選び、手の強さを競う（手の強さは問題文参照）。
あなたはテレパシーで相手の非公開カードを知っている。
勝てる確率を求めよ。ただし引き分けは負けとする。
解法
実装する。ポーカー役判定ライブラリがあれば楽勝だと思う。
残りの2枚のカードの組みの出方はすべて等しいので、全パターンで勝敗を求め、平均をとる。
問題
Clock Hands | Aizu Online Judge
問題概要
現在の時刻が与えられるので、次に時針と秒針が作る角度と分針と秒針が作る角度が等しくなる時刻を求めよ。
ただし、針が重なる瞬間は除く。
時針はH時間で1周する。
分針と秒針はそれぞれ60分、60秒で1周する（これは多分問題文に書いてないので制約から察する）。
解法
とりあえず分数が必要になるので用意しておく。
時針、分針、秒針が1秒に動く角度を とする。
時針と分針の真ん中の角度を , 秒針の角度を
とすると、
は1秒間に
ずつ縮まので、これが
になる時間を求めればよい。
条件を満たすような角度は2つあるので、それぞれについて求めて最小値をとる。
source
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2016952#1
450と500がもうすぐ埋まりそう。
124550 -> 125600
AOJ-ICPC 2016.9.30
サイコロの問題はめんどくさいことが知られている。
だから解きたくないのだが、他に解ける問題が減ってきたので解いていく。
問題
Dice Puzzle | Aizu Online Judge
問題概要
サイコロ27個からなるキューブを考える。
キューブの上面と全面の数字は指定されていることがある。
隣り合うサイコロの面の和は7になっている必要がある。
キューブの右面の数の和として考えられるものを列挙せよ。
解法
全探索。
サイコロの置き方は 通りあるが、条件のせいで枝刈りが効きまくるので間に合う。
問題
問題概要
各面に のマスが書かれた立方体がある。
マスには穴が開いていることがある。
立方体を4方向の任意の方向に回転させて、正面と裏側の面の下の段に穴があるようにするとき、
最小の操作回数を求めよ。
解法
BFS。
立方体の置き方は24通りしかないのでBFSすればそのうち答えが求まる。（3回の回転で全列挙できる気がする）
最後の画像は説明がないけど数字の向きに合わせて入力される、という意味だと思う。
問題
Traveling Cube | Aizu Online Judge
問題概要
各面に異なる6色の色がついた立方体が盤面を転がりながら移動する。
盤面にも色がついていて、白には自由に入れ、黒には入れない。
それ以外の色は1マスずつあり、立方体の上面が盤面と同じ色になる場合のみ入れる。
また、白以外のマスはそれぞれ一度ずつしか入れない。
白以外の色の順番が指定されるので、その順にマスを踏んでいく時、最小何手で指定されたマスを全て踏めるか求めよ。
解法
BFS。
[今いる場所、立方体の状態、何番目の色まで踏んだか]という情報を持っておく。
問題
Dice Stamp | Aizu Online Judge
問題概要
（省略）
解法
bitDP。
各マスについて、通るダイスを前処理で記録しておく。
そのダイスが通過するそれぞれのマスについて、そのダイスがそのマスを通過する最後のダイスである場合のみ、そのダイスのスコアに加算する。
1つのダイスが2回同じ場所を通過することもある点に注意する。
あとは使用したダイスを状態に持って普通にbitDPをやればいい。
問題
問題概要
（省略）
解法
貪欲法
最初の置き方が 通りあるので、それぞれに対して以下の操作を行い、解を求める。
E,N,W,Sの順に回転を試してみて、次の状態が詰んでいなければその回転方向に確定する。
詰んでいる状態とは「ある反対方向にあるペアの和が、他の4面の和より2以上大きい」または「ある反対方向にあるペアの和が、他の4面の和より1大きく、現在そのペアが上面と下面になっている」
のどちらかを満たす場合である。
source
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2015833#1
最初の2問が一番時間がかかった。めんどいだけ。
3つ目と4つ目はいい感じの典型っぽくて5問目は面白かった。
121750 -> 124550
