競プロ参加日記001 NOMURA プログラミングコンテスト 2020 参加

ぬるからです。

N年ぶりにatcoderのコンテストに参加しました。
一回、競プロから離れようとして消したアカウントでは水色までいっていたので、今回は青色を目指せたらなと思います。

●NOMURA プログラミングコンテスト 2020の全体的な感想
https://atcoder.jp/contests/nomura2020
A,B,Cの3完で1501位でした。
A,B,C問題の早解きコンテストでしたね。
ぬるからは、C問題の解法を思いつくのに時間がかかったので順位はあんまり伸びませんでした。
とはいっても、久しぶりのコンテストで600点通せたので満足です。

●A問題　Study Scheduling
H2時M2分とH1時M1分の時差を求める問題ですね。
時差=(H2-H1)*60+M2-M1とかなのですが、問題文から日跨ぎの有無が読み取れなかったので、計算せずにH1時M1分をH2時M2分と同じになるまで1分ずつ進めて、進めた時刻を時差としました。

#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
#define int long long
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
signed main(){
   int H1,M1,H2,M2,K;
   cin>>H1>>M1>>H2>>M2>>K;
   int to=0;
   while(1){
       if(H1==H2&&M1==M2) break;
       to++;
       M1++;
       if(M1>=60){
           M1=0;
           H1++;
       }
       if(H1>=24) H1=0;
   }
   cout<<max(0ll,to-K)<<endl;
}

(高橋君が徹夜して、5/30 9:00～5/31 15:00まで起きていた可能性もあるので、問題文がちょっと優しくないなぁと思いました。)

●B問題　Postdocs
PD,DD...をたくさん作る問題です。
結論から言うと、？にPを入れる必要はありません。
Pを入れてPDが作れるなら、Dを入れてDDを作っても博士・PD 指数が変わらないからです。(どちらも1)
??  -> PD,DD
?P  -> どのパターンでもだめ
?D -> P,D
D? -> D
P? -> D
？のパターンとそこに何を入れるかを考えると、?Pの絶対に増えないパターンを除けば、とりあえずDを入れれば増えることがわかります。

#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
#define int long long
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
signed main(){
   string T;
   string ans="";
   cin>>T;
   for(int i=0;i<T.size();i++){
       if(T[i]=='P') ans+='P';
       else if(T[i]=='D') ans+='D';
       else ans+='D';
   }
   cout<<ans<<endl;
}

●C問題　Folia
単純にDFSすると当たり前のようにTLEします。
何とかして早く求める必要があります。
※入力例3で書きます。
4
0 0 1 0 2
①まず、A[N]の葉の数を無視して、各深さが取れる最大の頂点数(葉を除く)を求めます。
深さ0 -> 根が1つだけなので1固定です。
深さ1 -> 根から2つ伸びるのが最大なので2です。
深さ2 -> 深さ1から2つ伸びた4つのうち1つは葉にしないといけません。残りの3が最大です。
深さ3 -> (説明省略)最大は6です。
深さ4 -> (説明省略)最大は10です。
この頂点数の最大ですが、言い換えればその頂点は1～最大のどの頂点にもできるといえます。(各頂点から1,2つ伸ばせるので、自由がかなり効きます。)
②深さNの方から、実際に可能な最大の頂点数を求めます。
深さ4 -> 10個まで頂点は作れますが、葉の数は2でなければいけないため、実際の最大数は2になります。
深さ3 -> 6個まで作れますが、次の深さの頂点数を2にできません。次の深さの頂点数を2にするために、実際の最大数は2が限度です。
深さ2 -> 3個まで作れますが、次の深さの頂点数を2にできません。次の深さの頂点数を2にするために、実際の最大数は2が限度です。これに葉の1を加えた3が実際の最大数です。
深さ1 -> (説明省略)実際の最大は2です。
深さ0 -> (説明省略)実際の最大は1です。
これらを足し合わせた10が答えになります。
オーダーもO(2N)なので間に合います。

ただし、オーバーフローには気を付けましょう。
https://note.com/nullkara/n/n7ca680f3fc7b
私は以前にも書いた、多倍長のライブラリを使いました。計算量がやや心配でしたが、600msほどで何とかACです。

#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<boost/multiprecision/cpp_int.hpp>
using namespace std;
using namespace boost::multiprecision;
//cpp_int 多倍長
using namespace std;
#define int long long
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
int A[100001];
cpp_int mxa[100001];
int N;
int sol(){
   //test();
   cin>>N;
   int mn=1;
   cpp_int mx=1;
   for(int i=0;i<N+1;i++){
       cin>>A[i];
       //cout<<",,,,"<<mx<<endl;
       mx-=A[i];
       mxa[i]=mx;
       if(mx<=0&&i!=N||mx<0&&i==N){
           //cout<<"-1"<<endl;
           return -1;
       }
       mx*=2;
   }

   int bef=A[N];
   int ans=A[N];
   for(int i=N-1;i>=0;i--){
       //cout<<ans<<","<<bef<<","<<mxa[i]<<endl;
       if(mxa[i]>bef) mxa[i]=bef;
       ans+=min(bef,(long long)mxa[i])+A[i];
       bef=min(bef,(long long)mxa[i])+A[i];
   }
   return ans;
}
signed main(){
 cout<<sol()<<endl;
}

https://atcoder.jp/contests/nomura2020/submissions/13739011
上記のコードは少し整理していて、コンテストでACしたコードはかなり汚かったりします。
dfsのコードと答えを比較して、間違っている入力例を見つけていたりと、C問題で死にかけてた様子が見えるかと思います。

●最後に
パフォーマンスが1344で水色だったので、実力は落ちていなさそうで安心しました。
C問題は早い段階から、逆から解くという方に考えがいっていたので、それが上手くハマりました。
競プロの問題って、分けるとか逆から見るとか好きですよね。