2018-10-12

AOJ2243 Step Step Evolution

問題概要

3*3のマスを左右どちらかの足で順番に踏むゲームをする。与えられる指示に従って左右の足で交互にマスを踏んでいきたいが、右足よりも右側のマスを左足で踏んだり、左足よりも左側のマスを右足で踏んだりすることはしたくないので、そのような場合は同じ足で続けてマスを踏むことになる。
踏むマスの順が文字列で与えられるので、左右の足で交互にマスを踏めない回数を答えよ。

制約

文字列の長さは $10^5$ 以下

解法

一番最初にマスを踏む足（右足か左足）を決めると、求める回数は一意に定まるので、小さい方を答えれば良いです。
AIZU ONLINE JUDGE: Code Review

2018-10-12

AOJ1316 The Sorcerer's Donut

競技プログラミング AOJ

The Sorcerer's Donut | Aizu Online Judge

問題概要

ドーナツ状の物体の表面に文字列が書かれている。ある文字から8方向に移動し続けてできる文字列のうち、2度以上出現する文字列で長さが最長のものを答えよ。複数存在する場合は辞書順最小のものを答えよ。

制約

$3 \le h \le 10$
$3 \le w \le 20$

解法

すべての文字について、その文字からはじまる文字列を全部調べ、mapなどに入れて、2度以上出現する文字で最長なものを探せばいいです。
AIZU ONLINE JUDGE: Code Review

2018-10-12

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

2018-10-12

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

2018-10-10

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

2018-10-10

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$ はいくつあるか答えよ。