ABC377 反省

自己紹介

所属

九州工業大学情報工学部

ハンドルネーム

buridaikon

ABC377　反省

ABC373で茶パフォを出せたからと言って自分に期待してしまっていた。
精進してないくせに茶パフォ出せると思うなよ、自分

• 単純にアルゴリズム分かってない
• 精進不足
• C++の知識が乏しい
• 確認を怠っていた
• 典型的な問題の経験が足りない

A - Rearranging ABC

abc377_a.cpp

// Rearranging ABC

#include <iostream>
#include <vector>

using namespace std;

int main() {
    string s;
    cin >> s;
    bool flag = false;
    if (s.find("A") != string::npos && s.find("B") != string::npos && s.find("C") != string::npos) {
        flag = true;
    }
    if (flag) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

私は制約を見て、文字列のサイズが3かつ並び替えてABCに等しくなれば、Yesを出力、等しくなければNoと出力すればいいということはすぐわかったのだが、なぜか文字列をソートするという考えに至らず、上のような回りくどい解き方で解いてしまった。しかも、Noを出力する分岐を書いていなくて1ペナを食らった（BとCを先に見てしまったことで動揺していたのだと思う）。軽微なミスもあるが、文字列のソートをしたことがなかったためソートするという発想に至らなかったこということが、Aでの大きな敗因であると思う（条件式を書くだけで結構時間をくってしまった）。

B - Avoid Rook Atack

abc377_b.cpp

// Avoid Rook Attack

#include <iostream>
#include <vector>
#define n 8
using namespace std;
void horiz(vector<vector<int>> &expression, int a)
{
   for (int i = 0; i < n; i++)
   {
       expression[a][i] = 1;
   }
}
void verti(vector<vector<int>> &expression, int index)
{
   for (int i = 0; i < n; i++)
   {
       expression[i][index] = 1;
   }
}
int main()
{
   vector<string> vec(n);
   vector<vector<int>> expression(n, vector<int>(n));
   for (int i = 0; i < n; i++)
   {
       cin >> vec[i];
   }

   string sharp = "#";
   string period = ".";

   for (int i = 0; i < n; i++)
   {
        size_t pos = vec[i].find(sharp);
       while (pos != string::npos)  // process all '#' in the row
       {
           horiz(expression, i);
           verti(expression, pos);
           pos = vec[i].find(sharp, pos + 1);  // find next '#' in the row
       }
   }

   int count = 0;

   for (int i = 0; i < n; i++)
   {
       for (int j = 0; j < n; j++)
       {
           if (expression[i][j] != 1)
           {
               count++;
           }
       }
   }

   cout << count << endl;

   return 0;
}

　Bに関してはコード長は長くなったが、よく考えてプログラミングできたので自分としては満足している。一つ悔やまれるとすれば、同じ行に2つ以上#が含まれた時の処理を考えていなかったことで1ペナを食らってしまったことだ。次回までにはCまで（できればDまで）自分で実装して実力をつけておきたい。

C以降の問題はどうすればいいのか分からなかったので諦めました
Cは一応書いたには書いたけどちゃんとした答えが出なくて（答え自体は惜しかったけど±2くらい毎回誤差があった（なぜ？））。入力例2に関してはkilledになった。

abc377_c.cpp

// Avoid Knight Attack

#include <iostream>
#include <vector>
using namespace std;
void renewthebox(vector<vector<long long>> &expression, long long a, long long b)
{

    vector<long long> horiz = {a + 2, a + 1, a - 1, a - 2, a - 2, a - 1, a + 1, a + 2};
    vector<long long> verti = {b + 1, b + 2, b + 2, b + 1, b - 1, b - 2, b - 2, b - 1};

    for (long long i = 0; i < 8; i++) {
        if (horiz[i] >= 0 && horiz[i] < expression.size() &&
            verti[i] >= 0 && verti[i] < expression[0].size()) {
            expression[horiz[i]][verti[i]] = 1;
        }
    }
}
int main()
{
    long long n, m;
    cin >> n >> m;
    vector<string> vec(n);
    vector<vector<long long>> expression(n, vector<long long>(n));
    for (long long i = 0; i < m; i++)
    {
        long long querya, queryb;
        cin >> querya >> queryb;
        renewthebox(expression, querya, queryb);
    }

    long long count = 0;

    for (long long i = 0; i < n; i++)
    {
        for (long long j = 0; j < n; j++)
        {
            if (expression[i][j] != 1)
            {
                count++;
            }
        }
    }

    cout << count << endl;

    return 0;
}

全部の変数の型をlong longにしてみたものの、変数の型を変えればいいという問題でもなく、、、

総括

　計算量をできるだけ減らすアルゴリズムを勉強して、文字列の扱いに関しても勉強する必要があるなと思わされる回でした。精進あるのみですね。次回も頑張ります。