AtCoder Beginner Contest 262

https://atcoder.jp/contests/abc262

結果

A - World Cup:AC(6:27)
B - Triangle (Easier):WA
C - Min Max Pair:提出無し

A - World Cup

西暦を4で割った余りが2になる年が、与えられた年から先で一番近いのは何年かを求める問題

自分の回答

int main() {
  int Y;
  cin >> Y;
 
  int N = Y % 4;
  while(true){
    if(N == 2){
      printf("%d\n", Y);
      break;
    }
    if(N == 4){
      N = 0;
    }
    else{
    N++;
    Y++;
    }
  }
}

特に深く考えず余りが2かを判定して2じゃないなら余りと西暦をインクリメント、余りが4なら割り切れるから余りを0に
ただこれもっとシンプルにできたはず。間違いなくA問題で想定されるコードではない

公式解説

int main() {
    
	int Y;
	cin>>Y;
	
	if(Y%4==0)cout<<Y+2<<endl;
	if(Y%4==1)cout<<Y+1<<endl;
	if(Y%4==2)cout<<Y<<endl;
	if(Y%4==3)cout<<Y+3<<endl;
	
	return 0;
}

https://atcoder.jp/contests/abc262/editorial/4502より

そうか余りは4通りしか無いからそれぞれ別で書いちゃえばよかったのか
なるほど

B - Triangle (Easier)

1からN番までの頂点N個とその頂点のi番とj番を結ぶ辺がM個与えられ、辺3つで三角形をなす頂点の組み合わせはいくつあるかを求める問題

自分の回答

三角形をなしているならば辺3つを取り出したときにその頂点を示す番号は3種類が2つづつとなる、と思いついたためその方向で考えるが辺の数は最大4950本、そこから3つを選ぶ総当たりをするとなると時間切れとなるのは目に見えてる
しかしいい方法も思いつかないためその通りに書いてみる

int main() {
  int N, M;
  cin >> N >> M;
  vector<pair<int,int>> ver(M);
  for(int i = 0; i < M; i++){
    cin >> ver[i].first >> ver[i].second;
  }
 
  int count = 0;
  for(int i = 0; i < M - 2; i++){
    map<int,int> check;
    check[ver[i].first] = 1;
    check[ver[i].second] = 1;
 
    for(int j = i + 1; j < M - 1; j++){
      if(check.count(ver[j].first) || check.count(ver[j].second)){
        if(check.count(ver[j].first)){
          check[ver[j].first]++;
          check[ver[j].second] = 1;
        }
        else{
          check[ver[j].first] = 1;
          check[ver[j].second]++;
        }
 
        for(int k = j + 1; k < M; k++){
          if(check.count(ver[k].first) && check.count(ver[k].second)){
            if(check[ver[k].first] == 1 && check[ver[k].second] == 1){
              count++;
              goto OUT;
            }
            else{
              continue;
            }
          }
          else{
            continue;
          }
        }
      }
 
      else{
        continue;;
      }
    }
    OUT:;
  }
  printf("%d\n", count);
}

そしてできたものがこれ
頂点番号をkeyとしたその番号がいくつ出てきたかを確認するmapを作り
1本目の辺(最初のfor)で2つ作成、2本目の辺(2つ目のfor)で2つ目の辺の頂点をkeyとするものが1つある、すなわち1本目と2本目が繋がっているならばkeyがある方をインクリメント、無い方を作成する、そして3本目の辺(3つ目のfor)でその辺の頂点をkeyとするmapが両方存在し、共に1ならば3本の辺は三角形になっているためカウントをする
で、一応サンプルケースは3つとも通ったが結果としてTLE1つ、WA5つ
中身がしっかりある三重forとかTLEはわかり切っていたがサンプル以外のテストケース全てWAなため根本的な部分からダメだったっぽい

公式解説

int main() {
    int n, m;
    cin >> n >> m;
    vector adj(n, vector<bool>(n));
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        u -= 1, v -= 1;
        adj[u][v] = adj[v][u] = true;
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            for (int k = j + 1; k < n; ++k) {
                if (adj[i][j] and adj[j][k] and adj[k][i]) {
                    ans += 1;
                }
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

https://atcoder.jp/contests/abc262/editorial/4478より

$${N×N}$$の２次元配列を作ることで頂点i,jを結ぶ辺が存在するかを表す表が作れて、i,j、j,k、k,iが全てtrueならば三角形となっているのか
そしてi,j,kを総当たりする計算量は$${N^3}$$となるがNは最大100のため時間制限内で終わる
なるほど

C - Min Max Pair

数列が与えられ、i番目とj番目を取り出したとき、その数の小さい方がiと等しく、大きい方がjと等しい組み合わせの数を求める問題

自分の回答

提出無し

Bを考えてる間に覗いた程度なためほとんど考えてないが、愚直に行くと長さNの中から2つ取り出す総当たりになって計算量は$${N^2}$$、そしてNは最大$${5×10^5}$$だから時間制限内で終わるか怪しいなと

公式解説

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    int same = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        a[i] -= 1;
        if (a[i] == i) {
            same += 1;
        }
    }
    long long ans = (long long)same * (same - 1) / 2;
    for (int i = 0; i < n; ++i) {
        if (a[i] > i and a[a[i]] == i) {
            ans += 1;
        }
    }
    cout << ans << '\n';
    return 0;
}

https://atcoder.jp/contests/abc262/editorial/4477より

まず問題文の条件を満たすものは($${a_{i}=i}$$かつ$${a_{j}=j}$$)もしくは($${a_{j}=i}$$かつ$${a_{i}=j}$$)の2通りになる
そして前者は$${a_{k}=k}$$となっている中から2つを選べば条件を満たしているためkの個数をnとすれば$${\frac{n(n-1)}{2}}$$で求められる。コードとしては9~13行目
後者は$${a_{i}=j}$$ならば見る先は$${a_{j}}$$だけでいいため計算量はNで終わる。コードとしてはforの中、さらに言うと条件から$${i < j}$$だからa[i] > iでさらに減らせる
なるほど