💡
ABC346 B - Pianoの振り返り
PHPを使用しています
考察
「文字列 wbwbwwbwbwbw を無限に繰り返してできる文字列をSとおきます」
という一文があるため、無限の文字列から探索していく方法を最初に考える。
↓
そんな事をしたら処理が終わらん。
そもそも探索に無限の文字列は必要なのか?
↓
wbwbwwbwbwbwは繰り返しであるから、ある程度までいったら探索を終わればいいのでは?
白鍵 W 個と黒鍵 B 個の合計の上限はあるか?
↓
問題に以下の条件の記載あり
0≤W,B≤100
つまりWとBの合計の上限は200である
↓
文字列の先頭から上限200ずつずらして調べる。そのとき最初のパターンにもどるのは?→wbwbwwbwbwbwの最後のwからの200文字を調べたときである
↓
つまり調べるべき最大の文字列は200+(wbwbwwbwbwbwの文字数)= 200 + 12 =212
↓
ざっくり12×20=240文字作ればいいのでは?
ということで、元になる文字列Sを作る
$s = str_repeat('wbwbwwbwbwbw', 20);
あとはこの文字列を先頭から順番に含まれている文字種の個数を数え、if文でW個とB個が合致したときに"Yes"を返せばOK。
使った標準関数
str_repeat
文字列を指定の回数リピートする
substr
指定した文字列の一部を取得する
substr(文字列, 開始位置, 抜き出す文字数)
substr_count
指定した文字数の数をカウントする
substr_count(文字列, カウントしたい文字or文字列)
実装
<?php
$input = trim(fgets(STDIN));
list($w, $b) = explode(' ', $input);
$s = str_repeat('wbwbwwbwbwbw', 20);
while (true) {
for ($i = 0; $i < 12; $i++) {
$substring = substr($s, $i, $w + $b);
$count_w = substr_count($substring, 'w');
$count_b = substr_count($substring, 'b');
if ($count_w == $w && $count_b == $b) {
echo "Yes" . "\n";
return;
} else {
continue;
}
}
echo "No" . "\n";
return;
}
Discussion