ABC341 A-D問題の解説（Python）

はじめに

AtCoder Beginner Contest（略称：ABC）とは、AtCoderが週末に開催している、競技プログラミングコンテストのことです。

A-D問題について、自身の復習も兼ねて説明できればと思います。誤った記述やより良い解法などあれば、コメントをいただけると幸いです。

ABC341

A – Print 341

問題

A問題

N個の0とN+1個の1からなる、0と1が交互に並んだ文字列を出力する問題です。（両端は1）

思考の筋道

N=3のとき、”1010101″となります。
この場合、”10″を3回出力し、末尾に”1″を加えればよいですね。

コード

N = int(input())
print("10" * N + "1")

B – Foreign Exchange

問題

B問題

N個の国があり、両替を利用して国Nの通貨をなるべく多くする問題です。両替はインデックスが隣の国同士でのみ可能です。

思考の筋道

国Nの通貨は、国N-1の通貨から両替できます。そしてその国N-1の通貨は、国N-2の通貨から両替できます。同様に考えると、両替は国1の通貨まで遡ります。

つまり、前から考えると
国1の通貨を最大限、国2の通貨に両替
国2の通貨を最大限、国3の通貨に両替
……
国N-1の通貨を最大限、国Nの通貨に両替
としていけば、国Nの通貨をなるべく多くできます。

コード

N = int(input())
A = list(map(int, input().split()))

for i in range(N - 1):
    S, T = map(int, input().split())
    A[i + 1] += T * (A[i] // S)

print(A[-1])

C – Takahashi Gets Lost

問題

C問題

H行N列のグリッドがあり、各マスは陸か海のどちらかです。はじめ、高橋くんがどの位置にいるかは分かりません。LULDRなどの与えられた移動方法で、ずっと陸のマスのみを通って移動できるはじめの位置が何通りあるかを調べる問題です。

思考の筋道

高橋くんがはじめスタートするマスの選択肢は、制約から500^2以下です。そのそれぞれの選択肢に対し、N回移動が出来るか確かめます。Nも500以下のため、計算量は全体で500^3（1.25×10^8）となります。かつかつのラインではありますが、制限時間が3秒のためギリギリ通ります。

要は、実装は少し面倒ですが、ただの全探索の問題ということです。

なお、グリッドの外周のマスは海であることから、移動によりインデックスが範囲外になることは気にしなくてよいです。

コード

H, W, N = map(int, input().split())
T = input()
S = [input() for _ in range(H)]

count = 0

for i in range(1, H - 1):
    for j in range(1, W - 1):
        if S[i][j] == "#":
            continue
        x, y = i, j
        flg = True
        for char in T:
            if char == "L":
                y -= 1
            if char == "R":
                y += 1
            if char == "U":
                x -= 1
            if char == "D":
                x += 1
            if S[x][y] == "#":
                flg = False
                break
        if flg:
            count += 1

print(count)

D – Only one of two

問題

D問題

正整数N, M, Kが与えられます。正の整数であって、NとMのちょうど一方で割り切れる数のうち小さい方からK番目のものを出力する問題です。

思考の筋道

正整数aに対し、a以下の正整数でNとMのちょうど一方で割り切れる数の個数は、
（aをNで割った商）+（aをMで割った商）ー（aをNとMの最小公倍数で割った商）× 2 となります。分からない方は、ベン図を書いて考えましょう。

さて、NとMのちょうど一方で割り切れる数のうち小さい方からK番目の数とは、（aをNで割った商）+（aをMで割った商）ー（aをNとMの最小公倍数で割った商）× 2 = K となる最小のaのことです。この最小値は二分探索によって、効率よく求めることができます。

コード

import math
N, M, K = map(int, input().split())
L = math.lcm(N, M)

def solve(mid):
    return mid // N + mid // M - mid // L * 2 >= K

left, right = 0, 10 ** 20
while right - left > 1:
    mid = (left + right) // 2
    if solve(mid):
        right = mid
    else:
        left = mid
print(right)