質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.35%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

1回答

1338閲覧

AtCoder 三井住友信託銀行プログラミングコンテスト2019 D問題

bonjiri____

総合スコア1

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

0クリップ

投稿2021/02/23 22:34

編集2021/02/23 22:43

前提・実現したいこと

AtCoder 三井住友信託銀行プログラミングコンテスト2019 D問題についての質問です。
問題文のURLは以下です。
D - Lucky PIN

0から999まで全探索をすれば解けることがわかりましたが、以下のようなコードを書いてTLEが出てしまいました。isContainPIN()を使えば以下のようなTLEが出力され、解説を見て、試しに以下のisContainPIN2()関数を作成し、これを使えばACとなりました。

考え方は同じように書いたつもりでしたが、どこでこのような違いが発生してしまっているのでしょうか。

お教え頂ければ幸いです。よろしくお願いいたします。

発生している問題・エラーメッセージ

・isContainPIN()を使用したとき
isContainPIN()を使用したとき

・isContainPIN2()を使用したとき
isContainPIN2()を使用したとき

該当のソースコード

c++

1#include <bits/stdc++.h> 2#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i)) 3#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i)) 4using namespace std; 5 6bool isContainPIN(int64_t first,int64_t second, int64_t third , int64_t n, string s){ 7 REP(i, n - 2){ 8 if(s[i] - '0'== first){ 9 REP3(j, i + 1 ,n - 1){ 10 if(s[j] - '0' == second){ 11 REP3(k, j + 1, n){ 12 if(s[k] - '0' == third){ 13 return true; 14 } 15 } 16 } 17 } 18 } 19 } 20 return false; 21} 22 23bool isContainPIN2(int64_t first,int64_t second, int64_t third , int64_t n, string s){ 24 int64_t c[3] = {first, second, third}; 25 int64_t f = 0; 26 REP(i, n){ 27 if(s[i] - '0'== c[f])f++; 28 if(f == 3) return true; 29 } 30 return false; 31} 32 33int64_t solve(int64_t n, string s) { 34 int64_t ans = 0; 35 REP(i, 10){ 36 REP(j, 10){ 37 REP(k, 10){ 38 if(isContainPIN(i, j, k, n, s))ans++; 39 } 40 } 41 } 42 return ans; 43} 44 45int main() { 46 int64_t N; 47 string S; 48 cin >> N >> S; 49 auto ans = solve(N, S); 50 cout << ans << endl; 51 return 0; 52}

試したこと

上記のように、2つのisContainPIN関数を用意し、比較を行いました。明らかに実行速度に差が出ているのがわかり、アルゴリズムが違うのだと推測します。

補足情報(FW/ツールのバージョンなど)

特にありません。
共有する情報が不足している等ございましたら、ご指摘いただけると幸いです。よろしくお願いいたします。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

isContainPINで"111111111...11"から"112"を探す場合を考えてみてください

(s[i] - '0'== first)
(s[j] - '0' == second)
(s[k] - '0' == third)

このうち最初二つは必ずtrueで最後は必ずfalseなのでこう書き換えることができます。

C++

1 REP(i, n - 2){ 2 REP3(j, i + 1 ,n - 1){ 3 REP3(k, j + 1, n){ 4 //pass 5 } 6 } 7 } 8 return false;

isContainPIN2がループ1つなのにしたいして、こちらは3重ループですから相当遅くなります。

投稿2021/02/24 01:51

yudedako67

総合スコア2047

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

bonjiri____

2021/02/24 07:38

ご回答いただきありがとうございます。 理解できました、この書き方だとtrueが一つでもあった場合それ以降の桁も探索してしまうのですね 試しにk == n - 1のときに3重ループを抜けるよう修正するとACとなりました ただこの場合だとそもそも3重ループである必要がありませんね。順に線形探索すればよいだけなので、意識的にisContainPIN2を書けるように頑張っていきます。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.35%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問