AtCoder Beginner Contest 299を受けた結果　【Atcoder19日目】

こんにちは！seiです。
AtCoderを始めて19日が経過したので、コンテストにリアルタイムで参加しました！

AtCoderを19日やり続けると、どの程度解けるようになるのでしょうか？
AtCoder初心者が参加する前に知っておくべきこともまとめました！

結果

結果は8問中3問正解でした！19日の学習でC問題まで解くことができました。
D問題は考え方はあっていましたが、コードに起こすのが難しくて結局WAでした。
ここまでで学んだアルゴリズムは以下の4つです。

• 全探索 (答えから考えるやつも）
• bit全探索
• 順列全探索
• DFS

余談：解答の途中でAtCoderにアクセスできなくて焦りましたが、あれがDDos攻撃だったのか…

AtCoder初心者が大会に参加する前に知っておくべきこと

AtCoder初心者がコンテストに参加する前に知っておくべきことをいくつか紹介します。

必ずRatedで参加登録する

AtCoderのコンテストには、「Rated」と「Unrated」の2種類があります。Ratingをあげたい方は必ず「Rated」で参加しましょう！
僕は今回含め二回とも「Unrated」で参加してしまいました(´;ω;｀)
※今回参加したコンテストはDDos攻撃でみんなUnratedになったようです。

参加ボタンを押すだけではダメです！（デフォルトでUnratedになります）
以下画像のようにRatedになるまで確認しておきましょう！

「Rated」は、参加者のパフォーマンスに応じて、レーティングという数値が変動するタイプのコンテストです。「Unrated」は、その逆でレーティングの変動がないタイプのコンテストです。AtCoder初心者は、「Rated」のコンテストに参加することをおすすめします。なぜなら、自分の実力を客観的に知ることができ、レーティングが上がることでより高度なコンテストに参加できるようになるからです。

エディタ等で標準入力値を受け取ってテストできる環境を作成しておく

AtCoder上にも「コードテスト」でコードをテストできる環境がありますが、エディターからいちいちコピペしてテストするのは非効率です。
またこのテストエディターを使っていると標準入力、出力がどのようなものか、理解できません。（自分も理解してませんでした汗）標準入力や標準出力は転職の際の技術テストで聞かれたことがあるので手を動かして理解しておくのをおすすめします。

僕は以下のような.shファイルを作ってコマンドで自動的にファイルが作成されるようにしています。#includeなどの共通部分も自動で入力された状態にしています。

#!/bin/bash

if [ -e $1.cpp ]; then
    echo "すでにファイルが存在しています"
else
    touch $1.cpp &&
        code $1.cpp

    cat <<EOS >$1.cpp
#include<bits/stdc++.h>
using namespace std;

int main(){
    cin >>

    return 0;
}

EOS

fi

exit 0

また今後すべての問題を時間内に解こうと思ったら時間が足りないので、なるべく時短していきたいところです。

AtCoder Beginner Contest の特徴

AtCoder Beginner Contestは、AtCoderが主催する初心者向けのコンテストです。
問題の難易度は初心者向けに設定されており、簡単なものから難しいものまで幅広く用意されています。

AtCoder Beginner Contestは、土曜日の21時から開催される場合が多いです。開催日に合わせてスケジュールを調整しましょう。

A,B,C,D問題の解答

A問題
言われた通りに実装するだけですね。

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
 
    int n, first = 0, middle = 0, end = 0;
    bool flg = false;
 
    string s;
 
    cin >> n >> s;
 
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == '|')
        {
            if (!flg)
            {
                first = i;
                flg = true;
            }
            else
            {
                end = i;
            }
        }
        if (s[i] == '*')
            middle = i;
    }
 
    if (first < middle && middle < end)
        cout << "in" << endl;
    else
        cout << "out" << endl;
 
    return 0;
}

B問題
先頭のヒトの色を考える場合と、あらかじめ用意された色で考える場合、どっちの場合も同時に最大値を計算しています。
出力の時にifで分岐すればよいですね。

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
 
    int n, ans = 0, ans2 = 0;
    long long int t, c[250000], r[250000], max2 = 0, iroAtaiMax = 0;
    cin >> n >> t;
    for (int i = 0; i < n; i++)
        cin >> c[i];
    for (int i = 0; i < n; i++)
        cin >> r[i];
 
    for (int i = 0; i < n; i++)
    {
 
        if (c[i] == t)
        {
            if (r[i] > iroAtaiMax)
            {
                iroAtaiMax = r[i];
                ans = i + 1;
            }
        }
 
        if (c[i] == c[0])
        {
            if (r[i] > max2)
            {
                max2 = r[i];
                ans2 = i + 1;
            }
        }
    }
 
    if (iroAtaiMax)
        cout << ans << endl;
    else
        cout << ans2 << endl;
 
    return 0;
}<br />

C問題
基本的には連続する「o」の文字数を数えればよいです。

文字列の先頭は「-」で始まるか、「o」で始まるかの2パターンです。
「-」で始まる場合は2文字目以降は「-」と「o」が何個含まれててもOKです。残りすべて「o」で終わっても大丈夫です。
「o」で始まる場合は2文字目以降が全て「o」だと団子文字列となりません。「-」が一文字でも含まれていれば団子文字列になります。


よってすべて「o」の場合のみ省けばよいです。

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    // ooooooooはダメ
    int n, ans = -1;
    string s;
    cin >> n >> s;
 
    for (int i = 0; i < n;)
    {
 
        int tmp_max = -1;
 
        while (s[i] == 'o')
        {
            if (tmp_max == -1)
                tmp_max += 2;
            else
                tmp_max++;
            i++;
        }
 
        ans = max(ans, tmp_max);
 
        if (tmp_max == -1)
            i++;
    }
    if (ans == s.size())
        cout << -1 << endl;
    else
        cout << ans << endl;
 
    return 0;
}

D問題
Sは0で始まって1で終わる0と1のみで構成される文字列です。単純index0からに訪ねていくと20回以内で終わりません。
二分探索で調べます。計算量はlog(2*10^5)なので18回くらいで答えが出るはずです。

尋ねて出てきた答え（0または1)によって
始まりのindexと終わりのindexをどんどん更新していきます。（コンテスト参加時はここを聞いたインデックスから右に進む、左に進むで実装していたので複雑になってしまっていました。）
最後にインデックスの差が1になったら答えが出ます。

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
 
    int n, fn, en, mn, reply;
    cin >> n;
 
    fn = 1;
    en = n;
 
    for (int j = 0; j < 20; j++)
    {
        if (en - fn == 1)
        {
            cout << "! " << fn << endl;
            break;
        }
        mn = (fn + en) / 2;
        cout << "? " << mn << endl;
        cin >> reply;
 
        if (reply == 1)
            en = mn;
        else
            fn = mn;
    }
 
    return 0;
}
#include <bits/stdc++.h>
using namespace std;

int main()
{

    int n, fn, en, mn, reply;
    cin >> n;

    fn = 1;
    en = n;

    for (int j = 0; j < 20; j++)
    {
        if (en - fn == 1)
        {
            cout << "! " << fn << endl;
            break;
        }
        mn = (fn + en) / 2;
        cout << "? " << mn << endl;
        cin >> reply;

        if (reply == 1)
            en = mn;
        else
            fn = mn;
    }

    return 0;
}