今回のABCは定時参加できなかったので、後日のんびり解きました。

A問題

入力として長さが$|S|=|T|+1$である文字列$S,T$を受け取り、$S$と$T$末尾の1文字を除いた文字列が等しいかそうでないかを出力する問題。

A.py

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

B問題

$ 1,0,-1 $のカードがそれぞれ$ A,B,C $枚あり、その中から$ K $枚を取り出す。その時取りうるカードの和の最大値を求める問題。スコアの高いものから選び、合計を出力する。

B.py

A, B, C, K = map(int, input().split())
if K <= A:
    print(K)
    exit(0)
K -= A
if K <= B:
    print(A)
    exit(0)
print(A-(K-B))

C問題

全てのアルゴリズムで$X$以上の理解度をつけるために必要な参考書の購入費を求める問題。条件が達成できない場合は-1を出力する。
考えられる参考書の選び方は$2^N-1$であり、$0\leq N\leq 12$なのでの最大値は$2^{12}-1=4095$通りと考えられるので、全探索でもきっと間に合う。
全ての選び方について理解度を求め、条件を達成しているかを判定する。条件が達成されていれば、購入費を更新する。

C.cpp

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int N, M, X;
    cin >> N >> M >> X;
    vector<vector<int>> A(N, vector<int>(M + 1, 0));
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j <= M; j++)
        {
            cin >> A[i][j];
        }
    }
    int ans = 100000000;
    for (int i = 1; i < (1 << N); i++)
    {
        int score = 0;
        vector<int> x(M, 0);
        for (int j = 0; j < N; j++)
        {
            if ((i >> j) & 1)
            {
                for (int k = 0; k < M; k++)
                {
                    x[k] += A[j][k + 1];
                }
                score += A[j][0];
            }
        }
        bool flag = true;
        for (int j = 0; j < M; j++)
        {
            if (x[j] < X)
            {
                flag = false;
                break;
            }
        }
        if (flag)
        {
            ans = min(ans, score);
        }
    }
    if (ans == 100000000)
    {
        cout << -1 << endl;
    }
    else
    {
        cout << ans << endl;
    }

    return 0;
}

D問題

桃鉄みたいな問題。町1から移動して$K$回移動したときの町番号を求める問題。
$0\leq K\leq 10^{18}$なので、単純に求めるとTLEしてしまう。でも、町の数は$0\leq N\leq 2*10^{5}$なので、どのようにループするかを求めてしまえば剰余を使って求めることができる。そのために、まずどのようにループするかを求める。
$X$で今までに来たことのある町を記録し、$r$で町1からどのように遷移するかを記録する。1つ進むごとに$K$を$-1$して、まだ来たことのない町だったら$X,r$に記録する。もし、来たことのある町だったら、1周したことになり、今いる町よりも後ろにある$r$の要素でループすることになる。その町を$R$に記録して、剰余を用いて求める。

D.py

N, K = map(int, input().split())
A = list(map(int, input().split()))
X = {1}
r = [1]
for i in range(0, N):
    idx = A[r[-1]-1]
    if K == 1:
        print(idx)
        exit(0)
    else:
        if X.isdisjoint({idx}):
            r.append(idx)
            X.add(r[-1])
            K -= 1
        else:
            R = r[r.index(idx):]
            K -= 1
            break
print(R[K % len(R)])

D問題はもっといい解法がありそうですね。

ABC167 A-D問題を解く

A問題

B問題

C問題

D問題