足跡-sokuseki-

りかの日進月歩の記録

AOJ1345 Bit String Reordering

競技プログラミング AOJ

Bit String Reordering | Aizu Online Judge

問題概要

長さ N のビット列 b を、となりあう2つのビットをswapすることを繰り返してランレングス符号が p であるようなビット列に変換するときの最小のswap回数を求めよ。
ランレングス符号は0または1が連続する最大の長さを表した数列のことである。たとえば、ランレングス符号が"1 3 2"となるビット列は"011100"と"100011"の2通り存在する。

制約

1 \le N \le 15
ビット列 b からswap操作のみを繰り返してランレングス符号が p となるようなビット列に変換できることが保証される。

解法

ありうる2通りのビット列に対して、最小のswap回数を求め、小さい方を出力すれば良い。
最小のswap回数は、左から順に見ていって、ことなるビットの場合は、それより右で一番近いものとswapするを繰り返せば良い。
AIZU ONLINE JUDGE: Code Review

AOJ1286 Expected Allowance

競技プログラミング AOJ

Expected Allowance | Aizu Online Judge

問題概要

n 個の m 面サイコロを振って出た目の総和から k を引いたものの期待値を求めてください。ただし、出た目の総和から k を引いたものが0以下になるときは1として計算します。

制約

1 \le n
2 \le m
0 \le k \le nm
nm × mn \le 10^8

解法

制約を睨むと目の出方を全探索することができるので、やります。
AIZU ONLINE JUDGE: Code Review

AOJ1277 Minimal Backgammon

競技プログラミング AOJ

Minimal Backgammon | Aizu Online Judge

問題概要

0から N までのマスがあるすごろくをします。マスには何も書いていないマス、止まると1ターン休みになるマス、止まるとスタートのマスまで戻るマスがあります。マス0がスタートのマス、マス N がゴールのマスで、どちらのマスにも何も書いてありません。
6面のサイコロを使って駒を動かします。駒はゴールのマスより先に進めないので、例えば N-3 のマスにいるときにサイコロの目が5のとき、駒は N-2 に進みます。
T ターン以内に駒がゴールに到達する確率を求めてください。

制約

5 \le N \le 100
1 \le T \le 100

解法

dp[ i ][ j ] := i ターン目にマス j にいる確率
として確率DPをします

AIZU ONLINE JUDGE: Code Review

AOJ1368 Quality of Check Digits

競技プログラミング AOJ

Quality of Check Digits | Aizu Online Judge

問題概要

0000~9999の4桁の数の後ろにチェックディジットを1つつけて5桁の数を作る。チェックディジット e は、4桁の数の数字を上から abcd としたとき、
e =( ((0 \otimes a) \otimes b) \otimes c) \otimes d
と定義される。ここで x \otimes y は与えられた表の x 行 y 列目の数字を指す。
与えられる表の i 行 i 列目は必ず0になっているので、 ((((0 \otimes a) \otimes b) \otimes c) \otimes d) \otimes e は必ず0になる。これが0にならない場合、誤りを発見したことになる。

0000~9999の4桁の数 x にチェックディジットをつけた5桁の数 y について、以下の2つのどちらかの操作を行った後、 ((((0 \otimes a) \otimes b) \otimes c) \otimes d) \otimes e が0になるような x はいくつあるか答えよ。

  • y のある1つの桁の数字を異なる数字にする
  • y のとなりあう2つの桁の数を入れ替えて、 y とは違う数にする

解法

全探索して愚直に数え上げます。

AIZU ONLINE JUDGE: Code Review

AOJ2340 Carpenters' Language

競技プログラミング AOJ

Carpenters' Language | Aizu Online Judge

問題概要

括弧列がvalidであるとは、文脈自由文法で以下のように定義される。

S -> SS | (S) | )S( | ε

あなたは最初、空の括弧列Sを持っている。
q 回のクエリが与えられる。 i 番目のクエリで p_i, c_i, n_i が与えられるので、Sの p_i 文字目に c_i を n_i 回挿入し、できた括弧列がvalidであるかを判定してください。

制約

1 \le q \le 10^5
0 \le p_i \le i番目のクエリの前の S の長さ
1 \le n_i \le 2^{20}
c_i は '(' または ')'

解法

よく考えると、'('の個数と')'の個数が同じだとvalidな括弧列になることがわかるので、オーバーフローを気にしながら'('の数と')'の数が等しいかをチェックすれば良いです。
ちなみにぼくはよく考えてもわかりませんでした。
AIZU ONLINE JUDGE: Code Review

AOJ2165 Strange String Manipulation

競技プログラミング AOJ

Strange String Manipulation | Aizu Online Judge

問題概要

線形合同法を使って擬似乱数を生成します。線形合同法は
R_0 = S
R_i = ( A R_{i-1} + C ) mod M
で計算します。ここで S, A, C, M は定数で、この問題では 0 \le S, A, C \le 15 、 M=256です。

いま、文字列 I を、乱数列 R を使って別の文字列 O に変換したいです。文字列 O は
O_i = ( I_i + R_i ) mod M
で定義されます。
文字列 O のエントロピーが最小になるような S, A, C を答えてください。エントロピーが最小になるような組が複数ある場合は S, A, C が最小になるものを答えてください。
文字列のエントロピー H は
H = - \sum_x \frac{\#(x)}{N} \log \frac{\#(x)}{N}
で定義されます。ここで N は文字列の長さ、 \#(x) はアルファベット x の出現回数です。

解法

S,A,Cを全探索します。16*16*16*256なので間に合います。
AIZU ONLINE JUDGE: Code Review

AOJ1249 Make a Sequence

競技プログラミング AOJ

Make a Sequence | Aizu Online Judge

問題概要

2人のプレイヤーが白と黒の石を使って交互にゲームをプレイする。黒が先手。
n* n 本のペグ(杭)があり、それぞれ n 個までボールを重ねることができる。
ゲーム開始時にはどのペグにもボールはない。

ターンになると、プレイヤーは1つのペグを選び自分の色のボールを1つ置くことができる。そのペグにボールがない場合は自分のボールがペグの一番下になり、そうでない場合はそのペグの一番上にあるボールの上に重なる。
縦または横または斜めに自分の色のボールが m 個以上連続した列ができるとそのプレイヤーの勝ちになる。勝者が決まる前にボールを置く場所がなくなったりゲームをやめてしまったら引き分けになる。（勝者が決まっているのにプレイを続行している入力があることに注意する。）

ターン数 p とボールを置いたペグの座標 (x_i, y_i) （ 1 \le i \le p ）が与えられるので、どちらのプレイヤーが勝ったかを判定する。黒が勝った場合は"Black"、白が勝った場合は"White"、引き分けだった場合は"Draw"を出力する。また引き分けでないときは勝敗が決まったターン数も出力する。

制約

3 \le m \le n \le 7
1 \le p \le n^3
1 \le x_i, y_i \le n

解法

それぞれのターンごとに、勝者が決まるかどうかを判定します。
ある位置にボールを置いたとき、ボールが m 個連続しているかどうかを見る必要があるのは13方向（くわしくは問題文参照）で、各方向につき n 個見ればいいので、全体で p * 12 * n 回になって間に合います。

愚直に書くと行数がアになるのでもう少し綺麗に書きたいですね。
AIZU ONLINE JUDGE: Code Review