ARC115参戦記

はじめに

2021年3月21日20:00～22:00に開催されたARC115に参戦しました。
結果は121:43のB１完で1890位／2592人中、パフォーマンス562でレーティングは前回890から-28の862になりました。

前日のABCに続けての茶パフォでだいぶ冷えましたが、多少冷えても茶落ちしないのは心の平穏に寄与しています。
反省の多い回でした。

A問題

A - Two Choices

解けませんでした。
愚直解で当然のTLE。えいやっで出すのはいい加減に辞めようと思います。
答えが違う問題が奇数個ある場合→正解の数の偶奇　まで思い至りませんでした。
Ｏ（N^２）がダメなのでO（Ｎ）解法を捜すしかなく、０１の列なので偶奇は見やすいところです。
実装が簡単な問題だけに悔しいところですが、いい勉強になりました。

B問題

B - Plus Matrix

A問題に相当長時間つぎ込んだ上でのＢ問題。
実装がやや重たいだけの問題ですがコードがぐちゃぐちゃになり時間がかかりました。
それでも解ききれてよかった。途中、０完の悪夢も頭をよぎりました。

私の恥ずかしいコード

https://atcoder.jp/contests/arc115/submissions/21147534?lang=ja

C問題

C - ℕ Coloring

これはよく見れば素因数の数の行列になります。
落ち着いてやれば解けたなと思います。
ちょっと悔しいですがこれが今の実力か。

復習しました

　素因数の数だけでは不十分で約数のAiより大きな数とするようDP的に更新していく必要がありました。
細かな実装の工夫も必要でしたが解けない問題ではなかったと思います。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
typedef pair<int,int>P;

int k[100010];
int main(){
  int n,temp;
  cin>>n;
  vector<int>vec;
  k[1]=1;
  rep(i,n){
    temp=i+1;
    if(temp==1){
      vec.push_back(temp);
      continue;
    }
    for(int j=1;j*j<=temp;j++){
      if(temp%j==0){
        k[temp]=max(k[temp],k[j]+1);
        if(j !=1){
          k[temp]=max(k[temp],k[temp/j]+1);
        }
      }
    }
    vec.push_back(k[temp]);
  }
  for(int i=0;i<vec.size();i++){
    if(i !=0) cout<<" ";
    cout<<vec[i];
  }
  cout<<endl;
  return 0;
}

親子競プロ

父親が１完で冷えている間に息子は前日に続く青パフォで爆上げしています。
この調子でもう１戦すると水色になるレベルでちょっと離されました。
諦めずにもう１度追い抜けたらいいなと思います。