Atcoder Problems という競プロを勉強する上でのコンテンツがあります。URL
今回は、hard100問の内、1問目を解説していきたいと思います。
問題名 【D – Gathering Children】
問題
LとRからなる文字列Sが与えられます。各マスには子供がいて、子供はLと書かれたマスなら左に行き、Rと書かれたマスなら右に行きます。この動作を10の100乗繰り返したら、子どもたちの配置はどうなるか
- 入力
S(文字列) - 出力
10の100乗後の子供の位置
考察
愚直に計算したら、10の100乗の計算をしなければならないので、TLEです。
しかし、Sの制約が2 <= s <= 10**5なので、sについては全探索できそうです。なので、Sの1つ1つについて考えていきます。
規則性を見つける
今回の条件をよくよく考えてみると実は4つのパターンからなることがわかります
- パターン1 ・・・〇〇RR〇〇・・・の場合
この場合は、10**100回やれば子供は右に寄ります - パターン2・・・〇〇LL〇〇・・・の場合
この場合は、10**100回やれば子供は左に寄ります - パターン3 ・・・〇〇RL〇〇・・・の場合
RLのところを子供は反復します。 - パターン4 ・・・〇〇LR〇〇・・・の場合
Lよりも左側にいる子供はR側に行くことはなく、Rよりも右側にいる子供はL側に行くことはないです。
一応、これだけでも問題を解くことができるのですが、、、
せっかくなのでもう少し問題について考察を深めていきましょう。
Sの中身(R or L)の特徴について考える
今回の問題、試行を重ねてみると必ず ○○RL○○ となっているところに子供が集まります。
なぜなら、〇〇RL〇〇となっていた場合、Rよりも左側の子どもたちはRよりもLよりも左側に行くことができず、同様にLよりも右側にいる子どもたちは、Rよりも右側に行くことができないからです。
つまり、RLとなっているところの数だけ子どもたちが集まる場所があり、その場所に集まる子どもたちの範囲は、〇〇LR〇〇・となったRから、次の〇〇LR〇〇となったLの範囲までです。
(最初と最後のみ例外)
以下の場合だったら、子どもたちの集まる場所は太字の3箇所となる。(同系色が集まる範囲)
RRRRLLLRLRLLL
では次に「最終的にRとLどちらの位置になるか？」について考えていきます。
RLのどちらに移動するか
それは、i番目が奇数なら奇数番目のR or L の位置になります。
理由
RLは隣り合う場所なので、必ず、どちらかが偶数番目でもう一方が奇数番目になります。
今回、試行回数が10**100(偶数回)なので、最終的な盤面は、
i番目の数が偶数であれば、RLの偶数の方に集まり、奇数ならその逆の場所に集まるためです。
コード
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def II(): return int(sys.stdin.readline())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def S(): return sys.stdin.readline().rstrip()
#入力を受け取るためのスニペット
box = S()
index = [0,]
check = []
ans = [0 for i in range(len(box))]
Even_cnt = 0
Odd_cnt = 0
gather = 0
for i in range(len(box)-1):
if box[i] == box[i+1]:
if i%2 == 0:
Even_cnt += 1
else:
Odd_cnt += 1
elif box[i] == "R" and box[i+1] == "L":
gather = i
if i%2 == 0:
Even_cnt += 1
flg = True
else:
Odd_cnt += 1
flg = False
elif box[i] == "L" and box[i+1] == "R":
if i%2 == 0:
Even_cnt += 1
else:
Odd_cnt += 1
if flg:
ans[gather] = Even_cnt
ans[gather+1] = Odd_cnt
else:
ans[gather] = Odd_cnt
ans[gather+1] = Even_cnt
Odd_cnt = 0
Even_cnt = 0
if (len(box)-1) %2 == 0:
Even_cnt += 1
else:
Odd_cnt += 1
if flg:
ans[gather] = Even_cnt
ans[gather+1] = Odd_cnt
else:
ans[gather] = Odd_cnt
ans[gather+1] = Even_cnt
print(*ans,sep = " ")
まとめ
制約をみて、絶対は計算量オーバーするであろう問題は、規則性を使う問題が多いです。
なので、今回みたいな問題のときでも、手を動かしてみて、規則性を見つけ解決の糸口にしてみてください！！
コメント