足跡-sokuseki-

りかの日進月歩の記録

AOJ1325 Ginkgo Numbers

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

AOJ2243 Step Step Evolution

Step Step Evolution | Aizu Online Judge

問題概要

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

制約

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

解法

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

AOJ1316 The Sorcerer's Donut

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

AOJ1345 Bit String Reordering

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

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

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

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