AtCoder ABC 167

AtCoder

ABCD4完の緑パフォでした。

A - Registration

問題のリンク

概要

  • 以下の二つの文字列が等しいか否か
  • S, 及び Tの末尾を削ったもの

制約

  • 1 ≤ |S| ≤ 10
  • |T| = |S| + 1

考察

特になし

コード

S = input()
T = input()

if S == T[:-1]:
    print('Yes')
else:
    print('No')



B - Easy Linear Programming

問題のリンク

概要

  • 1が書かれたカードが A枚、 0が書かれたカードが B枚、 −1が書かれたカードが C枚あります。これらのカードから、ちょうど K枚を選んで取るとき、取ったカードに書かれた数の和として、 ありうる値の最大値はいくつか。

制約

  • 入力は全て整数である。
  • 0 ≤ A, B, C
  • 1 ≤ K ≤ A + B + C ≤ 2×10 ^{9}

考察

特になし

コード

A, B, C, K = map(int, input().split())

if K<=A:
    print(K)
elif A<K<=A+B:
    print(A)
elif A+B<K<=A+B+C:
    print(A-(K-A-B))



C - Skill Up

問題のリンク

概要

  • 高橋くんは学びたいアルゴリズムが M個あり、スタート時点で M個全て理解度は 0である。
  • 参考書が N冊ある。 i番目の参考書を読むとそれぞれのアルゴリズムの理解度が A_{ij}上がる。また i番目の参考書は C_i円である。
  • 全ての理解度が X以上になるための最小コストを求めよ。

制約

  • 入力は全て整数
  • 1 ≤ N, M ≤ 12
  • 1 ≤ X ≤ 10 ^{5}
  • 1 ≤ C_i ≤ 10 ^{5}
  • 1 ≤ A_{ij} ≤ 10 ^{5}

考察

　とりあえず全探索が間に合いそうなことは分かった。（解説でも全探索しか方法はないと言っていた。）そこで買う or 買わないのbit全探索を実装。ただ、少しコードが長くなって正解するまでに実装ミスを連発してしまった。尚、DFSで実装する方が効率的。

コード

import numpy as np

N, M, X = map(int, input().split())
book = [list(map(int, input().split())) for _ in range(N)]

ans = 10**9

for i in range(1<<N):
    cost = 0
    tisiki = np.array([0]*M)
    cond = [0]*N
    for j in range(N):
        if 1&(i>>j):  # 右シフトして論理積（bit全探索）
            cond[j] = 1
    
    for k in range(N):
        if cond[k]==1:
            b = book[k]
            cost += b[0]
            tisiki += np.array(b[1:])
    
    if np.all(tisiki>=X):
        ans = min(ans, cost)

if ans < 10**9:
    print(ans)
else:
    print(-1)



D - Teleporter

問題のリンク

概要

  • 1 ~ Nまでランダムに番号のついた N個の街がある。
  • それぞれの街にはテレポーテーターが設置されており、それぞれの転送先は A_iである。
  • K回移動した際に泊まっている街を求めよ。

制約

  • 2 ≤ N ≤ 2×10^{5}
  • 1 ≤ A_i ≤ N
  • 1 ≤ K ≤ 10 ^{18}

考察

  • Kが物凄く大きいためそのまま K回for文を回すのは不可能。
  • 一度ループが検出できれば、残っている移動回数から最終的なストップ地点を求めることが可能。
  • 移動していく処理は再帰関数で実装。
  • 他の人のコードを見てるとどうやら再帰関数を使わずwhile文を使って書いてる人もいた。

コード

import sys
sys.setrecursionlimit(10**9)

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

log = []
check = [False]*N

def func(x, iter):
    x = A[x-1]

    if iter+1 == K:
        return x
    if check[x-1]:
        ix = log.index(x)
        loop = log[ix:]
        tmp = (K-iter-1)%len(loop)
        return loop[tmp]
    else:
        log.append(x)
        check[x-1] = True
        iter += 1
        return func(x, iter)

print(func(1, 0))