ABC172に挑んだ回
ちょっと今回異様に難しくないですか?
B止まりはめちゃくちゃ悔しい。
発想力というか、柔軟さに欠けている。
C - Tsundoku
最初愚直に少ない方を加算してた。
その後問題文見返して、あぁDPか。DP理解できないって逃げた。
そして蓋を開けたらDPじゃない。なにこれ。
解答は解説通り。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
void funcC() { ll N, M, K; cin >> N >> M >> K; // 棚Aの先頭からの合算値と、棚Bの先頭からの合算値をBooksに保存。 // 合算値の時点で合計時間を超えたらBooksには入れない。 vector<ll> aBooks; { ll a = 0; aBooks.push_back(0); for (ll i = 0; i < N; ++i) { ll n; cin >> n; // 読み込み中断すると次のB列に影響するので注意(やらかした) if (a + n < K) { aBooks.push_back(a + n); a += n; } } } vector<ll> bBooks; { ll a = 0; bBooks.push_back(0); for (ll i = 0; i < M; ++i) { ll n; cin >> n; bBooks.push_back(a+n); a += n; if (a > K) break; } } // ここまでで、Booksにはそれぞれ棚Aだけ・棚Bだけを読める最大数が保存されてる。 ll bRead = bBooks.size()-1; // 棚Bを全部読めたと仮定する ll ans = 0; // 下記forループでやってること。 // 最初は棚Aのを1冊だけ読んでみる。 // その時点で棚A+棚Bの読んだ時間が制限時間を超えたら、棚Bの本を1冊ずつ減らす。 // 棚A1冊+棚Bの読めた数:ansで、より多く読めてた方を採用する(max) // forループで次は棚Aを2冊読んだ…で計算を続ける。 // 本は上から順に読むので、棚Bの本は減らしたら戻ることはない。 for (ll i = 1; i < aBooks.size(); ++i) { auto n = K - aBooks[i]; while (bBooks[bRead] > n) { bRead--; } ans = max(ans, bRead + i); } DisplayAnswer(ans); } |
D - Sum of Divisors
約数の情報を保存して計算回数減らしたりするかなー。
でも面倒だし、DPの勉強してこよって逃げた。
仮に約数に着目して続けてたとしても、時間的に間に合わないように作られてたらしい。
ある意味逃げてて正解。
そういう部分も計算量からぱっと理解できるようになりたい。
約数うんぬんから目をそらして、普通に計算式としてどうなりそうかに着目すべき?だった問題らしい。
(解説PDF見てもあんま理解できなくて、他の人の答えを見ながら考えて理解した。
例題ケースの[4]の場合、約数の件の詳細は以下のような感じ。
1:1→1個*1
2:1,2→2個*2
3:1,3→2個*3
4,1,2,4→3個*4
1は1,2,3,4…のすべてで登場するし、2は2,4,6…の2の倍数、3は3,6,9…の3の倍数で登場する。
ので、これらの登場回数を配列でカウントして、最後に配列のインデックスで掛け算すれば答えになる。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
void funcD() { ll N; cin >> N; ll ans = 0; vector<ll> counts(N+1, 0); // 要素を1~N+1で使う for (ll i = 1; i <= N; ++i) { // 1~Nまで、割り切れる数として+=iで計算する // 結果、jはiの倍数なので、登場回数として[j]++する。 for (ll j = i; j <= N; j+=i) { counts[j]++; } } // 登場回数*iを加算する for (ll i = 1; i <= N; ++i) { ans += counts[i] * i; } DisplayAnswer(ans); } |
DP
↓見ながらお勉強中。
蛙は飛ばしたよ。
https://qiita.com/drken/items/dc53c683d6de8aeacf5a
コメントを残す