今回はAとBはスッと解けたもののCでハマってしまった。
A. Five Antennas
条件よく読んでなくて総当たりしてしまった。
a = [int(input()) for _ in range(5)] k = int(input()) flag = True for i in range(5): for j in range(5): if abs(a[i] - a[j]) > k: flag = False break if flag: print('Yay!') else: print(':(')
C++でやり直し。これでよかったですね。
#include <bits/stdc++.h> using namespace std; int main(){ int a, b, c, d, e, k; cin >> a >> b >> c >> d >> e >> k; cout << (e - a <= k ? "Yay!" : ":(") << endl; }
B. Five Dishes
Python
import math t = [int(input()) for _ in range(5)] min1 = map(lambda x: x % 10, t) min1 = min([10 if i == 0 else i for i in min1]) print(sum(map(lambda x: math.ceil(x) * 10, [i/10 for i in t])) - (10 - min1))
C++
#include <bits/stdc++.h> using namespace std; int main(void){ int min_1 = 10; int sum = 0; int t; for (int i = 0; i < 5; i++) { cin >> t; if (t % 10 != 0 && t % 10 < min_1) min_1 = t % 10; sum += int(ceil(t / 10.0) * 10); } cout << sum - 10 + min_1 << endl; }
C. Five Transportations
ここで時間切れになってしまった。
1つの都市が空になるまでの時間を積み重ねていこうと思ったんだけど、これが良くなかった。最終的に解ける方法ではあったのだけれど、細かい部分にバグが入り込みやすくてWA連発してしまった。テストケースをもう少しうまく組み立てられればなんとかなったかもしれない。
N = int(input()) abcde = [int(input()) for _ in range(5)] time = 0 n = N # 次の都市でまだ残っている人数 last = 0 # 最後の1回で移動する人数 for i in range(5): time += n // abcde[i] if n % abcde[i] > 0: time += 1 last = n % abcde[i] if last == 0: last = abcde[i] if i < 4: n = last + max((N-last) - (time-i-1) * abcde[i+1], 0) print(time)
まあ実際にはこれでよかったんだけど…。
Python
import math N = int(input()) a = [int(input()) for _ in range(5)] print(math.ceil(N / min(a)) + 4)
C++
#include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ ll N; cin >> N; vector<ll> max_n(5); for (int i = 0; i < 5; i++) { cin >> max_n.at(i); } ll min; min = *min_element(max_n.begin(), max_n.end()); cout << setprecision(16) << ceil(N / double(min)) + 4 << endl; }
D. Cake 123
解答見て素直な方法をやってみたらギリTLEになってしまった(提出 #4867478 - AtCoder Beginner Contest 123)。
x, y, z, k = [int(i) for i in input().split()] a = [int(i) for i in input().split()] b = [int(i) for i in input().split()] c = [int(i) for i in input().split()] ab = [ai + bi for ai in a for bi in b] ab.sort(reverse=True) ab = ab[:k] abc = [abi + ci for abi in ab for ci in c] abc.sort(reverse = True) for i in range(len(abc)): if i < k: print(abc[i]) else: break
ところが全く同じコードをPyPy3で提出したところACになった(提出 #4868185 - AtCoder Beginner Contest 123)。ループの少ない例ではあまり時間が短縮されないようだった(むしろ長くなる例もあった)が、ループが多いとかなりの時間短縮が見込めるようだ。ギリギリTLEになるときはとりあえずPyPy3にしてみるというのはアリかもしれない。互換性がどの程度なのかよく調べてないけど…。
ちなみにC++なら相当余裕があった。
#include <bits/stdc++.h> using namespace std; #define REP(i, n) for(int i = 0; i < (int)(n); i++) using lli = long long int; int main(){ int x, y, z, k; cin >> x >> y >> z >> k; vector<lli> a(x); vector<lli> b(y); vector<lli> c(z); REP(i, x) cin >> a.at(i); REP(j, y) cin >> b.at(j); REP(k, z) cin >> c.at(k); vector<lli> ab(x*y); int idx = 0; REP(i, x) { REP(j, y) { ab.at(idx) = a.at(i) + b.at(j); idx++; } } sort(ab.rbegin(), ab.rend()); vector<lli> abc(k*z); idx = 0; REP(i, min(x*y, k)) { REP(j, z) { abc.at(idx) = ab.at(i) + c.at(j); idx++; } } sort(abc.rbegin(), abc.rend()); REP(i, k) { cout << abc.at(i) << endl; } }