今日の一問を解いた。
以下のコードは PyPy3 (2.4.0), C++14 (GCC 5.4.1) で AC を確認している。
2019/08/20 ABC026-C
{上司の社員番号: [部下の社員番号, ...]}という連想配列を作る- 給料計算関数は設問の規則に従う
- 給料計算関数に高橋君 (社員番号 1) を与える
として解いた。
# PyPy3 (2.4.0)
N = int(input())
B = []
for i in range(N-1):
B.append(int(input()))
relation = ({1: []})
for i in range(N-1):
if B[i] in relation:
relation[B[i]].append(i + 2)
else:
relation[B[i]] = [i + 2]
def salary(relation, num):
if num not in relation:
return 1
e = relation[num]
if len(e) == 1:
return 2 * salary(relation, e[0]) + 1
salaries = [salary(relation, x) for x in e]
return (max(salaries) + min(salaries) + 1)
ans = salary(relation, 1)
print(ans)
2019/08/21 ABC112-C
以前に Python で解いていたが、幸いなことに解法を忘れていたので新鮮な気持ちで取り組めた。賢い方法がわからなかったので、力技で全探索した。解いたあとで前回の Python の回答を見たら全探索だった。
// C++14 (GCC 5.4.1)
#include <iostream>
using namespace std;
int main()
{
long long N;
cin >> N;
long long X[100], Y[100], H[100];
for (long long i = 0; i < N; ++i) {
cin >> X[i] >> Y[i] >> H[i];
}
for (int x = 0; x < 101; ++x) {
for (int y = 0; y < 101; ++y) {
bool found = true;
long long h = -1;
for (long long n = 0; n < N; ++n) {
if (H[n] == 0) {
continue;
}
// 一つ候補を見つけて高さの基準にする
h = H[n] + abs(X[n] - x) + abs(Y[n] - y);
break;
}
// すべての高さが矛盾しないものを見つける
for (long long n = 0; n < N; ++n) {
const long long h_candidate = max(h - abs(X[n] - x) - abs(Y[n] - y), 0ll);
if (H[n] != h_candidate) {
found = false;
break;
}
}
if (found) {
printf("%d %d %lld\n", x, y, h);
return 0;
}
}
}
return 0;
}
2019/08/22 ARC001-B
これも賢い方法を思いつかなかったので、差が 10 度未満になるまで 10 度で調整して、残りはベタ書きした。
// C++14 (GCC 5.4.1)
#include <iostream>
using namespace std;
int main()
{
int A, B;
cin >> A >> B;
const int diff = abs(A - B);
int ans = 0;
int remain = diff;
if (remain >= 10) {
const int count = remain / 10;
remain -= count * 10;
ans += count;
}
if (remain <= 2) {
ans += remain;
}
if (remain == 3 || remain == 7 || remain == 8) {
ans += 3;
}
if (remain == 4 || remain == 6 || remain == 9) {
ans += 2;
}
if (remain == 5) {
ans += 1;
}
printf("%d\n", ans);
return 0;
}