東京海上プログラミングコンテスト振り返り

東京海上プログラミングコンテストの振り返りをします

結果は11分A,B2完2ペナでレートが下がってしまいました。

頭が働いてなかった(´ω`)
B問題も誤読してなぜか整数秒後のみ条件をみたすと思いペナルティを出してしまい、C問題もO(log K)で各要素が最大値に達することに気づけたのにかけませんでした。

A問題

A - Nickname

前から3文字の文字列を抜き出すことでかけます。

int main(){
 string s; cin >> s;
 string t;
 rep(i,3){
   t.pb(s[i]);
 }
 cout << t << endl;
}

B問題

B - Tag

T秒の間に追いつけば良いので、T秒以内に距離abs(A-B)をつめることができるかを考えれば解けます。

int main(){
 ll A , V , B , W , T; cin >> A >> V >> B >> W >> T;
 if(V  > W){
   ll sa = abs(A - B);
   if((V - W) * T >= sa){
       cout << "YES" << endl;
       return 0;
   }
 }
 cout << "NO" << endl;
}

C問題

C - Lamps

左端の電球が右端に届くまでの操作の回数の最大値を見れば、操作の回数の最大値を把握できるはずです。

厳密ではないですが、大体2回の操作で左端に届く電球が2倍程度になるので、左端からの電球の光が届く範囲も2倍程度になります。

従って、O(log K)の回数で全ての要素がNに達するはずです。

各操作の実装に関してはコンテスト中は二分探索を利用して書き進めていました。

int main(){
 ll N , K; cin >> N >> K;
 vector<ll> a(N); rep(i,N) cin >> a[i];
 vector<ll> s(N); vector<ll> t(N);
 rep(loop , K){
   if(a[0] == N and a[N - 1] == N) break;
   // update s and t
   rep(i,N){
     s[i] = max( (ll)0 , i - a[i]);
     t[i] = min(N , i + a[i] + 1);
   }
   SORT(s); SORT(t);
   ll cnt = 0;
   // update a
   rep(i,N){
     cnt += POSU(s, i) - POSL(s , i);
     cnt -= POSU(t, i) - POSL(t , i);
     a[i] = cnt;
   }
 }
 rep(i,N) cout << a[i] << " ";
 cout << endl;
}

この方法だと計算量はO(N log N log K)で間に合います。

解説を見ていもす法という、累積和を処理するのに簡潔でわかりやすい方法をしりました。

以下の記事を参考にさせてもらいました。

いもす法

int main(){
 ll N , K; cin >> N >> K;
 vector<ll> a(N); rep(i,N) cin >> a[i];

 rep(loop , K){
   vector<ll> b(N + 1);
   rep(i,N) b[max( (ll)0 , i - a[i])]++;
   rep(i,N) b[min(N , i + a[i] + 1)]--;
   rep(i,N) b[i + 1] += b[i];
   if(a == b) break;
   a = b;
 }
 rep(i,N) cout << a[i] << " "; cout << endl;
}

この方法だと計算量はO(N log K)で先ほどより速い回答がかけました。

んーわかりやすいし、実装も簡単^ ^