ABC 123反省会

C++ Python AtCoder

今回は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;
  }
}