AtCoder Beginner Contest 285 に参加しました＆反省会

AtCoder Beginner Contest 285 の振り返り

• A問題のみ解けた
• A問題で識別されないトークンですと全角が入っているらしきエラーが出て、その原因を探すのに時間が溶けた。結局別のファイルにコーディングすることで解決した→リネームしたらエラーが解消された！？（一応の対策として全角スペースを検知するvscodeの拡張機能zenkakuを導入した。全角スペースが原因とは確定していないが）
  上とは別に別の箇所で==と=を間違えていた
• B問題：問題文が理解できない
• C問題：アルファベットを数字に置き換える。26進数として扱えそうだが
• 紙に書き出して問題文、考えをまとめる
• A問題のエラーが解消できない・時間が溶ける・B問題が理解できないでパニックになった

A問題

atcoder.jp

考えたこと

• 二次元配列で親ノードと子ノードを管理する
• 入力値aを要素にアクセスする添字（親ノード）とし、入力値bと等しい要素（子ノード）を持つかを判定する

解説*1から、よりシンプルな解法
線で直接結ばれた点の組14組を列挙する解法では、列挙漏れやタイプミスなどによって思わぬバグが混入することがあるため、可能であればよりシンプルな解法を探すべきです。 実は、今回の問題において答えが Yes となることは、a=⌊b/2⌋ であることと同値になります（⌊⋅⌋ は切り捨てを表す）。したがって、次のようなシンプルな if 文で判定することができます。

a,b=map(int,input().split())
if a==b//2:
  print("Yes")
else:
  print("No")

B問題

atcoder.jp

解説*2から 制約が N≤5000 と小さいので、各 i に対して O(N) 回程度の計算量をかけてもよいことが分かります。 なので、以下のように素直にループを回す解法が成立します。

• i=1,2,…,N−1 について、以下を繰り返す。
  • j=1,2,… について、以下を繰り返す。
    • i+j>N のとき、 i に対する答えは j−1 で確定する。
    • Sj = Sj+iのとき、 i に対する答えは j−1 で確定する。
    • 上のどちらでもない場合、 j ループを続行する。

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n;
  string s;
  cin >> n >> s;
  for(int i=1;i<n;i++){
    for(int j=1;j<=n;j++){
      if(i+j>n){cout << j-1 << "\n";break;}
      if(s[j-1]==s[j+i-1]){cout << j-1 << "\n";break;}
    }
  }
  return 0;
}

C問題

atcoder.jp

考えたこと

• ASCⅡでAは65、Zは90で表されるので、英字が数字の1~26と対応するよう64で引く
• 桁が増える際に26をかける

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

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

  long long ans = 0;
  for (int i = 0; i < s.size(); i++) {
    ans *= 26;
    ans += (s[i] - 64);
  }
  
  cout << ans << endl;

  return 0;
}

*1:https://atcoder.jp/contests/abc285/editorial/5511

*2:https://atcoder.jp/contests/abc285/editorial/5528