AtCoder Beginner Contest 275

AtCoder Beginner Contest 275 - AtCoder

結果

A - Find Takahashi:AC(4:03)
B - ABC-DEF:提出無し
C - Counting Squares:WA

A - Find Takahashi

$${N}$$本の橋があり、$${i}$$番目の橋の高さは$${H_{i}}$$であり全ての橋の高さは相異なる
この中で最も高い橋は何番目かを求める問題

自分の回答

int main(){
  int N, H = 0, B;
  cin >> N;

  for(int i = 0; i < N; i++){
    int h;
    cin >> h;
    if(H < h){
      H = h;
      B = i + 1;
    }
  }
  printf("%d\n", B);
}

シンプルに1つづつ確認していき、これまでの最大より大きければそれが何番目の橋かを入れていく

公式解説

同じため省略

B - ABC-DEF

非負整数$${A,B,C,D,E,F}$$が与えられ、$${(A×B×C)-(D×E×F)}$$を998244353で割った余りを求める問題

自分の回答

オーバーフローの回避方法が思いつかなかった
最初に各値を998244353で割った余りにしても最悪$${998244352^3}$$になるからもう1つか他の方法で工夫しなきゃいけないんだろうけど…

公式解説

const int mod=998244353;

int main() {
  long long a,b,c,d,e,f;
  long long x,y,ans;

  cin >> a >> b >> c >> d >> e >> f;

  x=((a%mod)*(b%mod))%mod;
  x=(x*(c%mod))%mod;
  y=((d%mod)*(e%mod))%mod;
  y=(y*(f%mod))%mod;

  ans=(x+mod-y)%mod;

  cout << ans <<endl;
  return 0;
}

https://atcoder.jp/contests/abc275/editorial/5129より

2乗までならオーバーフローしないからそこでさらに余りを求めればいいのか

なるほど

C - Counting Squares

二次元平面上の座標$${(r,c)\space\space (r,cは1以上9以下の整数)}$$上に「.」か「#」がある
この平面上で「#」を頂点とした正方形がいくつあるかを求める問題

自分の回答

int main(){
  vector<int> X, Y;
  for(int i = 0; i < 9; i++){
    for(int j = 0; j < 9; j++){
      char C;
      cin >> C;
      if(C == '#'){
        X.push_back(j);
        Y.push_back(i);
      }
    }
  }
 
  if(X.size() == 0){
    printf("0\n");
    return 0;
  }
    
  int count = 0;
  for(int i = 0; i < X.size() - 3; i++){
    for(int j = i + 1; j < X.size() - 2; j++){
      for(int k = j + 1; k < X.size() - 1; k++){
        for(int l = k + 1; l < X.size(); l++){
          int x1=X[i], x2=X[j], x3=X[k], x4=X[l], y1=Y[i], y2=Y[j], y3=Y[k], y4=Y[l];
          int s1 = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
          int s2 = (x1 - x3) * (x1 - x3) + (y1 - y3) * (y1 - y3);
          int s3 = (x3 - x4) * (x3 - x4) + (y3 - y4) * (y3 - y4);
          int s4 = (x2 - x4) * (x2 - x4) + (y2 - y4) * (y2 - y4);

          if(s1 == s2 && s2 == s3 && s3 == s4){
            int d1 = (x1 - x4) * (x1 - x4) + (y1 - y4) * (y1 - y4);
            int d2 = (x2 - x3) * (x2 - x3) + (y2 - y3) * (y2 - y3);

            if(d1 == d2){
             count++;
            }
          }
        }
      }
    }
  }
  printf("%d\n", count);
}

コンテスト終了後にAC出せたもの
#を4つ選んでそれでできる四角形の辺の長さが全て等しく、対角線の長さも等しければ正方形であるため、それでチェックするのを総当たり

そもそも#が無いときにforが無限ループに入っちゃうのにあと10秒早く気づければ時間内に解けた…
あとそこ絡みでX.size()==0としてるけどこれそもそも四角形ができないなら0なんだからX.size()<4の方が確実だね
テストケースで四角形ができないパターンは#が無いのだけだったから通ったけど2つでもTLEする
(3つだとちゃんと動くから根本的な原因がわからん…)

公式解説

int main() {
    vector<string> s(9);
    for(auto &v : s) cin >> v;
    auto valid = [&](int x, int y) {
        return clamp(x, 0, 8) == x and clamp(y, 0, 8) == y and s[x][y] == '#';
    };
    set<set<pair<int, int>>> st;
    for(int i = 0; i < 9; i++) {
        for(int j = 0; j < 9; j++) {
            for(int dx = -8; dx < 9; dx++) {
                for(int dy = -8; dy < 9; dy++) {
                    if(!dx and !dy) continue;
                    int i2 = i + dx, j2 = j + dy;
                    int i3 = i2 - dy, j3 = j2 + dx;
                    int i4 = i3 - dx, j4 = j3 - dy;
                    if(valid(i, j) and valid(i2, j2) and valid(i3, j3) and valid(i4, j4)) {
                        set<pair<int, int>> sq;
                        sq.insert({i, j});
                        sq.insert({i2, j2});
                        sq.insert({i3, j3});
                        sq.insert({i4, j4});
                        st.insert(sq);
                    }
                }
            }
        }
    }
    cout << st.size() << endl;
}

https://atcoder.jp/contests/abc275/editorial/5137より

これは1点を決めてそれを起点に正方形を作り、頂点全てに#があるならその座標をsetに入れるのを総当たりしてるのかな

この問題いろいろな解き方ありそうだなぁ