AtCoder Beginner Contest 301 感想 A問題 B問題

「今日は昨日参加したAtCoder Beginner Contest の感想を書くぞ！」と思ったのですが、いざ書こうと思うと億劫で書く気が起きません！ｗｗｗ　だいぶ前からやろうと思ったのですが、あんまり趣味ではないかもしれない！　理由は分からないけれど。

単純にやったことを振り返るだけでは面白くないなあと思うので、この記事を書きながらもう一度問題を解いて記事を書いていこうかなと思ってます。別に参加したコードをもう一度見たくないとかではなく、なんとなく能動的に書いていった方が楽しそうだなあと思います。

初めて書くので断っておきます。私の書く言語はC++です。競技プログラミングではC++を使ってます。競技プログラミング以外でC++を使うことがないので本当に競技プログラミングのためだけにC++を使って競技プログラミングを行っているって感じです。

atcoder.jp

A - Overall Winner

atcoder.jp

今、早速解説を見て解こうとしているのですが……「天才！？」になっています。そんな解き方ができたんだ、と思って早速実装しようと思います。いやはや、ABCに参加中は全く思いつかなかったなあ、すごいなあ、どうしたらこんな風な考えが出るんだろ？

この問題は高橋くんの勝ち数と青木くんの勝ち数を数えることから始めます。for文を用いて文字列を最初から最後まで一字ずつ見ることでどちらが勝ったのかを調べることができ、一回勝つごとに一個ずつ増やしていきます。

最後にどちらが多く勝っているかを確かめます。高橋くんの方が多く勝っていれば高橋くんの勝ち、青木くんの方が多く勝っていれば青木くんの勝ちです。勝ち数が同じ場合は先に達した方が勝ちなので先に達した方を調べて勝ちを決めます。

コードでは、二人の勝ち数が同じ場合は最後に勝ってない方を勝ちに選んでいます。理由は勝ち数が同じであれば、最後に勝った方は同じ勝ち数になるために最後の一回を勝たなければいけなく、必ず遅れて勝ち数に届くからです。勝ち数が同じなら最後に勝った方が負けです。

勝ち数が同じ場合は最後に勝った方が負けになることを本番中は気付きませんでした。こんな数学的な考え方もできないなんて……と悲嘆に暮れそうですが、今ここでもう一度解き直すことで分かったので次はこの考え方を用いて解けるときは解きたいですね。こういう数学的なアイデアが思い浮かべばいいんですけどね！

#include <bits/stdc++.h>

using namespace std;


int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  // 入力
  long long N;
  string S;
  cin >> N >> S;
  long long t = 0LL;  // 高橋くんの勝った回数
  long long a = 0LL;  // 青木くんの勝った回数
  for (long long i = 0LL; i < N; ++i) {
      if (S[i] == 'T') {
          t++;
      }
      else {
          a++;
      }
  }
  // 出力
  if (t > a) {
      cout << 'T' << endl;
  }
  else if (t < a) {
      cout << 'A' << endl;
  }
  else {
      if (S[N - 1] == 'T') {
          cout << 'A' << endl;
      }
      else {
          cout << 'T' << endl;
      }
  }
  return 0;
}

atcoder.jp

B - Fill the Gaps

atcoder.jp

B問題は本番中にいい実装が分からなかったので、解説を見て今解きました。すごく参考になります。evimaさん本当にありがとう……。

入力例の１であれば、

4
2 5 1 2

を、

2 3 4
5 4 3 2
1

という感じでfor文を回しながら出力して、最後に

2

を出力します。 2から4、5から2、1から1、そして最後に2だけ出力する感じだといい感じにコードが書けるかなと思いました。

上の例は改行してますが、改行がいるのは最後の出力が終わった場合だけなので気をつけてください。あくまで例で分かりやすくするためです。実際には一列に並べて出力します。

2 3 4 5 4 3 2 1 2

実際の手順として例えば2から4を出力する場合は、まず無条件に2を出力する、それからfor文で3から4を出力するって感じにします。そうすると1から1みたいな場合も問題なく回せます。1をまず出力してfor文を回すけれども実際には回さずに次の項目に行くって感じです（？）。

#include <bits/stdc++.h>

using namespace std;


int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  long long N;
  cin >> N;
  vector<long long> A(N, 0LL);
  for (long long i = 0LL; i < N; ++i) {
      cin >> A[i];
  }
  for (long long i = 0LL; i < N - 1; ++i) {
      cout << A[i] << " ";
      if (A[i] <= A[i + 1]) {
          for (long long j = A[i] + 1; j < A[i + 1]; ++j) {
              cout << j << " ";
          }
      }
      else if (A[i] > A[i + 1]) {
          for (long long j = A[i] - 1; j > A[i + 1]; --j) {
              cout << j << " ";
          }
      }
  }
  cout << A[N - 1] << endl;
  return 0;
}

atcoder.jp

続く

初めてABCの感想を書いたのですけれど、思った以上に時間がかかっちゃって今日は、本当はC問題もD問題も感想を書きたかったけど、終わりにします。ブログ書くのって大変ですねえ。こんなに時間がかかって大変な労力がかかるとは知りませんでした。

追記

次の記事を書いて公開したのですが、改めて見るとあまりにも目に余る酷さでしたので非公開にしました。申し訳ございません。この記事はこれで終わりになります。