SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192) 参戦記

atcoder.jp

はじめに

2021年2月20日21:00-22:40に開催されたSOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192) に参戦しました。

結果は29:25 3完 WAなし 4369位/8699人中でパフォーマンス654、レーティングは前回892から21下がって871になりました。

Contest Result - AtCoder

A問題

100の倍数に切り上げる問題です。
入力に100のMODをとり，100から引いて出力しました。
サンプルも確認し1分23秒で提出。

B問題

文字列が小文字・大文字の順でできているかを判定する問題。
このあたりの処理には余裕がでてきましたが丁寧にサンプルもためして提出します。
4分02秒、通算5分25秒。

C問題

難しかったというか、難しく考えすぎました。
問題自体はシンプルで実装もそんなに重たくないのですが、関数部分を丁寧に試しながら書いていて時間がかかりました。時間がかかったのは、計算量がすっと読めずに不安に感じていたのも一因だと思います。

24分　通算29分25秒で提出。

提出コード

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
int temp;

int gf(int x){
  if(x==0) return 0;
  vector<int>g2;
  while(x){
    temp=x%10;
    g2.push_back(temp);
    x/=10;
  }
  int len=g2.size();
  sort(g2.begin(),g2.end(),greater<int>());
  int ans=0;
  //cout<<len<<endl;
  for(int i=0;i<len;i++){
    ans*=10;
    ans+=g2.at(i);
  }
  return ans;
}

int gs(int x){
  if(x==0) return 0;
  vector<int>g1;
  while(x){
    temp=x%10;
    g1.push_back(temp);
    x/=10;
  }
  int len=g1.size();
  sort(g1.begin(),g1.end());
  int ans=0;
  for(int i=0;i<len;i++){
    ans*=10;
    if(i==0 && g1.at(i)==0) continue;
    ans+=g1.at(i);
  }
  return ans;
}

int f(int x){
  return gf(x)-gs(x);
}

int main() {
  int n,k;
  cin>>n>>k;
  for(int i=0;i<k;i++){
    n=f(n);
  }
  cout<<n<<endl; 
  return 0;
}

D問題

難しかったです。
愚直に実装して２ケースでTLEになり、原因をつかみきれずに詰まりました。
あとでいろいろ試すと桁数の小さいところでTLEしていることがわかりました。
二分探索は頭をよぎりましたが本番中に実装するところまでいかず。
終了後に解説ＡＣしました。

解説で学んだこと。

・　二分探索に使う変数を(l)left,(r)rightとかでなくAC,WA,WJにするのはわかりやすくていいなと思いました。
・　文字列中の文字を順に操作する際の範囲for文　for(char c:x) 　はすっと使えるようになりたいと思いました。
・　未だにif文　else文の書き方がしっかり身についていません。必要以上に{}を多用して行が増えて読みにくいコードになってるのでシンプルに書けるよういちどしっかり押さえておきたいと思いました。
・　オーバーフローの判定は悩ましいですが解説でもだいぶ悩んでおられたので理屈をしっかり押さえるのは難しいところだと理解しました。とりあえず確実な方法をストックしておきたいと思いました。

E問題

ダイクストラで解く方法は思いつきましたが３変数を収納するデータ構造を書けないところで詰まりました。
structの使い方とか独学でやってると入門書などでも丁寧に解説されたものがあまりなくて（特にアルゴリズム本などは、そのあたりは当然に理解していることが前提の説明が多いように思います）しっかり理解できないままに来ています。これもどこかでしっかり押さえておかないと、と思いました。

終わりに

今回は冷えましたが多少冷えても茶に落ちないのは精神的に余裕があります。まずは緑安定をしっかり確保したいと思います。

パフォ654がいつのまにかだいぶ失敗したな、できなかったな、というレベルに感じられるようになったのも進歩です。

Ｄ問題、Ｅ問題いずれも実力のちょっと上にある感じで解けませんでした。
全体に参加者のレベルが高くなっていることを感じますが、５完できれば最低でも水パフォは確保できるのであり、水色が決して手の届かないところにはないことを再確認しました。

道は平たんではなく課題もたくさんありますが、道のりが見えてきた気がします。
更に考えながら精進していきたいと思います。

なお、今回は、DropBoxにおいていたライブラリが壊れて自宅環境からアクセスできないというアクシデントがありました。古いアプリを使ったデータベースだったので、これを機会に、シンプルな形に整理することを考えたいと思います。