今日は気付いたら22時になっていた。
1日1個は何か技術的な学びを発信するつもりでいるのだが、この時間からは重いタスクをするのが難しそうなので、軽くAtCoderのC問題の過去問に取り組むことにした。
問題の参考としてはこの記事の"1-6-4.全探索に慣れる！"よりピックアップ。
茶色コーダーになるためのガイドラインとして参考にさせていただいている。
今日は時間的に2問解いていこう。
1問目はこちら。
atcoder.jp
N=A×Bを満たす整数N, A, Bに対して、AとBの桁数が小さくなるように探索する問題。
Nの上限値が10^10とあるので、Nを全探索するとTLEになる。（昨日学んだ計算量の知識である）
直感的には、A, BがNの平方根に近い時にF(A, B)は最小になるだろう。A, BのいずれかがルートNより大きい時、もう一方はルートNより小さくなるため、対称性を考える時探索範囲をルートN、すなわち10^5まで絞ることができる。
この範囲の全探索であれば、TLEを回避できそうだ。
適当にコードを書き、サンプルを通してみたところサンプル3にて以下のようなエラーが。
8547 Floating point exception: 8
よくわからないのでChatGPTに聞いてみたところ、「このサンプルの入力として与えられている9876543210がint型の定義可能域を超えている」と言われた。
なるほど、そういえばはるか昔にAtCoder参加した時もそんなことあったような…
intは32bitサイズであり、格納できる整数の絶対値は2^31-1まで。約2×10^9であり、今回のNの定義域はこれを超えているので、Nはint型ではなくlong long型で定義する必要がある。
修正し無事AC。最終的なコードは以下。
#include <iostream>
#include <algorithm>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
using ll = long long;
int digitCount(ll n) {
if (n == 0) return 1;
n = abs(n);
int count = 0;
while (n > 0) {
count++;
n /= 10;
}
return count;
}
int main() {
ll N;
cin >> N;
int rank = 10;
for (ll i = 1; i*i <= N; i++) {
if (N % i == 0) {
ll b = N / i;
if (rank > max(digitCount(i), digitCount(b))) {
rank = max(digitCount(i), digitCount(b));
}
}
}
cout << rank << endl;
return 0;
}提出までの時間は25:42:97。
83分掛けて解けなかった3/30のC問題とはえらい難易度の差だなと思った。
2問目はこちら。
atcoder.jp
組み替え可能なピザを購入して目的の個数を揃える問題。
A+B <= 2C の時、ABピザを買うインセンティブが存在しないので答えはAX+BYとなるだろう。
問題はA+B > 2C の時。この場合はAピザ1枚とBピザ1枚をABピザ2枚に置き換えることで得になる。
そして最後にはABピザ沢山と、AピザもしくはBピザのどちらか単体が残る。こうなった場合現実的には単体ピザを買う方が安いと思うが、一応制約として「ABピザ2枚がA or Bピザ1枚分より安い」という非現実な価格設定もあり得なくはない。即ちA > 2C やB > 2C ということだ。この場合は全てをABピザに置き換えることで金額最小となる。
ここまで考えて後は適当に実装。3つのサンプルが通ったので、後は一応32bitオーバーフローが起きないかどうかだけ確認。
今回はピザの価格が5×10^3 で、ピザの枚数が10^5の範囲。これらの掛け算が合計価格になり、かつABピザは2枚ずつ買うという性質があるので、価格の持つ範囲は2×5×10^8 = 10^9。
これは場合によっては32bitの定義域を超えそうなので、価格だけはlong longで定義しておく。
無事にAC。試しに価格をlong long からintに変更して提出してみたところ、こちらもACしたので、別に関係なかったのかもしれない。
というか、こういう「32bitオーバーフローしそうかどうか微妙」な範囲の変数はとりあえずlong longで定義しておくという雑な方針で行く方が、少なくともAtCoderにおける提出時間を早めるということにおいては正解のような気がしてしまう。いちいち定義域の範囲を計算する時間が勿体無いため。
これには別の制約（メモリ？）が引っかかってくるのだろうか。メモリに関する知識が浅いため、今後調べる必要がありそう。
実際に提出したコードは以下。
#include <iostream>
#include <algorithm>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
using ll = long long;
int main() {
int A, B, C, X, Y;
cin >> A >> B >> C >> X >> Y;
ll sum = 0;
if ((A+B) <= 2 * C) {
sum = A * X + B * Y;
} else {
if (X < Y) {
if (B <= 2 * C) {
sum = 2 * C * X + B * (Y-X);
} else {
sum = 2 * C * Y;
}
} else {
if (A <= 2 * C) {
sum = 2 * C * Y + A * (X-Y);
} else {
sum = 2 * C * X;
}
}
}
cout << sum << endl;
return 0;
}この問題を解いた後に公式解説を見て思ったのだが、これは全探索で解くべき問題なのだろうか？ 自分のコードは完全に条件分岐に従って数学的に解いており、探索を行なっていない。
この辺りはコーダーの性格で済ませていい問題なのか、例えば解の安全性的に探索的に解いた方が良いとかあるのだろうか。今の段階では解ければどっちでもいいか〜としか思えない。
提出までの時間は29:06:34。
3/30ではC問題で突っかかってしまったため「3完って思ったよりムズイか」となっていたが、過去問との難易度差を見るとあれが特別に難化していただけなのかもしれない。
もしくは、年々問題の難易度が上がっているのか。この辺りは回数をこなさないとわからなさそう。
今日の記事は以上。
