【AtCoder】ABC 342 B - Which is ahead? | 茶コーダーが解くAtCoder

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 57

問題概要

人が一列に並んでおり、前から 番目に並んでいる人は人 である。 個のクエリを処理せよ。 番目のクエリは以下の通り。

整数 が与えられる。人 と 人 のうち、より前に並んでいる人の番号を出力せよ。

制約

• 入力はすべて整数
• 
• 
• 
• 
• 

考察

問題文に素直に沿えば、前からの順番を添字にして人の番号を要素とする配列を作ることになる。しかし、クエリでは人の番号から前からの順番を求める必要があるので、この配列では各クエリに対して がかかってしまう。今回は

具体的には、 のある一文字 について注目したとき、その他の の文字すべてと異なれば、その が求める数である ( は1-indexed) 。

コード

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

#define rep(i, start, end) for (ll i = (start); i < (ll)(end); i++)

// ======================================== //

int main()
{
    string S;
    cin >> S;

    rep(i, 0, S.size())
    {
        bool flag = true;
        rep(j, 0, S.size())
        {
            if (i == j)
                continue;

            if (S[i] == S[j])
                flag = false;
        }

        if (flag)
        {
            cout << i + 1 << endl;
            return 0;
        }
    }
}

atcoder.jp

実装時間: 5分