chacoderのブログ

競技プログラミングそのほか

トップ > 京セラプログラミングコンテスト2021（ABC200） 参戦記

京セラプログラミングコンテスト2021（ABC200） 参戦記

f:id:chacoder:20210509095500p:plain

はじめに

2021年5月8日21:00-22:40に開催された京セラプログラミングコンテスト2021（ABC200）に参戦しました。
結果は125分02秒（8ペナ含む）4完で1709位／8577人中、パフォーマンス1217でレーティングは前回909から+35の944になり、highestを更新しました。

f:id:chacoder:20210509095356p:plain

A問題

XX年は何世紀ですか、という問題。
2000年までが20世紀で2001年は21世紀とかちょっとわかりにくく感じることもありました。
100で割って切り上げる、というのは１引いて100で割って1足す操作です。
境目を丁寧に試してAC.
2分6秒。

B問題

B - 200th ABC-200

整数N（<10^5）が与えられ、（操作１）200で割れるときは200で割る、（操作２）割れないときは末尾に文字列として200を加えた数に置き換える、という操作を20回以内する問題です。文字列で3ケタづつ足す操作でどこまで数が大きくなるのか不安に感じましたが、そもそもB問題で文字列で整数を扱わなければならないこともないだろう、とも考えました。末尾に200を加えた数は必ず200で割り切れるので操作２の回数は多くても１０回。操作１により２桁小さくなるので、long long 型に収まりそうです。

素直に操作を実装してAC。
3分8秒、通算5分14秒。

C問題

数列Aの中に差が200で割り切れるペアがいくつあるかを問う問題です。
N<10^5なのでO（N^2）では間に合わないのは明らかです。
しばらく考えて、200で割った剰余が等しいものの数を数えればよいことに思い至りました。

しばらく前に苦労した問題にでてきた技です。
D - Multiple of 2019

mapで管理して剰余が等しいものの数がもとまればあとはコンビネーションを足していきます。

7分19秒　通算12分33秒と自分にしては快調に3完できてほっとしました。

提出コード

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int d[200];

signed main(){
  int n;
  cin>>n;
  int a[n];
  rep(i,n){
    cin>>a[i];
    d[a[i]%200]++;
  }
  int ans=0;
  rep(i,200){
    if(d[i]>1){
      ans+=(d[i]*(d[i]-1)/2);
    }
  }
  cout<<ans<<endl;
  return 0;
}

D問題

D - Happy Birthday! 2


難しかったです。
数列中から異なる組み合わせでつくった部分数列の200で割った剰余が一致するものの有無を判定し、あれば一例を出力する問題です。

なかなか方針が思いつかず、最初はサンプルケースのmod200を出力するプログラムを書いて結果を眺めるなどしました。そうこうしているうち、鳩ノ巣原理を思い出し、最初の８個だけ試せばかならず重複がでてくるはずであることに気づきました。bit全探索で試せそうです。

もっとも解答を出力するあたりの実装に手間取ったり、全探索を２回やって結果が合うところを探さなければならないことに気づくまで時間がかかったり、更に２回とも同じ組み合わせしてしまっていたりして時間を溶かしWAを重ねました。このあたりになるともうペナ出すのは怖くなくなります。

途中では疑心暗鬼になり，やっぱり８個試すだけだとだめなんだろうかと弱気になって16個試してみたり迷走を続けました。最後に気づいたのはbit==0の組み合わせを出力してしまっていたことでした。自分でサンプルケースをつくっていろいろ試す中で発見できました。

提出コードは無駄が多くて恥ずかしすぎるので貼りません。

ACできて　解けた！を味わうことができました。
72分29秒8ペナ　通算85分02秒＋8ペナ

E問題

E - Patisserie ABC 2


Dまで解けてまだ15分程度残していたのでEを考察する時間ができました。
パスカルの三角形みたいなのを考えて何個目の島に入っているかを求め、更にその島の中での位置を求める、みたいなことを考えてみましたが解法まで辿り着けず。後日ゆっくり考えます。

おわりに

highestの更新は、これまでに到達できなかった高みまで登れたということなので、まだまだ自分には可能性があるという希望を与えてくれます。今回のコンテストはたまたま相性がよかったこともありますが，Ｃ問題は苦しんだ過去問の経験を活かせましたし、Ｄ問題は最近の精進ですらすら書けるようになってきたbit全探索に助けられました。

努力せずによい結果を出すのがかっこいいみたいな風潮を感じることもありますが，私は違う価値観を持っています。資質や環境、ハンディキャップなどでなかなか伸びないこともあるけれど、できなければ人の２倍、３倍努力して追いつけばいいし、愚直にこつこつと地道な努力を重ねることこそが貴いことだと思っています。引き続きがんばります。