プログラミング初心者の理系大学生がAtcoderに挑戦してみた [ABC268]

　プログラミング初心者がAtcoderで灰色から抜け出すにはどうしたらいいかを考えた。
　→　A問題、B問題、C問題の３つを完璧によう に解けるすること

Atcoderploblemsを用いて日々演習を重ねていくことにした。
というわけで各コンテストのA,B,C問題の進捗と出来具合、ポイントを解説していく。しかしこれはあくまで自分のプログラミング技術向上のためのアウトプットに過ぎないため、レベルの低い解説になるであろうことは悪しからず。使用する言語はC++を選択した。

1.ABC268-A

#include <bits/stdc++.h>
using namespace std;
int main(void)
{
    int A, B, C, D, E;
    cin >> A >> B >> C >> D >> E;

    int count = 1;

    if (A != B) count++;
    if (A != C and B != C) count++;
    if ((A != D and B != D) and C != D) count++;
    if (((A != E and B != E) and C != E) and D != E) count++;


    cout << count << endl;


    return 0;
}

正直模範解答とほぼ同じなのだがコンピューターは二つの比較しかできないところがミソ。私たちはa=b=cを簡単に判断できるがコンピューターに同じことをさせるならa=b かつ b=c すなわち　a=b=cとなることに注意。
また私と同じ初心者からするとif文の{}がないことに違和感を覚えるかもしれないが、処理が一行のみであれば{}を省略して書けることはコード量が少なくて済むのでおすすめ。公式の解答もそうしている。
文字をAからEの順に参照していく。そして今参照している文字は過去に参照した文字と同じか否かを判定しているだけだ。

2.ABC268-B

接頭辞になるかならないかを考える問題である。
文字列における文字の順番の情報があれば回答できそう...

#include <bits/stdc++.h>
using namespace std;
int main(void)
{
    string s, t;
    cin >> s >> t;

    int a = s.size();
    int b = t.size();

    if (a <= b) {
        if (s == t.substr(0, a)) {
            cout << "Yes" << endl;
        }
        else {
            cout << "No" << endl;
        }
    }
    else {
        cout << "No" << endl;
    }


    return 0;
}

文字列S,Tをまずは入力する。ここでSとTの文字数をそれぞれa,bであらわす。文字列Aの大きさを取り出したい場合には**A.size()**とすれば参照可能である。SがTの接頭辞となることはSの大きさがTの大きさ以下であることが必要である。よって

a > b

となる時点で題意を満たすことはない。
次にTの０番目からa-1番目の文字を取り出す。（文字は0番目スタートであることに注意）この取り出した文字列がSと同じであればSはTの接頭辞であるといえるということである。文字を取り出す関数はsubstr関数で()内の左側の数字の番号から右側の数字の個数分文字を取り出すことが出来る。

string S;
S = "asdfghj";

cout << S.substr(2,3) << endl;

実行結果は

dfg

となる。

SがTの接頭辞となるのは

S =|〇〇●〇●〇|
T =|〇〇●〇●〇|dhskhsc...

となるときである。

3.ABC268-C

• C問題について
  C問題になると難易度が一気に跳ね上がる。私はまだC問題を自力でACを出せたことはない。おそらく初心者脱出の壁になるのがC問題になるかと思う。Atcoderの社長もC問題を解けないエンジニアに信頼性はないと言い切るほど。

• C問題の難しさ
  　単純に処理が難しくなることはもちろんなのだが、競プロらしく計算量、実行時間を意識しないとACは取れない。ちなみにAtcoderの制限時間内に行える実行回数は$10^8$から$10^9$くらいだといわれており、制約が$N <= 10^5$だった場合二重ループにすると計算量がO($N^2$)になりTLE(制限時間オーバー)になってしまう。また計算量の表し方の一つとしてオーダー記法を用いてみた。

人iは料理iが正面もしくは左右隣りに置いてあると喜ぶ。喜ぶのは人だから人に注目して考えてしまうとO($N^2$)となり時間オーバーになってしまうため料理に注目していきたい。

#include <bits/stdc++.h>
using namespace std;
int main(void)
{
    int N;
    cin >> N;

    vector<int> p(N);
    for (int i = 0; i < N; i++) {
        cin >> p[i];
    }

    vector<int> c(N);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 3; j++) {
            c[(p[i] - i - 1 + N + j) % N]++;
        }
    }

    int ans = 0;

    for (int i = 0; i < N; i++) {
        ans = max(ans, c[i]);
    }

    cout << ans << endl;

    return 0;
}

おそらくこの問題の一番難しいところは料理p[i]が人iのところにいるときどのくらい動かせば人p[i]が喜ぶのかを余りを表すmodを用いて計算するかにある。人p[i]が喜ぶ位置は人p[i]+1、人p[i]、人p[i]-1の前に料理iがいるときである。これを計算するにはまず人i+1のところに料理iを移動させそこから一つずつずらす操作を二度行えばよいことになる。料理p[i]が人iのところにいるとすると人p[i]-1の前に移動させるための回転回数はp[i]-i-1回となる。
しかしここで注意したいのがC++では余りが負の数になった時エラーが起こることがあるため、最後にNを足してやる必要がある。

1...  -5 = 3  (-1) -2   

2... -5 = 3  (-2) + 1 

⓵はあまりが$-2$と負の数になってしまったが、⓶で分かるように５で割ったあまり$-2$は$-2+5=3$と正の数3と同じである。
ここに1と2を加えるため変数jも用いて二重ループを構成する。ただし$0<=j<=2$であるためO($N^2$)にならないことに注意。それを格納した配列の最大値をmax関数で出力して終了

ちなみに配列c内の(p[i]-i-1 +N +j) % N どれだけ回転させたかを表している。