[初投稿]ABC192 - 参戦記録

2021年2月20日、AtCoderのABC192(SOMPO HD プログラミングコンテスト2021)が開催されました。備忘録ついでに記録を投稿します。

まだコンテスト2回目です。初心者です。ヤサシクシテクダサイ。

前回はCもDも解けず2完に終わりましたが、今回はCが捻りの無い簡単な問題だったので余裕でした。3完までは。

結果は
・A 1:00
・B 8:47
・C 14:20
以下クリアできず600点でした。

時間がそれなりだったので緑パフォでした。

はじめに

ABC191Dのような死にたくなる問題はありませんでした。
ただやっぱり問題の読み替えとDPについて耐性がなさすぎるので、死にます。

A - Star

これはマ〇オですね。どう考えてもマリ〇です。
入力n(int)から数直線の正方向を見て次に来る100の倍数との差を答えます。nが100の倍数なら解は100で、0ではありません。
解説では1枚ずつ全探索と剰余を使った計算の両方が載ってました。

#include <bits/stdc++.h>
using namespace std;
int main(){
 int n; cin >> n;
 cout << (100 - (n % 100)) << endl;
}

ここまで書いて入力サンプルの1000にちょっと小突かれた気持ちになりましたが、普通に1100と出力されたので提出、AC。

B - uNrEaDaBlE sTrInG

奇数文字目が小文字、偶数文字目が大文字である文字列を「読みづらい文字列」とする。入力がそれに相当するか答えよ。

…………うわあああああああああああああああ()

実はこの日までAtCoder Boot Camp for Beginnersで散々と文字コード関係の計算をやってました。もう嫌じゃ嫌じゃ。
といってもこいつは26文字分の配列用意とかじゃないのでまだましでした。C++にはisupper() islower()があります。Pythonにもあります。

#include <bits/stdc++.h>
using namespace std;
int main(){
 string s; cin >> s;
 char d[s.size() + 1]; strcpy(d, s.c_str());
 bool ans = true;
 for(int i = 0; i < s.size(); i++){
   int t = (unsigned char)d[i];
   if(i % 2 == 1 && islower(t)){
     ans = false;
     break;
   }else if(i % 2 == 0 && isupper(t)){
     ans = false;
     break;
   }
 }
 cout << (ans ? "Yes" : "No") << endl;
}

なんとも長ったらしいですね。とにかくCへ移ることばかり考えていたのでif文なんか最悪です。時間制限なかったらこんな書き方はしてません……

C - Kaprekar Number

問題文がごちゃごちゃして理解しづらいナリ……そうだ！入力例を見るナリ！

in
314 2

out
693

……わかるかァ！
問題文に戻ります。どうやらカプレカ数という数学理論であるようです。問題を解き終わった後に調べたのですが、なんでも3桁の数字または4桁の数字でこの問題の処理を繰り返すと、最後には特定の数字に行きつくのだとか。で、問題の処理は……

どうやら数字の各桁を昇、降順に並び替えて各差を計算するみたいです。f(x)という余計なモノを挟むから読むのがめんどくさい。そして解は入力nに対してn=f(n)をk回繰り返すと出来るようです。

#include <bits/stdc++.h>
using namespace std;
int main(){
 int n, k; cin >> n >> k;
 for(int i = 0; i < k; i++){
   if(n == 0){break;}
   vector<int> s((int)ceil(log10(n + 1)));
   for(int i = 0; i < s.size(); i++){
     s[i] = (n / (int)pow(10, s.size() - 1 - i)) % 10;
   }
   sort(s.begin(), s.end()); n = 0;
   for(int i = 0; i < s.size(); i++){
     n += s[i] * (int)pow(10, i);
   }
   for(int i = 0; i < s.size(); i++){
     n -= s[s.size() - 1 - i] * (int)pow(10, i);
   }
 }
 cout << n << endl;
}

いけました。でもちょっと重くて遅いです。あんまりいい書き方じゃない気がします。お決まりのceil(log10(n + 1))ですね。10進から各桁を取り出すのもだいぶ慣れてきた気がします。

D - Base n

処理内容がすごいです。
文 字 列 xとmが入力です。xは10進の数字から成ります。xの中に含まれる最大の数字dを求め、d+1以上の数字nについて
xをn進数とみなして得られる数字がmを越えないnの値が何種類あるか答えよ。
入力xの長さは1～60文字、mは1以上10^18以下。

えぇ…………

特に曲者だなと思ったのが「60文字」です。単純に下から60桁目に1を立てて3進数とみなしただけでlong longがオーバーフローします。絶対に単純計算ではないのはわかります。
ちょっと考えて「mを任意進数に変換すれば60桁のほうは進数変換しなくて良い」という結果には至りました。しかしこれだけでは余裕でTLEするので解けません。「100 10^18」などを入れられたらオシマイです。そして肝心なことに気付けませんでした。
b進数のnを10進数表記した値を考えると、それはbが増加するならば必ず増加します。つまりmを昇順キーに対応する値を並べることができたならば、それも昇順に並びます。ということは二分探索できてしまうのです。下はb=d+1で上はクソデカ(10^18)を入れればおｋみたいです。二分探索は基本がO(log n)なので余裕じゃないか。
悔しい。ただただ悔しい。

E - Train

ここから手が付けられていません。DPであることは問題を見ればE, Fともに察知できました。
DPの一種であるダイクストラ法でダイヤによる遅延を移動時間に足せば解けるようです。Educational DP Contest埋めます。すみませんでした。

F - Potion

これもDPです。問題を見たらDPテーブルが3次元だったので一般通過学生には不可能でした。Educational DP Contest埋めます。すみませんでした。

おわれない

コンテスト二回目にして三完達成しました。でもあんまり良いプレイング(？)じゃなかったと思います。C問題ACまで0WA、約15分でそこから2WA 0ACでした。D問題の「問題内容から1手先へ進む」感じとE, F問題のDPが圧倒的にデカい壁です。ABC193までにこれらを絶対克服してやりたい、そんな気持ちになりました。

終われません。