abc254に挑んだ初心者の感想

夏休みで暇なので競プロの勉強をしています．まだ茶色ですが、ゆくゆくは緑色くらいにはなりたいお兄さんです．ちなみに、Ｅ問題以降は目を通してすらいません．悪しからず．言語はcppです

A - Last Two Digits

int n;

int main(){
  cin >> n;
  printf("%02d", n%100);
}

3桁の数字のうち、後半2桁を出力します．100で割ったあまりが答えですが、2桁表記しなければならないのでprintfを用いて、
　　　　　　　　　　　printf("%02d", n%100)
としました．
毎回書き方忘れますが、今回は覚えていました．
公式解説では10の位と1の位を別で出力していました．これはこれで面白いですね．ちなみに、整数nの下からi桁目の数字は
                        　　　　 (n%10^i)/10^(i-1)
ですね～!使う日が来るかは謎です．

B - Practical Computing

要はパスカルの三角形を書けってやつです．nCkです．

int n;
vector<vector<int>> a(30, vector<int>(30));

int main(){
  cin >> n;

  rep(i, 0, n){
    erep(j, 0, i){
      if(j == 0 || j == i) a.at(i).at(j) = 1;
      else a.at(i).at(j)  = a.at(i-1).at(j-1) + a.at(i-1).at(j);

      cout << a.at(i).at(j) << " ";
    }
    cout << endl;
  }

}

2重ベクトルを作り、2重ループを回して指示通りに数列を完成させました．言われた通り素直にやれば解けると言えばそれまでなのですが、それを無心でできるというのは成長の証ですね．

C - K Swap

言い換えると、k個間隔の数字は任意の順番に置き換えられるということです．例えば、入力例1ではk=2なので、1, 3, 5番目の要素の順番と、2, 4番目の順番は入れ替え放題です．よって、k個間隔ごとの数列をそれぞれ昇順にソートし、最終結果が昇順になっていればよいのでは？と考えました．

int n, k;
vector<int> a(200010);
 
int main(){
  cin >> n >> k;
  rep(i, 0, n) cin >> a.at(i);

　//数列をk個間隔の数列に分ける．
  vector<vector<int>> array(k, vector<int>()); 
  rep(i, 0, n){
    array.at(i%k).push_back(a.at(i));
  }
　//k個の数列をソートする．
  rep(i, 0, k){
    sort(array.at(i).begin(), array.at(i).end());
  }
  //もとの数列aに戻す．
  rep(i, 0, n){
    a.at(i) = array.at(i%k).at(i/k);
  }
  //昇順かどうかチェック
  rep(i, 0, n-1){
    if(a.at(i+1) < a.at(i)){
      cout << "No" << endl;
      return 0;
    }
  }
  
  cout << "Yes" << endl;
}

この問題で必要な思考ポイントは
　　　　　　　　k個間隔でスワップ可能＝k個間隔でソート可能
っていう点です．k=1で考えるとわかりやすいです．隣接する要素がスワップできたら、ソートができるわけです．詳しくはバブルソートでググってください．しかし、実装時は実行時間に間に合わせるためにクイックソートで実装します．O(NlogN)で実行可能です．

D - Together Square

解けませんでした(´;ω;｀)．解説見て自己咀嚼します．