2018-10-14

AOJ1237 Shredding Company

問題概要

整数 $t$ と数字のみからなる文字列 $num$ が与えられる。文字列 $num$ をいくつかの箇所で分割し、分割後の数の総和が $t$ 以下になるようにするとき、総和の最大値とそのときの分割の仕方を答えよ。なお、分割後の数の総和が $t$ 以下にならないときは"error"、答えとなる分割の仕方が複数存在するときは"rejected"と出力せよ。

制約

$t < 10^6$
$| num | \le 6$

解法

分割の仕方は高々 $2^{|num|-1}$ 通りなので、全て試して、総和が $t$ 以下になる最大のものを調べてあげればよいです。
AIZU ONLINE JUDGE: Code Review

2018-10-13

AOJ1325 Ginkgo Numbers

競技プログラミング AOJ

Ginkgo Numbers | Aizu Online Judge

問題概要

Ginkgo Numbersは整数 $m, n$ のペア $(m,n)$ です。
Ginkgo Numbersの掛け算は $(m, n)$ ・ $(x, y)$ = $(mx − ny, my + nx)$ で定義されます。
$(m, n)$ ・ $(x, y)$ = $(p, q)$ となるとき、 $(m, n)$ は $(p, q)$ の約数です。

どんなGinkgo number $(m, n)$ にも少なくとも8つの約数が存在し、それらは $(1, 0)$ , $(0, 1)$ , $(-1, 0)$ , $(0, -1)$ , $(m, n)$ , $(-n, m)$ , $(-m, -n)$ , $(n, -m)$ です。もし $m^2 + n^2 > 1$ ならば、これらの8つの約数はすべて異なります。

$m^2 + n^2 > 1$ かつ約数がちょうど8つのGinkgo number $(m, n)$ をprimeと呼びます。与えられた $(m, n)$ がprimeであればPを、そうでないならCを出力してください。

なお、Ginkgo numberには以下の2つの性質があります。

$m^2 + n^2 > 0$ の場合、 $mp + nq$ と $mq − np$ がともに $m^2 + n^2$ を約数としてもつときのみ、 $(m, n)$ は $(p, q)$ の約数である。
$(m, n)$ ・ $(x, y)$ = $(p, q)$ ならば、 $(m^2 + n^2)(x^2 + y^2) = p^2 + q^2$ が成り立つ。

制約

$1 < m^2 + n^2 < 20000$

解法

$m^2 + n^2$ のすべての約数 $a$ について、 $a = x^2 + y^2$ となる $x,y$ が存在するなら、 $xm+yn$ と $xn-ym$ がともに $x^2+y^2$ で割り切れるか調べ、もし割り切れるなら $(x, y)$ は $(m,n)$ の約数となる。このようにして調べていき、 $(m,n)$ の約数が8個かどうかで判定すれば良い。

AIZU ONLINE JUDGE: Code Review

2018-10-12

AOJ2243 Step Step Evolution

競技プログラミング AOJ

Step Step Evolution | Aizu Online Judge

問題概要

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$ ターン以内に駒がゴールに到達する確率を求めてください。