ABC169に挑んだ回
今回も幸運にもD突破。
勉強したソースは残しておくもんだぜ。
B - Multiplication 2
確か 10^15 10^15 になった場合の値がおかしくて死んだ。
以下のケースに当たったら途中抜け、そうじゃなければ続行できる。
①数値リストに0がいたら答えは0
②掛け算する値が指定値超えたら-1
③a b > 指定値 は-1 → 指定値 / a < b は-1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
ll funcAns(ll a) { auto overValue = 1000000000000000000; std::vector<ll> vec; for (ll i = 0; i < a; ++i) { ll n; cin >> n; vec.push_back(n); if (n == 0) return 0; // ① } ll ans = 1; for( auto n : vec){ if (n > overValue) return -1; // ② if ((overValue / ans) < n) return -1; // ③ ans *= n; } return ans; } |
C - Multiplication 3
doubleの丸め誤差に殺された。
偶然double 1.98 →1.9777777…9みたいなことが起きてそのことに気づけた。
小数第2位まで有効とのことだったので、じゃあいっそ文字列で取得して/100したらいいのかとたどり着けて事なきを得た。
0.001の微小値を加算すると回避できたらしい?
https://drken1215.hatenablog.com/entry/2020/05/31/224300
D - Div Game
素因数分解した結果を保存してるmapのソースを残してたのが役立った。
AtCoder 版!マスター・オブ・整数 (素因数分解編)
同じ数字は使えないので、2の累乗だと2=2^1、4=2^2、8=2^3…。
1~nを足し合わせたときの数までが使えるので、8まで使いたいときは2^6が素因数分解に含まれてればOK。
素因数分解して、例えば例にあった24は2^3 * 3^1
。x^3だと2回、x^1だと1回で計3回。
ちなみにx^2だと既出の数値を使ってしまうので1回…みたいな丸め込みが必要になる。
1~nまで足し合わせた数式リストを作って、
1 2 3 4 |
vector<ll> sumCounterList; for (int i = 1; i <= 100; ++i) { sumCounterList.push_back(i * (i + 1) / 2); } |
↑の素因数分解ソース参考にした因数分解mapを取ってきて、
因数分解した数値の乗数の回数を足してくと完成。
1 2 3 4 5 6 7 8 |
for (auto n : answers) { if (n.second == 0) continue; auto find = std::find_if(sumCounterList.rbegin(), sumCounterList.rend(), [n](ll v) { return n.second >= v; }); auto v = sumCounterList.size()-std::distance(sumCounterList.rbegin(), find); //cout << n.first << ":" << n.second << "->" << v << endl; ansCount += v; } |
100で足りなかったらリスト追加で作ろう…と思ってたら意外と通ってしまった。
E - Count Median
入力例1ケースで4種類で3なのに入力例2ケースが答え9991になるって言われて頭パーンなってしまったので撤退した。
でも冷静に見たら問題を読み違えているね。かわいそう。
問題
数値X1はA1~B1の間になる。(A1=2,B1=4ならX1=2,3,4のいずれか)
数値XxはN個定義されている。
すべての組み合わせを検証して、答えの数を計算する。
理解する
解説してくれてる動画があるけど理屈がまだ理解できない…
https://www.youtube.com/watch?v=JDc-T9j7hZo
理解したかも?
重複しない答えの数を数えるだけなので、中央値の最小値と最大値がわかれば、その差分が答えになる。
例えば、例として↓。奇数個の配列を作りたかったので例題とはちょっと違います。
1 2 3 4 |
3 1 2 2 3 3 4 |
中央値の最大値は、XxがすべてBの場合の中央値が該当する。2,3,4→3
中央値の最小値は、XxがすべてAの場合の中央値が該当する。1,2,3→2
この例の場合は中央値が取りうる値が2~3なので、取りうる答え=3-2+1=2個。
偶数個の場合は中央値の取得条件が変わるのでそのへん注意。
というわけで、まずminとmaxのソート済み配列を作る
1 2 3 4 5 6 7 8 9 |
vector<ll> mins, maxs; for (int i = 0; i < n; ++i) { ll a, b; cin >> a >> b; mins.push_back(a); maxs.push_back(b); } sort(mins.begin(), mins.end()); sort(maxs.begin(), maxs.end()); |
偶数・奇数で解答ケースを分ける。
奇数の場合は中央値は実数だけだから素直な計算になる。
例えば2と3で2個。
偶数の場合は0.5を考慮するので答えが2倍の数になる。
例えば例題ケースは3個。
maxCenter(2+3)-minCenter(1+2)+1 = 5-3+1 = 3(実態は1.5・2・2.5の3つ)
1 2 3 4 5 6 7 8 9 10 11 12 |
ll ansCount = 0; if ((n % 2) == 1) { ll index = n / 2; ansCount = maxs[index] - mins[index] + 1; } else { ll index1 = n / 2; ll index2 = index1-1; ll minCenter = mins[index1] + mins[index2]; ll maxCenter = maxs[index1] + maxs[index2]; ansCount = maxCenter - minCenter + 1; } |
所感
なんとか理解したぞぅ…!解説動画に感謝。
一見愚直に計算しそうに見せかけてそうでもない問題って難しそう。
コメントを残す