C問題埋めをやっていますが、Medium100は1問ごとの考察がEasyより必要でなかなか進みません。ただ、やっている中でいろいろなことを知れているので頑張っていきます。
しかし、解くスピードとまとめるスピードが明らかに違うので、まとめるための計算用紙が机の横に積まれていて、すでにどんな事を考えながらコードを書いていたか忘れています。また、数式を入れるとページ表示が激重になるので、極力入れないように問題を書いていましたが、流石にめんどくさくなったのでキーワードだけ置くことにしました。
目次
1.ABC154D
キーワード:サイコロ、期待値、最大値、累積和
期待値をまともに計算しているとTLEします。なので高速に期待値を求める必要があります。今回は累積和を用いることでそれを実現できました。
| #include <bits/stdc++.h> | |
| #define rep(i, n) for (int i = 0; i < (n); i++) | |
| #define rep2(i, s, n) for (int i = (s); i < (n); i++) | |
| using namespace std; | |
| using ll = long long; | |
| using P = pair<int, int>; | |
| int main() { | |
| int n, k; | |
| cin >> n >> k; | |
| vector<double> v(n + 1); | |
| v[0] = 0; | |
| rep2(i, 1, n + 1) { | |
| double num; | |
| cin >> num; | |
| v[i] = (1 + num) / 2; | |
| v[i] += v[i - 1]; | |
| } | |
| double ans = 0; | |
| rep2(i, k, n + 1) ans = max(ans, v[i] - v[i - k]); | |
| printf("%.10lf\n", ans); | |
| return 0; | |
| } |
by 累積和を実装している部分は16行目です。ただこれだけで格段に高速になります。すごい。
2.ARC091C
キーワード:カード、操作
全部のマスに操作をすると確実にTLEするので、ちゃんと考える必要があります。入力例を見れば、n=1かm=1の場合は特殊な場合であり、それ以外は一般的に表せることがわかります。あとは、4パターンについて考えてあげればACしました。
| #include <bits/stdc++.h> | |
| #define rep(i, n) for (int i = 0; i < (n); i++) | |
| #define rep2(i, s, n) for (int i = (s); i < (n); i++) | |
| using namespace std; | |
| using ll = long long; | |
| using P = pair<int, int>; | |
| int main() { | |
| ll n, m; | |
| cin >> n >> m; | |
| ll ans = 0; | |
| if (n == 1 || m == 1) { | |
| if (n == 1) ans += m - 2; | |
| if (m == 1) ans += n - 2; | |
| if (n == 1 && m == 1) ans = 1; | |
| } else { | |
| ans += (n - 2) * (m - 2); | |
| } | |
| cout << ans << endl; | |
| return 0; | |
| } |
3.ARC080C
キーワード:整数列、並び替え、倍数、判定問題
自由に並び替えて、隣の要素との積は4の倍数になるかどうかというもの。4の倍数なので、偶数×偶数ならば必ずできます。問題は、奇数の要素です。奇数を4の倍数にするには4の倍数を掛ける必要があります。よって、偶数だが4の倍数でないもの、4の倍数、奇数をそれぞれカウントする必要があることがわかりました。その後、奇数の個数が4の倍数の個数を超えると、必ず4の倍数にできないペアができるので、その部分で判定します。
| #include <bits/stdc++.h> | |
| #define rep(i, n) for (int i = 0; i < (n); i++) | |
| #define rep2(i, s, n) for (int i = (s); i < (n); i++) | |
| using namespace std; | |
| using ll = long long; | |
| using P = pair<int, int>; | |
| int main() { | |
| int n; | |
| cin >> n; | |
| int multi4 = 0, even = 0, odd = 0; | |
| rep(i, n) { | |
| int num; | |
| cin >> num; | |
| if (num % 4 == 0) multi4++; | |
| if (num % 4 != 0 && num % 2 == 0) even++; | |
| if (num % 2 != 0) odd++; | |
| } | |
| if (odd > multi4) { | |
| if (odd - multi4 == 1 && even == 0) { | |
| cout << "Yes" << endl; | |
| } else { | |
| cout << "No" << endl; | |
| } | |
| } else { | |
| cout << "Yes" << endl; | |
| } | |
| return 0; | |
| } |
4.ABC085C
キーワード:判定、1つが複数になる、候補を探索、一つが決まると他が決まる
鶴亀算かなと思ったら全然そうじゃなかった問題です。解けなかったので他の人のコードを参考にしました。
目標金額をY円、1000円札、5000円札、10000円札の枚数をそれぞれx,y,zとします。また、前準備としてYを1000で割っておきます。
まず、1000*xがYを超えるなら、ありえる候補はないので終わりです。
そうでない場合、xを0から目標枚数N枚まで増やしていきます。そうすると、yが定まります。yが4の倍数で表せるならば、4で割り、できないならばループの先頭に戻ります。
最後に、x,yが定まったらzが木枚r、yとzが0以上ならばそれは候補であり、それを出力して終わらせます。
| #include <bits/stdc++.h> | |
| #define rep(i, n) for (int i = 0; i < (n); i++) | |
| #define rep2(i, s, n) for (int i = (s); i < (n); i++) | |
| using namespace std; | |
| using ll = long long; | |
| using P = pair<int, int>; | |
| int main() { | |
| int n, Y; | |
| cin >> n >> Y; | |
| Y /= 1000; | |
| rep(x, n + 1) { | |
| if (10 * x > Y) break; | |
| int y = (Y - 10 * x) - (n - x); | |
| if (y % 4 != 0) continue; | |
| y /= 4; | |
| int z = n - x - y; | |
| if (y >= 0 && z >= 0) { | |
| cout << x << " " << y << " " << z << endl; | |
| return 0; | |
| } | |
| } | |
| cout << "-1 -1 -1" << endl; | |
| return 0; | |
| } |
5.ARC099C
キーワード:数列、操作、最小回数
最初は真面目に計算していましたが、どうやらもっとシンプルな数式で表せたらしいです。
長さNが奇数の場合と偶数の場合で分けて数式を作っていましたが、結局どちらも同じ数式になります。
| #include <bits/stdc++.h> | |
| #define rep(i, n) for (int i = 0; i < (n); i++) | |
| #define rep2(i, s, n) for (int i = (s); i < (n); i++) | |
| using namespace std; | |
| using ll = long long; | |
| using P = pair<int, int>; | |
| int main() { | |
| double n, k; | |
| cin >> n >> k; | |
| cout << ceil((n - 1) / (k - 1)) << endl; | |
| return 0; | |
| } |
6.おわりに
数学問題が苦手です。考察をする知能が足りない。悲しい。