今回のABCは定時参加できなかったので、後日のんびり解きました。
A問題
入力として長さが$|S|=|T|+1$である文字列$S,T$を受け取り、$S$と$T$末尾の1文字を除いた文字列が等しいかそうでないかを出力する問題。
S = str(input())
T = str(input())
if S == T[:-1]:
print('Yes')
else:
print('No')
B問題
$ 1,0,-1 $のカードがそれぞれ$ A,B,C $枚あり、その中から$ K $枚を取り出す。その時取りうるカードの和の最大値を求める問題。スコアの高いものから選び、合計を出力する。
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$通りと考えられるので、全探索でもきっと間に合う。
全ての選び方について理解度を求め、条件を達成しているかを判定する。条件が達成されていれば、購入費を更新する。
#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$に記録して、剰余を用いて求める。
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問題はもっといい解法がありそうですね。