B - あみだくじ
時間制限 : 2sec / スタック制限 : 10MB / メモリ制限 : 64MB問題文
高橋君は学校で班のリーダーを決めなければいけなくなったので、あみだくじを用いて決めることにしました。あみだくじとは、複数の縦線から 1 本を選び、その上端から下端へと辿っていき、
途中で横線があれば、その横線を通り繋がっている隣接する縦線へと移動し、また下へと進みます。
今日はたまたま手元に紙がなかったので、パソコン上で |、-、o を用いて以下のようなあみだくじを作りました。
| | | | | | | | |
|-| | |-| | |-| |
| | |-| | |-| | |
| |-| | | | | |-|
| | | |-| | | |-|
| | |-| |-| | | |
|-| | |-| | |-| |
| | | | | |-| | |
oo がある位置に到達した人がリーダーになります。実は高橋君はリーダーになりたかったので、どの縦線を選べば o に辿り着くのか知りたいです。
左から何番目の縦線を選べばリーダーになれるのかを求めなさい。
入力
入力は以下の形式で標準入力から与えられる。入力は L+2 行ある。N L |x|x|‥‥| |x|x|‥‥| |x|x|‥‥| : : : : : : : : | | |‥‥| y y y‥‥y
1 行目には、あみだくじの縦線の本数を表す整数 N(1≦N≦10) と
あみたくじの長さを表す整数 L(1≦L≦20)が与えられる。
2 行目からの L 行には、あみたくじの形が与えられる。
i 行目 (2≦i≦L+1) には 2N−1 文字の記号が与えられる。
各行の j 番目の記号は、以下のようになっている。
j が奇数の時：|
j が偶数の時(上記のxの位置)：- または (空白)
| はあみだくじの縦線を表し、-はその両端の縦線を繋ぐ横線であることを表す。
また、空白はその位置に横線が無いことを表す。
| を 1 つ挟んで左右に隣り合ったxの位置の両方が - という入力は存在しない。
L+2 行目には 2N−1 文字の記号が与えられる。
各行の j 番目の記号は、以下のようになっている。
j が奇数の時(上記のyの位置)：o または (空白)
j が偶数の時： (空白)
o は L+2 行目にただ 1 つのみ与えられる。
出力
あみだくじを辿って o に到達するために選ぶべき縦線は左から何番目か 1 行で出力せよ。なお、最後には改行を出力せよ。
出典
B: あみだくじ - AtCoder Regular Contest #006 | AtCoder回答
AtCoder/arc006_2.php at master · wada811/AtCoder · GitHub<?php
fscanf(STDIN, "%d %d", $col, $row);
for($i = 0; $i < $row; $i++){
for($j = 0; $j < 2 * $col - 1; $j++){
$amida[$i][$j] = fgetc(STDIN);
}
fgetc(STDIN); // throw line feed code
}
$goal = fgets(STDIN);
$pos = strpos($goal, 'o');
for($i = $row - 1; $i >= 0; $i--){
if($pos - 2 >= 0 && $amida[$i][$pos - 1] === '-'){
$pos -= 2;
}elseif($pos + 2 < count($amida[$i]) && $amida[$i][$pos + 1] === '-'){
$pos += 2;
}
}
$pos /= 2;
echo ++$pos.PHP_EOL;
?>
当たりから探すほうが簡単なので当たりの位置を取得したら左右を確認しつつ上に遡る。
もちろん境界条件も忘れない。
文字列の位置から何本目のアミダかに変換して出力するだけ。
今見直すと出力と演算を同時に行なっているのは筋が悪いな…。次回から気をつける。