ABC254感想など

Syntax_Error_

@SyNtAx_error_1がABC254で解いた記憶を残します。
A,B,Cの3完でした。
D,Eは難しかった…つらい…

椅子を温め続けた男

A問題

A問題は後ろ二桁を出力する問題ですね。
公式解説では割り算ですが、個人的には文字列として扱った方が楽だと思うので、そちらを載せます。
制約を見ていなかったので２桁以上なら、どんな数でもできるようになってます。

#include<bits/stdc++.h>
using namespace std;
int main(){
  string S;
  cin >> S;
  cout << S.substr(S.size-2) << endl;
}
print(input()[-2:])

B問題

漸化式が与えられているので、それについてシミュレーションしていけばよさそう。前から順に決めていけばOKです。
ちなみに、この漸化式をよく見ると、nCrを求める式になっていることがわかります。私はnを与えるとnCnまでのn*nの配列を返すライブラリを持っていたので流用しました。
流用コード
配列はN*(N+1)で取って大丈夫です。0だったら終わりにしてあげます。

#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin>>N;
  vector<vector<int>> v(N,vector<int>(N+1));
  for(int i=0;i<N;i++){
    for(int j=0;j<i+1;j++){
      if(j==0||j==i){
        v[i][j]=1;
        continue;
      }
      v[i][j]=v[i-1][j-1]+v[i-1][j];
    }
  }
  for(int i=0;i<N;i++){
    for(int j=0;j<N+1;j++){
      if(v[i][j]==0)break;
      cout<<v[i][j]<<" ";
    }
    cout<<endl;
  }
}
N=int(input())
v=[[0]*(N+1) for _ in range(N)]
for i in range(N):
  for j in range(i+1):
    if j==0 or j==i:
      v[i][j]=1
      continue
    v[i][j]=v[i-1][j-1]+v[i-1][j]
for i in range(N):
  for j in range(i+1):
    print(v[i][j],end=" ")
  print()

ちなみに、Pythonでv=[[0]*(N+1)]*Nと書くと、参照がひたすらコピー(シャローコピー)されるので、バグります。気を付けましょう

C問題

この問題を整理すると、並び替えられるのはmod Kが等しいもの同士のみです。昇順に並び替えるので、そのmod Kが等しいものの中でソートしてあげればいいです。私はヒープ(priority_queue)を使ってごりごりしました。
面倒なので、C++の方は提出コードのmain部分のみをコピペします。過去記事にライブラリを全て載せてあるので、わからない場合はそちらを参考にしてください。

int main() {
  ll N, K;
  cin >> N >> K;
  vll A(N), Ad(N);
  rep(i, N) cin >> A[i];
  Ad = A;
  rep(i, K) {
    rp_queue<ll> buf;
    for (int j = i; j < N; j += K) {
      buf.push(A[j]);
    }
    int j = i;
    while (exist(buf)) {
      A[j] = buf.top();
      buf.pop();
      j += K;
    }
  }
  sort(ALL(Ad));
  yesno(A == Ad);
}
import copy
N,K=map(int,input().split())
A = list(map(int,input().split()))
Ac = copy.copy(A)
Ac.sort()
for i in range(K):
  b = A[i::K]
  b.sort()
  for j,a in enumerate(b):
    A[j*K+i]=a
print("Yes" if A == Ac else "No")

D問題

本番中に解けていません。
制約の関係でN²が通らないのでずっと苦戦していました。
結局解ききれずに終わりました。
やったこととしては、iを全探索→iを素因数分解して〇²以外を掛け合わせて(=tとして)N/tを足し合わせる
コンテスト中は頭がバグっていました。

これが一番わかりやすいです。
とても参考になります。

E問題

本番中に解けていませんⅡ
やったこと→DFS
クエリは1.5×10^5ありますが、見る範囲が狭いので通りそう
結果→サンプルAC、全体WA
結果として、DFSではなくBFSをするべきでした。
BFSをしないと重複する部分で先を見れなくなってしまいます。
(こたつがめさんに終了後にご指摘いただきました。)
もう一つ落とし穴があって、BFS時の配列をvectorで持った場合、その初期化にO(N)かかり、間に合いません。
(unordered_)mapを使って管理するようにします。

まとめ

今回はDで数学力・考察力の足りなさを再実感しました。
一方で、A・B・C問題はなかなか早めに解けました。
D,Eを落としたのは痛いですが、早解きできたのでよしとします。

眠いです。おやすみなさい。

この記事が気に入ったらサポートをしてみませんか？