AtCoder Beginner Contest 167 に C# で参加した記録

AtCoder Beginner Contest 167 に C# で参加した記録

AtCoder Beginner Contest 167 – AtCoder

ABC167 にC#で参加しました。結果はABCDの4問ACでした。

パフォーマンスは1300弱でレートは微増でした。最近はこの辺のパフォーマンスに安定してしまっていて、何とか打破したかったのですがかないませんでした。茶diffまでしか解けてないのに水パフォは不幸中の幸いでした。

今回のコンテストではE問題が鬼門でした。D問題ACが20分くらいだったのですが、E問題がさっぱりでした。数え上げ、組み合わせ問題は厳しいですね。そうそうに諦めてF問題と格闘していましたが、何ともならず終了でした。

以下、振り返ります。

A – Registration

A – Registration

高橋君はとあるWebサービスに会員登録しようとしています。

まずIDを S として登録しようとしました。しかし、このIDは既に他のユーザーによって使用されていました。

そこで、高橋君は S の末尾に 1 文字追加した文字列をIDとして登録することを考えました。

高橋君は新しくIDを T として登録しようとしています。これが前述の条件を満たすか判定してください。

制約より|T|=|S|+1なので、2つの文字列を比較して、先頭|S|文字が一致するか確認すればよいです。

var ok = true;
for (int i = 0; i < S.Length; i++)
{
    if (S[i] != T[i]) ok = false;
}
if (ok)
{
    Console.WriteLine("Yes");
}
else
{
    Console.WriteLine("No");
}

B – Easy Linear Programming

B – Easy Linear Programming

1 が書かれたカードが A 枚、0 が書かれたカードが B 枚、 −1 が書かれたカードが C 枚あります。

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

制約

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

B問題だからと言って愚直にやろうとすると解けません。制約に注目すると、A,B,C が馬鹿でかい数になっています。ということでちゃんと数学的に計算しなければなりません。

とはいえ難しいことはなくAを最大枚数選び、まだ選べるならBを最大枚数選び、それでも選べるならCを選べばよいです。

if (A >= K)
{
    // AだけでK枚選べるときはK枚A(1のカード)を選ぶ
    Console.WriteLine(K);
}
else if (A + B >= K)
{
    // AとBでK枚選べるとき、Aはすべて選ぶ
    // Bは0なので無視
    var ans = A;
    Console.WriteLine(ans);
}
else
{
    // AとBをすべて選んでもK枚に満たないとき
    // 残りを(K-A-B)枚Cを選ぶ
    // Cの枚数分-1する
    var ans = A - (K - A - B);
    Console.WriteLine(ans);
}

C – Skill Up

C – Skill Up

競技プログラミングを始めた高橋くんは、学びたいアルゴリズムが M 個あります。 最初、各アルゴリズムの理解度は 0 です。

高橋くんが書店に行くと、N 冊の参考書が売っていました。i 番目の参考書 (1≤i≤N) は Ci 円で売られていて、購入して読むことで、各 j (1≤j≤M) について j 番目のアルゴリズムの理解度が Ai,j 上がります。 また、それ以外の方法で理解度を上げることはできません。

高橋くんの目標は M 個すべてのアルゴリズムの理解度を X 以上にすることです。高橋くんが目標を達成することが可能か判定し、可能な場合は目標を達成するのに必要な金額の最小値を計算してください。

制約

• 入力はすべて整数
• 1≤N,M≤12
• 1≤X≤10⁵
• 1≤Ci≤10⁵
• 0≤Ai,j≤10⁵

制約が bit全探索 してくださいと言っています。最近こういう全探索系の問題をたくさん解いていたのですんなりと手が動きました。

方針としては2進数でN桁の数を考えます。例えばN=3の時は2進数3桁の数として以下の8通りあります。

000
001
010
011
100
101
110
111

i桁目が1になっているとき、i番目の参考書を買うことにします。すべての桁を確認して、それぞれのパターンにおいて理解度を計算してすべてX以上の時だけ、答えの候補として最小値を管理します。

実装的に言うと、N桁の2進数は 0以上2<sup>N</sup>-1以下 の範囲にあるのでこれをループして確認します。2のN乗は 1<<N と書くと整数で得られます。Math.Pow(2, N) でもよいのですが、これだと double になって気持ち悪いですしタイプも多くなります。

整数aのi桁目の数は (a >> i) & 1 で得られます。i桁目の数を右にシフトしてずらし1でマスクして1桁目以外の数を0にしています。

// 入力部分省略...
var ans = long.MaxValue;
for (int a = 0; a < (1 << N); a++)
{
    // 金額の合計
    var res = 0L;
    // 理解度
    var rikaido = new long[M];
    for (int i = 0; i < N; i++)
    {
        // 2進数表記i桁目が1の時
        var x = (a >> i) & 1;
        if (x == 1)
        {
            // 参考書iを買う
            res += C[i];
            // 参考書iから得られる理解度を加算する
            for (int j = 0; j < M; j++)
            {
                rikaido[j] += A[i, j];
            }
        }
    }
    // すべての理解度がX以上かどうかを見てる
    if (rikaido.Min() >= X) ans = Math.Min(ans, res);
}
if (ans == long.MaxValue) Console.WriteLine(-1);
else Console.WriteLine(ans);

この問題はbit全探索の典型問題でした。実装も詰まらず5分程度でかけたので成長を感じました。

D – Teleporter

D – Teleporter

高橋王国には N 個の町があります。町は 1 から N まで番号が振られています。

それぞれの町にはテレポーターが 1 台ずつ設置されています。町 i(1≤i≤N) のテレポーターの転送先は町 Ai です。

高橋王は正の整数 K が好きです。わがままな高橋王は、町 1 から出発してテレポーターをちょうど K 回使うと、どの町に到着するかが知りたいです。高橋王のために、これを求めるプログラムを作成してください。

制約

• 2≤N≤2×10⁵
• 1≤Ai≤N
• 1≤K≤10¹⁸

テレポートの使用回数Kが小さいと単純にループしてシミュレートすればよいです。が、今回 10¹⁸ とテレポート回数が大きいのでシミュレートできません。何かしらの工夫が必要になります。

また、1≤Ai≤Nという制約があるのでテレポートを繰り返すとある地点で必ずループします。入力例1だと 1->3->4->1 ... みたいな感じでループします。ループに入るとどれだけKが大きくても余りをとって、周回部分のテレポートをカットできるのでループ箇所を管理します。

ループの開始位置と終了位置、その長さがわかればよいです。K % ループの長さ で得られる回数をループの位置から移動すればよいです。ループの長さはどれだけ大きくても N になるので、計算量 O(N) で解けます。

// 0-indexed にしておく
for (int i = 0; i < N; i++) A[i]--;
// 0からの距離を記録しておく
var dist = new long[N];
for (int i = 0; i < N; i++)
{
    dist[i] = -1;
}

// ループ開始地点, ループ終了地点(次のテレポートでloopSに戻る)
var loopS = 0;
var loopE = 0;
var now = 0;
var d = 0;
// ループするまでテレポートを繰り返す
while (dist[now] == -1)
{
    dist[now] = d++;
    loopE = now;
    now = A[now];
    // K回テレポートができたので終了
    if (d == K)
    {
        Console.WriteLine(now + 1);
        return;
    }
}
loopS = now;

// ループ1周の長さ
var loopdist = dist[loopE] - dist[loopS] + 1;
// 残りの回数をループの長さで余りをとる
K = (K - dist[loopS]) % loopdist;

// ループの開始地点からあまり分テレポートする
now = loopS;
while (K > 0)
{
    K--;
    now = A[now];
}
var ans = now + 1;
Console.WriteLine(ans);

以上。