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

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

ただいまの
回答率

88.82%

ABC009 C問題のWAを解決したい

解決済

回答 2

投稿

  • 評価
  • クリップ 0
  • VIEW 891
退会済みユーザー

退会済みユーザー

前提・実現したいこと

ABC009 C問題のWAを解決したいです。

問題へのリンク

C - 辞書式順序ふたたび

発生している問題

下記ソースコードを提出したところ、半分以上のテストケースが通らない状況です。
7時間ほど格闘しましたがダメなところを自分では見つけることができませんでした。
ご教授お願いします。

該当のソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
using namespace std;

int main(void) {
    int N, K;
    cin >> N >> K;

    string s;
    cin >> s;

    map<char, int> alphabet;
    for (char i = 'a'; i <= 'z'; i++)
    {
        alphabet[i] = 0;
    }

    for (int i = 0; i < N; i++)
    {
        alphabet[s[i]] += 1;
    }

    string ans = "";
    for (int i = 0; i < N; i++)
    {
        for (char i = 'a'; i <= 'z'; i++)
        {
            if (alphabet[i])
            {
                string tmp_ans = ans;
                map<char, int> tmp_alphabet = alphabet;

                int changed_count = 0;

                //ansとalphabetの内容を仮決め
                tmp_ans += i;
                tmp_alphabet[i]--;

                //すでに決まっている部分の変化数をカウント
                for (int j = 0; j < tmp_ans.size(); j++)
                {
                    if (tmp_ans[j] != s[j])
                    {
                        changed_count++;
                    }
                }

                //まだ決まってない部分の最小変化数をカウント
                for (int j = tmp_ans.size(); j < N; j++)
                {
                    if (!tmp_alphabet[s[j]])
                    {
                        changed_count++;
                    }
                }

                //変化量がK以下なら仮決めしていたansとalphabetを確定する
                if (changed_count <= K)
                {
                    ans = tmp_ans;
                    alphabet = tmp_alphabet;
                    break;
                }
            }

            //zまでたどり着いても確定できなかった場合は終了
            if (i == 'z')
            {
                cout << ans << endl;
                return 0;
            }
        }
    }

    cout << ans << endl;
    return 0;
}
  • 気になる質問をクリップする

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • episteme

    2019/05/01 09:10

    ところでコンパイラ/デバッガはあなたのPCにインストールされてるんですよね?

    キャンセル

  • 退会済みユーザー

    退会済みユーザー

    2019/05/01 10:42

    はい、私のPCにインストールされています
    次回からそういった情報も載せておきます!この記事に反応してくださり誠にありがとうございましたm(__)m

    キャンセル

  • episteme

    2019/05/01 10:57

    いや、実行/デバッグ環境が用意されているのは「アタリマエ」なのでわざわざ載せるに及びません。
    7時間もの間"何"と格闘してたんだろ... まさかコードとにらめっこ? デバッガの使い方知らない? とか思ったもので。

    キャンセル

  • 退会済みユーザー

    退会済みユーザー

    2019/05/01 12:01

    わかりました!では次回からも載せません!
    Visual Studio使ってるのでデバッガは使ってます!
    ただブレークオフポイントつけたりステップインしながら変数に入ってる値の変化を確認したりといったことしかしてないので、もっとうまい使い方を勉強しようと思います!
    ”何”と格闘していたかは、"正しく論理を組めない自分の頭"と格闘していたといったところでしょうか!
    反応ありがとうございますm(__)m

    キャンセル

回答 2

+2

失敗するテストケースは見つけましたので、バグ取りがんばってください

4 2
braa

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/05/01 09:09

    ありがとうございます!
    がんばってみます!!

    キャンセル

check解決した方法

0

解決できました!
変化した部分のカウントをカウントアップからカウントダウンに変更して、
まだ決まってない部分の最小変化数をカウントする際にminを使って英字を総なめする方針で行くと全部通りました!

元のコードは、同じ文字が文字列に含まれている場合に、まだ決まってない部分の最小変化数をカウントするループ中でalphabetが持つ値を更新しなければならないことを見落としていたためにできなかった感じです!このやり方はいろんな変数の更新頻度が多くなり煩雑だったのでカウントダウンへ方針転換したところすっきりしました!

皆様ありがとうございました!

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
using namespace std;

int main(void) {
    int N, K;
    cin >> N >> K;

    string s;
    cin >> s;

    map<char, int> alphabet;
    for (char i = 'a'; i <= 'z'; i++)
    {
        alphabet[i] = 0;
    }

    for (int i = 0; i < N; i++)
    {
        alphabet[s[i]] += 1;
    }

    string ans = "";
    for (int i = 0; i < N; i++)
    {
        for (char i = 'a'; i <= 'z'; i++)
        {
            if (alphabet[i])
            {
                string tmp_ans = ans;
                map<char, int> tmp_alphabet = alphabet;

                int changed_count = N;

                //ansとalphabetの内容を仮決め
                tmp_ans += i;
                tmp_alphabet[i]--;

                //すでに決まっている部分の変化数をカウント
                for (int j = 0; j < tmp_ans.size(); j++)
                {
                    if (tmp_ans[j] == s[j])
                    {
                        changed_count--;
                    }
                }

                //まだ決まってない部分の最小変化数をカウント
                for (char k = 'a'; k <= 'z'; k++)
                {
                    changed_count -= min<int>(count(s.begin() + tmp_ans.size(),s.end(),k),tmp_alphabet[k]);
                }

                //変化量がK以下なら仮決めしていたansとalphabetを確定する
                if (changed_count <= K)
                {
                    ans = tmp_ans;
                    alphabet = tmp_alphabet;
                    break;
                }
            }

            //zまでたどり着いても確定できなかった場合は終了
            if (i == 'z')
            {
                cout << ans << endl;
                return 0;
            }
        }
    }

    cout << ans << endl;
    return 0;
}

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

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

  • ただいまの回答率 88.82%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る