ARC006 B - あみだくじ
備忘録
問題
回答
import sys import os import math import bisect import itertools import collections import heapq import queue import array import time # 時々使う # import numpy as np # from decimal import Decimal, ROUND_HALF_UP # from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall # 再帰の制限設定 sys.setrecursionlimit(10000000) def ii(): return int(sys.stdin.buffer.readline().rstrip()) def il(): return list(map(int, sys.stdin.buffer.readline().split())) def fl(): return list(map(float, sys.stdin.buffer.readline().split())) def iln(n): return [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)] def iss(): return sys.stdin.buffer.readline().decode().rstrip() def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split())) def isn(n): return [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)] def lcm(x, y): return (x * y) // math.gcd(x, y) MOD = 10 ** 9 + 7 # MOD = 998244353 INF = float('inf') def main(): if os.getenv("LOCAL"): sys.stdin = open("input.txt", "r") N, L = il() drawing = [] for _ in range(L): drawing.append(iss()) bingo = input().split(' ') for i in range(N): now = i for j in range(L): if now < N - 1 and drawing[j][now*2 + 1] == '-': now += 1 elif 0 <= now and drawing[j][now*2 - 1] == '-': now -= 1 else: if len(bingo) > now * 2 and bingo[now*2] == 'o': print(i+1) exit() if __name__ == '__main__': main()
考え方
基本的にはあみだくじのルール通り、現在位置の左右どちらかに-
が存在していた場合に、
現在位置を更新して、次の列へ進むだけ。
しかし、文字列であみだくじが表現されており、縦棒の間にスペースが存在するため
左右移動の判定が少々面倒になっている。
0-based
で考えると、
現在地が最も右ではない、かつ現在位置 * 2 + 1
の位置に-
が存在している場合に現在位置を一つ右へ移動させ、
現在位置が最も左でない、かつ現在位置 * 2 - 1
の位置に-
が存在している場合に現在位置を一つ左へ移動させる。
あとは最終的に到達した地点にo
があるかないかを判定するだけ。
最後の判定時にも、スペースの有無で文字列の長さが変わるため、範囲外を選択しないように注意が必要。