ABC311の解説

ABC311のA～D問題の解説を書いてみたいと思います。

A問題　First ABC

この問題は、特に難しいアルゴリズムは使いません。
入力された文字列を配列などに格納しておいて、前から見ていきます。
そして、A、B、Cそれぞれが全部出たというタイミングで、今いる場所を出力します。
（↑なんかめちゃくちゃ当たり前のこと言っている気がします…でもこれでAC）

Pythonの例

n=int(input())
s=list(input())
hako=["A","B","C"]
for i in range(len(s)):
  if s[i] in hako:
    hako.remove(s[i])
  if len(hako)==0:
    print(i+1)
    break

B問題　Vacation Together

まず、一人目の予定を確認して、行ける日を配列などに格納しておきます。
例えば、以下のような入力だとしたら（入力例１）

3 5
xooox
oooxx
oooxo

このとき、一人目の人の空いている日をリストに格納すると

[2,3,4]

となります。

そして、ここから、二人目の人、三人目の人…を見ていきます。例えば二人目の人を見たときは
・リストに入っている日にちが開いているかを確認する
→もし空いていれば、リストのその要素はそのまま
→もし空いていなければ、その要素はリストから削除する

これを繰り返していくことによって、みんなのいける日だけがリストに残ることになります。

ここまでくれば、連続している日の中で、最長の物はすぐにわかります。日にちの差が一日以内なら、連続していると分かるので、リストの一つ目の要素から順番に確認して、その中で最長のものの日数を保存していきます。

Pythonの例

n,d=map(int,input().split())
s=list(input())
hako=[]
for i in range(len(s)):
  if s[i]=="o":
    hako.append(i)
for i in range(n-1):
  s=list(input())
  for ipp in range(len(s)):
    if not ipp in hako:
      continue
    if s[ipp]=="x":
      hako.remove(ipp)
if len(hako)==0:
  print(0)
  exit()
hako=sorted(hako)
mae=hako[0]
count=1
saidai=0
for i in range(len(hako)-1):
  if hako[i+1]-1==mae:
    count+=1
    mae=hako[i+1]
  else:
    saidai=max(saidai,count)
    count=1
    mae=hako[i+1]
print(max(saidai,count))

C問題　Find it!

この問題は、単純にグラフの矢印を追っていけば解くことができます。

・まず、適当に頂点を選びます（頂点1とか…）
・そこから、行くことのできる頂点に行きます
・どんどんいける頂点をまわっていきます。

そして、今までに来たことのある頂点に来たら、ストップ！！！そこからは簡単です。
同じ頂点からは、同じような生き方しかないので、ループしているのは、前にその頂点に来た時から、次にその頂点に着く一歩手前までが閉路となっています。

例えば、入力例３を参考にすると以下のようになります（番号は頂点の番号）

１→３→４→７→８→２→７…

７に来れば、また８→２→７と回るので閉路になっているのはここだとわかります
ですから、頂点の数３と、７、８、２を出力すればよいです。

Pythonの例

n=int(input())
a=list(map(int,input().split()))
irane=set()
check=1
for i in range(n):
  if i in irane:
    continue
  stack=[i+1]
  while check==1:
    hako=a[stack[len(stack)-1]-1]
    if hako in irane:
      stack.append(hako)
      check=0
      break
    irane.add(hako)
    stack.append(hako)
  if check==0:
    break
hako=stack[len(stack)-1]
iti=len(stack)-2
while iti>=0:
  if stack[iti]==hako:
    stack=stack[iti:len(stack)-1]
    break
  iti-=1
print(len(stack))
print(*stack)

D問題　Grid Ice Floor

この問題は、深さ優先探索というアルゴリズムを使用します。このアルゴリズムを使えば、行けるところをもれなくカウントすることができます。

こんな動きをします（だいたい）
・スタートからいけるところに行く。
・いけるところをどんどん進んでいく。
・もし、行ける方向が二つ以上あるような分岐点に来たら、そこの位置をメモする。そのあと、どちらかの道を選んでまた進む。
・もし行き止まりに来てしまい、どこにもいけなくなってしまったら一番最近におとずれた分岐点のところまで戻り、さっきは選ばなかった道の方に進む。また、一度行った方にはいかないようにする。

この操作を続けていくと、最終的にスタート地点まで戻ります。スタート地点まで戻ってきたらこの操作を中止して、行くことのできた座標を出力します。

…とこのように行けるところが全部わかるのが深さ優先探索です。おもにグラフの問題などで使われていますが、この問題にも使うことができます。

と、ここまで書いてきましたが、この問題はグラフの問題と違う注意点があります。それは、この問題では岩にぶつかるまではすべっている設定なのでまがれないということです。まあ、グラフにたとえてみるのなら岩にぶつかる地点が頂点で、それ以外が辺ということになると思います。途中で曲がれないようにする実装が入ったことで、今回の問題は緑diffになったんじゃないかと思います（単純な深さ優先探索の問題は個人的なイメージだと茶diff）。

ぼくは、この滑っている途中でまがらないようにこんな感じのアルゴリズムにしました。

・ある頂点から、進むとき、まずはその頂点の北、東、南、西、それぞれが氷になっていて進むことができるかどうかを確かめます。
→例えば、右方向にだけ岩がなく氷ですすむことができたとします。
・そしたら、見ていく座標をどんどん右にずらして、氷が何マス続いているのかを確認します。
・そして、岩のある座標についたら、そのひとつ前の座標で止まることができるとわかります。

…説明してみましたが、ぼくの説明はとてもとても下手くそな気がします…

↓なんかめちゃくちゃ簡易なもので説明
＃＝岩、.＝氷　s=スタート地点

s . . . . #

こんな感じに、スタート地点から右方向に進むことができて、どこで止まるかを確かめたいとします。スタート地点の座標を(1,1)だとすると、どんどん右にずれるように座標を変化させていきます。

今回の場合だと(1,2)　→　(1,3) .....という風に座標を変化させていくことによって、どんどん右に進むことができます。
このように確認していき、岩が出たところでこの操作を終了して、深さ優先探索を続けます。

…やっぱり説明が下手くそな気がしますが、ネットで深さ優先探索の記事などを読むと、よりわかりやすいかもしれません。

n,m=map(int,input().split())
rotti = [[0] * 2 for i in range(n)]
for i in range(n):
  rotti[i]=list(input())
stack=[[1,1]]
irane=set()
irane.add("1a1")
while len(stack)>0:
  check=1
  now_y=stack[len(stack)-1][0]
  now_x=stack[len(stack)-1][1]
  ano=[]
  #上に向かう
  while rotti[now_y-1][now_x]!="#" and now_y>0:
    now_y-=1
    ano.append(str(now_y)+"a"+str(now_x))
  if check== 1 and not str(now_y)+"a"+str(now_x) in irane:
    irane.add(str(now_y)+"a"+str(now_x))
    check=2
    stack.append([now_y,now_x])
  #右に向かう
  if check==1:
    now_y=stack[len(stack)-1][0]
    now_x=stack[len(stack)-1][1]
  while check==1 and rotti[now_y][now_x+1]!="#" and now_x<m-1:
    now_x+=1
    ano.append(str(now_y)+"a"+str(now_x))
  if check== 1 and not str(now_y)+"a"+str(now_x) in irane:
    irane.add(str(now_y)+"a"+str(now_x))
    stack.append([now_y,now_x])
    check=3
  #下に向かう
  if check==1:
    now_y=stack[len(stack)-1][0]
    now_x=stack[len(stack)-1][1]
  while check==1 and rotti[now_y+1][now_x]!="#" and now_y<n-1:
    now_y+=1
    ano.append(str(now_y)+"a"+str(now_x))
  if check== 1 and not str(now_y)+"a"+str(now_x) in irane:
    irane.add(str(now_y)+"a"+str(now_x))
    stack.append([now_y,now_x])
    check=4
  #左に向かう
  if check==1:
    now_y=stack[len(stack)-1][0]
    now_x=stack[len(stack)-1][1]
  while check==1 and rotti[now_y][now_x-1]!="#" and now_x>0:
    now_x-=1
    ano.append(str(now_y)+"a"+str(now_x))
  if check== 1 and not str(now_y)+"a"+str(now_x) in irane:
    irane.add(str(now_y)+"a"+str(now_x))
    stack.append([now_y,now_x])
    check=5


  for ipp in range(len(ano)):
    irane.add(ano[ipp])
  if check==1:
    stack.pop()
    continue
print(len(irane))

最後までありがとうございました。

rotti-coder.hatenablog.com