競プロ参加日記003 東京海上日動　プログラミングコンテスト2020 参加

https://atcoder.jp/contests/tokiomarine2020

●まとめ
A,B,Cの3完で1016位でした。
水色コーダーにとってはC早解きコンテストでしたね

●A問題　Nickname
任意の場所なので、先頭3つを出力すれば良さそうです。
|A|>=|あだ名| なので、制約とか難しいことを考える必要もありません。

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
/*
#include<boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Bint = mp::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)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007
signed main(){
   string s;
   cin>>s;
   cout<<s[0]<<s[1]<<s[2]<<endl;
}

●B問題　Tag
鬼は逃げる子供に近づく、逃げる子供は鬼から遠ざかるのが最善手です。
ひたすら一方向に移動したとして、T秒後に位置関係が逆転するかどうかで判定しました。
T<=10^9、V,W<=10^9なので、最大10^18になるのでintだとオーバーフローします。
私は多倍長を使っていますが、long longで大丈夫です。

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>

#include<boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Bint = mp::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)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007
signed main(){
   Bint A,V,B,W,T;
   cin>>A>>V;
   cin>>B>>W;
   cin>>T;
   if(A==B){
       cout<<"YES"<<endl;
   }
   else if(A<B){
       A+=T*V;
       B+=T*W;
       if(A>=B){
          cout<<"YES"<<endl;
       }
       else{
           cout<<"NO"<<endl;
       }
   }
   else{
       A-=T*V;
       B-=T*W;
       if(A<=B){
          cout<<"YES"<<endl;
       }
       else{
           cout<<"NO"<<endl;
       }
   }
}

●C問題　Lamp

1000 10000
0 0 0 0.... 0 1
みたいな入力を観察すれば分かりますが、21手順目くらいで全ての値が1000になります。そこから10000手順目まで値が変化しません。
この問題、実はK手までする必要がなく、早い段階でA[i]のすべての値がNになります。なので、時間制限には思いのほか余裕があります。

それでも、愚直にシミュレーションをするとTLEします。
https://imoz.jp/algorithms/imos_method.html
今回のように、幾つもの区間があって、ある地点iに何個の区間があるかを調べる場合、いもす法を使うとO(N)で求められます。

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
/*
#include<boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Bint = mp::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)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007
#define NMAX 200000
signed main(){   
   int N,K,A[NMAX];
   int a[NMAX];
   cin>>N>>K;
   for(int i=0;i<N;i++){
       cin>>A[i];
   }
   for(int i=0;i<N;i++){
       a[i]=A[i];
   }
   for(int i=0;i<K;i++){
       int n[NMAX]={0};
       int sp=0;
       for(int j=0;j<N;j++){
           if(j-a[j]<0) sp++;
           else n[j-a[j]]++;
           if(j+a[j]+1<N) n[j+a[j]+1]--;
       }
       for(int j=0;j<N;j++){
           sp+=n[j];
           n[j]=sp;
       }
       bool mf=true;
       for(int j=0;j<N;j++){
           a[j]=n[j];
           if(a[j]!=N) mf=false;
       }
       if(mf) break;
   }
   for(int j=0;j<N;j++){
       cout<<a[j]<<" ";
   }
   cout<<endl;
}

※N<=2*10^5はトラップ(NMAX=10^5として1WAしました)

●D問題　Knapsack Queries on a tree
ナップサック問題を何回もする問題。
DPを使えばナップサック自体はO(n*min(V,W))で解けるのですが、それをQ回は明らかに時間が足りません。
メモをうまく残しながら、後半のクエリはさぼる問題と思ったのですが、いいメモ化の仕方が思い浮かばず断念しました。

●まとめ
提出前に制約を確認しよう(こんなミスで1WAは非常にもったいない)