ABC165 - blogskol

面白い問題の多い回だったから今更だけどコンテスト総評タイプの解説記事を試しに書いて見る
需要が高いらしいからなるべく考察フローを書こうとは思うけど、積極的に求めるものでも無いとは思う
解答から問題の本質とか自分が解けなかった理由考えて自分なりの考察フローを構成していくのが大事だと思うよ

A - We Love Golf

A - We Love Golf
ゴルフ経験が無いんですがKの倍数飛ばしたいなんてことあるのか？
$a \leq k \leq b$ 判定かと思ってWAを出した
適当にループを書けばいい

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void fin(T a){
  cout<<a<<endl;
  exit(0);
}

int main(){
  int k,a,b;cin>>k>>a>>b;
  for(int i=a;i<=b;i++)if(i%k==0)fin("OK");
  fin("NG");
}

Submission #12683922 - AtCoder Beginner Contest 165
fin関数は便利なので積極的に使おうね

B - 1%

制約が $10^{18}$ でビビるけどB問題なので愚直解で当然間に合う
オーバーフローしないように気をつける

#include <bits/stdc++.h>
using namespace std;

int main(){
  long long x,now=100,ans=0;cin>>x;
  while(now<x){
    now+=now/100;
    ans++;
  }
  cout<<ans<<endl;
}

Submission #12684013 - AtCoder Beginner Contest 165

C - Many Requirements

計算量が人によっては意外だったやつ
全探索の計算量を見積もるのは割と大事なのでしっかりとやろうね
俺は $\binom{20}{10}$ くらいだなぁしか考えてないんだけど
こんな複雑な設定のC問題が全探索間に合わないわけないだろ！と思ってそれ以上の見積もりはしなかった

昨日のCの数の見積もり、｢単調増加のことを無視すると10^10だけど単調増加にしようと思うと(全部異なるなら)1/10!くらいになってこれなら3000しかない、等しいのがあるからそこまでは減らないけどかといって100万とかまでは増えへんやろ｣くらいが踏みやすい考察だと思っています
— てんぷら (@tempura_cpp) 2020年5月3日

*1
これが一番楽そうかな？普通にボールと仕切りで考えるのも高校数学の典型なので覚えておいて良さそう雑な見積もりなら数字全部異なるパターンだけで十分だけど

単調増加数列の数え上げは、

・1 <= x < y < z <= N
binom(N,3) それはそう

・1 <= a <= b <= c <= N
x=a, y=b+1, z=c+2 とおくと、1<=x<y<z<=N+2 に対応
binom(N+2,3)

とやる方が好み。
— maspy (@maspy_stars) 2020年5月3日

こう言う考え方もあるのを知り勉強になるなぁと
実装もdfsとかで無駄なくやる必要はそんなになくて、NやMが小さいので多少N倍M倍されるような実装をしても大丈夫
値が[0,M)*2の数列はM進数に対応することを知っていれば、M進数に1足すことを繰り返すのが $N^{M}$ 通り全探索に対応することは分かるので、そこに更に単調非減少を毎回ねじこめばいい

#include <bits/stdc++.h>
using namespace std;

void chmax(int &a,int b){a=max(a,b);}
int n,m,q,v[10],a[50],b[50],c[50],d[50],ans,now;
void check(){
  int res=0;
  for(int i=0;i<q;i++)if(v[b[i]-1]-v[a[i]-1]==c[i])res+=d[i];
  chmax(ans,res);
}

int main(){
  cin>>n>>m>>q;
  for(int i=0;i<q;i++)cin>>a[i]>>b[i]>>c[i]>>d[i];
  while(~now){
    now=n-1;
    while(~now&&++v[now]>=m)v[now--]=0;
    for(int i=1;i<n;i++)chmax(v[i],v[i-1]);
    check();
  }
  cout<<ans<<endl;
}

Submission #12681631 - AtCoder Beginner Contest 165
ちょっと見辛いかもしれないんだけど、
v:数列
now:1足す場所 v[now]がMになったら繰り上がりなのでv[now]を0にしてnowを一つ下げて1足す
~nowはnowが-1、つまりv[0]がMになったらfalseになるので便利

D - Floor Function

これコンテスト中は最悪ケースならTLEするけどこんなケース入って無いやろ！で提出してしまった
割と考察が人と違いそうだったので通常と別視点から書いて見る
まず式が何を聞いているかなんだけど、二つの項は両方とも $\frac{Ax}{B}$ の形をしているので、もしfloorじゃなくてそのまま分数での計算だったら差はxに寄らず常に0なんだよね
つまりこの問題は、
(Ax/B-A*floor(x/B))-(Ax/B-floor(Ax/B))
と言う形に直してやるとより見やすくて
A[x/Bの小数部分]-[Ax/Bの小数部分]
を最大化する問題に言い換えることが出来る
で、xがB大きくなってもこれらの項は両方A増えて明らかに差は変化しないのでxは[0,B)の範囲で考えていいのはちょっと見ると分かる
この辺はmod計算の頻出テクで、小数部分って[剰余/B]なのでmod Bで何か言えることが無いかを確かめるのは大切
で、取り敢えずxを1大きくして見たときに何が起きるかを試しに見てみると、 A[x/Bの小数部分]は必ずA/B増える
これはxが[0,B)の範囲ではx/Bは1未満、すなわち全て小数部分であることから分かる
一方で[Ax/Bの小数部分]は高々A/B増える
分子がAしか増えないので最大でA/Bしか増えないのは明らか
さらにAxがBを超えると小数部分が1減る
結局、xを[0,B)の範囲で増やせば
A[x/Bの小数部分]-[Ax/Bの小数部分]
は増えることはあっても減ることはないのでxを増やせるだけ増やせばいい
すなわち $x=min(N,B-1)$ のときが答え

#include <bits/stdc++.h>
using namespace std;

int main(){
  long long a,b,n;cin>>a>>b>>n;
  long long x=min(b-1,n);
  cout<<a*x/b-a*(x/b)<<endl;
}

Submission #12685017 - AtCoder Beginner Contest 165

E - Rotation Matching

人の数字の増え方が特殊なのでまずはそこを言い換える
そうすると運が良ければ円（正確にはN角形）を回すのに対応していることに気付く
で、そこにアリーナを線で書いてあげるとなんかもう少し見えてくるんだけど、図を描くのがだるいのでこの記事では公式に頼る

youtu.be

1:30:20くらいまで見て欲しい*3んだけど、この図がまんまコンテスト中に紙に書いた図で、アリーナ回転させた方が楽じゃーんになる
もうちょっとしっかり言うと、この問題では人の組み合わせが重複しないことが大切で、重複させたく無いものは基本的に固定させた方がわかりやすいことが多いのでなるべく固定させる
今回の図だと人を固定させることによってアリーナの回転で同じ線が引かれないことが必要十分条件として言い換えられる
で、N回アリーナが回るのを実際に紙の上でやって見ると、重複するのは各対角線の[二つの弧の長さの非順序対]が重複するもしくは対角線の二つの弧の長さが等しい時だと分かるので、それが起こらないようにしたいなぁとなる
対角線の[二つの弧の長さの非順序対]が何通りあるかをまず考えると簡単な計算*4から(N-1)/2通りとなり、これはMの最大値じゃーんとなる
以下弧の長さは短い方を参照する
そのような対角線どうやって引くか考えるために紙に色々描くと、弧の長さが2だけ小さいやつをマトリョーシカ見たいに入れられて無駄ないなぁとなる（解説PDFの図参照）ので、弧の長さ奇数偶数それぞれマトリョーシカを作って見るとちゃんと上手くいきそうなのでOK

#include <bits/stdc++.h>
using namespace std;

int main(){
  int n,m,cnt=1;cin>>n>>m;
  for(int i=m;i>=1;i-=2,cnt++)cout<<cnt<<" "<<cnt+i<<endl;
  cnt=m+2;
  for(int i=m-1;i>=1;i-=2,cnt++)cout<<cnt<<" "<<cnt+i<<endl;
}

Submission #12650877 - AtCoder Beginner Contest 165
弧の長さをiで表しcnt,cnt+iに線を引くように考える
最初のループで一番大きな弧がmの方のマトリョーシカを作る
明らかに1~m+1が使われた可能性のあるゾーンなので次にcntをm+2にして一番大きな弧がm+1の方のマトリョーシカを作る

F-LIS on Tree

疲れた
dp[i]を長さiのLISを作る時に最後の数を最低でいくつに出来るかで持つLISのやり方と、木をdfsで降りる時に更新、登る時に更新キャンセルする典型を知っていればやるだけ
知らなかったら無理なのでこの機会に覚える

#include <bits/stdc++.h>
using namespace std;

int ans[223456],dp[223456],v[223456],n,INF=1e9+1,nowans;
vector<int>edge[223456];

void dfs(int parent,int idx){
  int l=0,r=n+1;
  while(r-l>1){
    int mid=(l+r)>>1;
    (dp[mid]<v[idx]?l:r)=mid;
  }
  int preidx=r,prevalue=dp[r];
  dp[r]=v[idx];
  if(nowans<r)nowans=r;
  ans[idx]=nowans;
  for(int q:edge[idx])if(q!=parent)dfs(idx,q);
  dp[preidx]=prevalue;
  while(dp[nowans]==INF)nowans--;
}

int main(){
  for(int i=1;i<223456;i++)dp[i]=INF;
  cin>>n;
  for(int i=0;i<n;i++)cin>>v[i];
  for(int i=1;i<n;i++){
    int a,b;cin>>a>>b;a--;b--;
    edge[a].push_back(b);
    edge[b].push_back(a);
  }
  dfs(-1,0);
  for(int i=0;i<n;i++)cout<<ans[i]<<endl;
}

Submission #12685807 - AtCoder Beginner Contest 165

終わりに

これすごい疲れるわ
maspyさんとかコンテスト直後に上げられるのやばいね
考察フローどれくらい伝わってるかな
他人のツイートや動画いくつか載せたけど、毎回コンテスト後はいろんな知見を教えてくれる人たちなので積極的にフォローするといいと思うよ
あとはABCでwriter経験ある人はだいたいフォローして良さそう
考察難易度がA<B=F<C<<<<<E<<<<<<Dとかなり逆転の起きてる回だったから人々のお怒りの気持ちはよく分かるよ（分かるので）

*1:値が異なる10個の数を適当に並べるのが $10!$ 通りでそのうち単調増加なのは $1$ 通り