ABC311復習

■結果

• ABC3完
• C/Dとも再帰で進めましたが、DのBFS実装中に時間切れ。Dの実装は難しかった。

■Ａ問題（First ABC）

３文字全部を見つけたことの判定がポイント。
解く速さを優先して出現文字種類が３文字になったことで判定。

n = int(input())
s = input()

chars=set()
for ii in range(n):
    chars.add(s[ii])
    if len(chars) >=3:
        print(ii+1)
        break

■Ｂ問題（Vacation Together）

• 15分AC。まあOK。
• 最大値を記録する部分はans=max(ans, count)とかでもよい。
  ただ変数名をmaxにするとハマった。pythonで関数名と同じ変数名を使わない方がよい例。

n,d = map(int, input().split())

schedule = []
for ii in range(n):
    schedule.append(input())

ans  = 0
count = 0
for day in range(d):
    free = True
    for ii in range(n):
        if schedule[ii][day] == 'x':
            free = False
            break
    if free:
        count +=1
        ans =max(ans, count)
    else:
        count=0
print(ans)

■Ｃ問題（C - Find it!）

面白い問題。
まずループを探索する処理は再帰がよさそう。ひたすら辿る列を伸ばして過去に同じノードが存在したかをチェックすればよい。気になる単連結ではない点だけれど、どの連結にも必ずループが有る点に気づき、任意の始点から辿ってよいと割り切る。実装時に、過去に同じノードが存在したか O(1)で確認するためsetを使った。45分でAC（やや長い）

import sys
sys.setrecursionlimit(10000000)

n = int(input())
route = list(map(int, input().split()))

l = []
s = set()

def go_next(node):
    if node in s:
        pos = l.index(node)
        print(len(s)-pos)
        print(*l[pos:])
        return
    l.append(node)
    s.add(node) 
    next = route[node-1]
    go_next(next)

go_next(1)

面白かった別解。

なるほどUnionFind。ノード順に処理で平均処理量速そう。

こちらは、ループ検出をコンパクトにwhile文で関数化。非再帰。

強コーダの方によると、C問題は強連結成分(SCC)を検出する問題と捉えることもできるそう。言語によっては強連結成分分解ライブラリも有るらしい。

■D問題（Grid Ice Floor ）

難しかった。
頭の整理と実装に時間が要りそうな感覚が有り、案の定という感じで提出に間に合わず。
startから上下左右に向かう。壁の手前で停止する。停止点をnext_nodeとする。next_nodeが過去辿った経路上なら終点になる、を移動ルールと解釈しよう。
過去通った点の管理には単純にvisited用gridを使う。（後で二重カウントせずに訪れた点を数えるにも都合がよい。）探索はbfsかdfsが良い。bfsにしよう。これで作戦が出来たが、実装に慣れがなくて時間かかる。
数回推敲し下記コードでコンテスト後AC。現状の精一杯かも。

from collections import deque

# up, down, left, right
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

n, m = map(int, input().split())

grid = []
for ii in range(n):
    s = input()
    grid.append(s)

v = [[0] * m for _ in range(n)]

def go_next_node(node, dir):
    x, y = node[0], node[1]
    v[x][y] = 1
    while True:
        cur = v[x][y]
        v[x][y] = 1
        xx = x + dx[dir]
        yy = y + dy[dir]
        if grid[xx][yy] == "#":
            break
        x, y = xx, yy
    if cur == 1:
        return (0, 0)
    return (x, y)

def bfs(start):
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for dir in range(4):
            next_node = go_next_node(node, dir)
            if next_node != (0, 0):
                queue.append(next_node)
    return

#for line in grid:
#    print(*line)

bfs((1, 1))

#for line in v:
#    print(*line)

ans = 0
for line in v:
    ans += sum(line)
print(ans)