2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

ABC167 A-D問題を解く

Last updated at Posted at 2020-05-11

今回の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問題はもっといい解法がありそうですね。

2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?