seiのエンジニア成長記

D – Lucky PIN解説　三井住友信託銀行プログラミングコンテスト2019解いてみた

Atcoder 頭の上にはてなが浮かんでいる男性

こんにちは！seiです！

  • Atcoderの解説を読んでもよくわからない
  • もっと詳しい解説はないだろうか？

 

この記事はLucky PINを詳しく解説した記事です。
Atcoderを初めて15日経過しましたが、初心者なりの悩みも出てきたので、その解決策も紹介しています！

 

目次

Lucky PIN問題概要

N桁のラッキーナンバーSから3桁だけ残し、左から読んで設定する場合、設定される可能性のある暗証番号の数を求める問題です。
制約は以下の通り。
4≤N≤30000
S は半角数字からなる長さN の文字列

Lucky PINの解答

早速解説です。この問題は全探索アルゴリズムで解くことができます。何を全探索するのか考える必要があります。

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

int main()
{

    int n, next_index[30005][10], result = 0;
    string s;
    cin >> n >> s;

    // ありえない外れ値作成
    for (int i = 0; i <= 9; i++)
    {
        next_index[n][i] = n;
    }

    for (int i = n - 1; i >= 0; i--)
    {
        for (int j = 0; j <= 9; j++)
        {
            next_index[i][j] = next_index[i + 1][j];
        }
        next_index[i][s[i] - '0'] = i;
    }

    for (int i = 0; i <= 9; i++)
    {
        for (int j = 0; j <= 9; j++)
        {
            for (int k = 0; k <= 9; k++)
            {
                int curIndex = next_index[0][i];
                curIndex++;
                curIndex = next_index[min(curIndex, n)][j];
                curIndex++;
                curIndex = next_index[min(curIndex, n)][k];

                if (curIndex < n)
                {
                    result++;
                }
            }
        }
    }

    cout << result << endl;

    return 0;
}

 

以下のコードでは現在のインデックス位置から、一番近い次の0~9の数字が存在するインデックスのデータを作成しています。例えば0224の文字列の場合に、現在indexが0の位置にいて、右に進行していくときを考えます。最も近い0~9の数字のインデックス位置を考えます。まず0について、index0の位置から見て次の0のindex位置は「0」になります。1は存在しないので、あり得ないindexの位置「4」を入れます。3,5,6,7,8,9も同様です。2の場合はindex0の位置から見て2は二つありますが、最も近いものを選ぶのでindex位置は「1」となります。
next_index[0]=>[[0]=0,[1]=4,[2]=1,[3]=4,[4]=3,[5]=4,…..[9]=4]となります。

後ろからコピーしてfor文を回していくのがポイントです。

// ありえない外れ値作成
    for (int i = 0; i <= 9; i++)
    {
        next_index[n][i] = n;
    }

    for (int i = n - 1; i >= 0; i--)
    {
        for (int j = 0; j <= 9; j++)
        {
　　　　　　// ポイント
            next_index[i][j] = next_index[i + 1][j];
        }
        next_index[i][s[i] - '0'] = i;
    }

以下のコードではありうる3桁の数字の組み合わせ、000~999までの10^3個について、与えられた文字列で作ることができるか調べています。現在位置のindexから3つの数字を通って最終的に到達したindexの位置が文字列の最大indexを超えなければ良いです。0224の場合はindex3を超えたところにいなければOKです。

    for (int i = 0; i <= 9; i++)
    {
        for (int j = 0; j <= 9; j++)
        {
            for (int k = 0; k <= 9; k++)
            {
                int curIndex = next_index[0][i];
                curIndex++;
                curIndex = next_index[min(curIndex, n)][j];
                curIndex++;
                curIndex = next_index[min(curIndex, n)][k];

                if (curIndex < n)
                {
                    result++;
                }
            }
        }
    }

 

問題を解く上でのポイント（計算量）

この問題は与えられた文字列について全探索するのではなく、答えから考えて、あり得る3桁の数字を全探索するのがポイントです。与えられた文字列から3桁を指定するのはO(N^3)かかります。Nの最大が30000なので、10^9を超えて制限時間内に間に合いません。（10^8~10^9あたりが限界）
しかし、あり得る3桁の数字の組み合わせは10^3個なので十分時間に間に合います。

 

Atcoder初心者が高難度問題に取り組む際の悩みと解決策

Atcoderをやり始めて15日経過していますが、以下のような悩みが生じています。

  • 上位レートコーダーのコードが理解できない
  • なんのアルゴリズムを使っているのか分からない
  • コードを理解するのに時間がかかる

 

これらの悩みを解決するために、以下のようなアプローチをとっています。

  • 実行時間最上位レベルのコードはdefineが多く理解しずらいので、中間上位層を参考にする
  • アルゴリズムの学習を深める
  • chatgptに投げてみる

特に初めは上位レートコーダーのコードばかり見て、時間を消費していたので中間上位層を参考にしています。
C問題までは全探索で解ける場合がほとんどなようなので、今は全力で全探索の精度を上げています。
これらのアプローチを用いて、効率的に学習を進めていきたいと思います！

 

アルゴリズムの使い所を理解するために

アルゴリズムの使い所を理解するためには、以下のようなアプローチが有効だと考えいます。

  • 似たような問題を解いてみる
  • アルゴリズムの特徴を理解する
  • 問題を単純化して考える

似たような問題を解いてみることで、アルゴリズムの使い所を理解することができます。僕の場合は最も基本の全探索から学習を進めています。
また、アルゴリズムの特徴を理解することで、そのアルゴリズムがどのような問題に有効であるかを理解することができます。例えば全探索の問題の場合はデータ量がそこまで膨大ではない、特定の状態からの遷移を考えると次の状態が違い過ぎて分岐がたくさん発生する+すべての場合を予測するのが難しい場合に全探索が有効だと考えています。
さらに、問題を単純化することでデータ構造に着目すると解法が思いつく場合があります。

 

コードを理解するための時間の使い方

コードを理解するための時間の使い方については、以下のようなアプローチをとっています。

  • 全く手がつかなかったら15分経過で答えをみる
  • デバッグやテストケース挿入はvscode上で行う
  • めんどくさい #include <iostream>等はshellコマンドで自動化

全く手がつかない問題の場合、アルゴリズムに対する知識が不足していると思います。めちゃめちゃ天才じゃない限り自分でアルゴリズムを発見するのは不可能なので、15分を目安に答えを見ています。それからデバッグやテストケースの挿入はサイト上ではなく、vscode上で行っています。こちらの方がコードをコピペする手間が省けるので楽です。同じくどの問題にも共通して記載するコード#include <iostream> int main(){}などはコマンドでファイルを作成する際に自動で記載されるようにしています。

 

まとめ

Atcoderをやり始めてから15日経過していますが、全探索の問題についてはかなり解けるようになっている気がします！積極的にコンテストに参加して自分の実力を計測していきたいです！

よく「実務ではアルゴリズムは使わない」と言われていますが、僕は基本的なアルゴリズムは理解しておいた方が良いのかなと感じています。
アルゴリズムが分かったほうが、どのくらいのアクセスが来て、大体どのくらいの時間がかかるのかコーディングの段階でわかると思うからです。
また転職活動の際に基本的な文字列操作程度のテストが課される場合が多かったことも要因です。実務では標準入力から値を受け取った経験がなく、また文字列を細かく操作する機会もなかったため時間に間に合わないことがありました。

頭の上にはてなが浮かんでいる男性
プログラミング学習方法を発信してます！