【解説】東京大学きらら同好会プログラミングコンテスト#001

はじめに

こんにちは！東京大学きらら同好会です！
当会初となるプログラミングコンテストはいかがでしたか？

まだ解いてない方はこちらから解くことができます！
※HackerRankにログインする必要があります
www.hackerrank.com

この記事では各問題の解説をしていきます！
問題文はコンテストサイトを参照してください。

相性

ストーリーの都合上第一問にしましたが、ちょっと厄介な問題でしたね。
攻撃力が2倍あるいは半分となる10通りを全通り書いても良いですが、ちょっと大変です。
"Fire"→0, "Wind"→1, ... ,"Sun"→5 と整数に置き換えると以下のようにコンパクトに記述できます。

S = input()
T = input()
A = int(input())
Type = ["Fire", "Wind", "Earth", "Water", "Moon", "Sun"]
for i in range(6):
    if S == Type[i]:
        s = i
    if T == Type[i]:
        t = i
if s < 4:
    if (s+1) % 4 == t:
        A *= 2
    if (s+3) % 4 == t:
        A //= 2
else:
    if s+t == 4+5:
        A *= 2
print(A)

時差

プログラミング言語によって負の数の余りをとったときの仕様は違います。詳しくはWikipediaを見てください。
なので $(A - 9)$ を $24$ で割った余りを出力するプログラムを書いて正解になるプログラミング言語もあれば、不正解になるプログラミング言語もあります。
とりあえず $(A + 24 - 9)$ を $24$ で割った余りを出力するプログラムを書いておけば間違いはないでしょう。

#include <iostream>
int main() {
    int A;
    std::cin >> A;
    std::cout << (A - 9 + 24) % 24 << '\n';
}

原稿

問題を言い換えると「 $D\times K\geqq N$ ですか？」という問題です。
32bit整数型を使ってこの掛け算を行うとオーバーフローするので注意しましょう。
64bit整数型を使う、もしくは割り算をするなどしてオーバーフローを回避しましょう。
Pythonはそういうことを考えなくてよいので楽ですね。遅いけど。

N = int(input())
D = int(input())
K = int(input())
if D*K >= N:
    print("SOLO")
else:
    print("HELP")

刺客

文字列が"yasuna"と一致しているものを数え上げる問題です。この辺からfor文等の繰り返し処理が必要になってきます。
"yasunaa"とかを数えないように注意してください。

use std::io::stdin;

fn main() {
    let n: i32 = {
        let mut s = String::new();
        stdin().read_line(&mut s).unwrap();
        s.trim().parse().unwrap()
    };
    let mut cnt = 0;
    for _i in 0..n {
        let mut s = String::new();
        stdin().read_line(&mut s).unwrap();
        s = s.trim().to_string();
        if s == "yasuna" {
            cnt += 1
        }
    }
    println!("{}", cnt)
}

テント

$A_i \geqq X$ かつ $C_i \geqq Y$ を満たす中での最小の $C_i$ となる $i$ を見つけようという問題です。
for文を回してきっちり場合分けをしましょう。

N, X, Y = map(int, input().split())
A, C = [], []
for i in range(N):
    a, c = map(int, input().split())
    A.append(a)
    C.append(c)
res = (10**15, -1)
for i in range(N):
    if A[i] >= X and C[i] >= Y:
        res = min(res, (C[i], i+1))
print(res[1])

巨大迷路町

この辺から愚直なコードは実行制限時間超過するようになってきます。工夫しましょう。
$t$ 件建物がある番地は $2^t$ 番地から $2^{t + 1} - 1$ 番地です。
建物が $1$ 軒建っている番地、 $2$ 軒建っている番地、... と順番に調べていくと $55$ 軒くらい建っている番地くらいまで足し合わせたところで建物の数が制約の $10^{18}$ を超えます。

#include <iostream>
using std::cin;
using std::cout;

int main(){
    long long N;
    cin >> N;
    for(int i = 1;; i++){
        if (N > i * (1ll << (i - 1))){
            N -= i * (1ll << (i - 1));
        }
        else{
            cout << ((1ll << (i - 1)) + (N - 1) / i) << "\n";
            return 0;
        }
    }
}

カフェ

$\sum_{i=1}^{N}\{A_i\times (i-j)\}$ を最大化したいです。
$\sum_{i=1}^{N}\{A_i\times (i-j)\} = \sum_{i=1}^{N}(A_i\times i) - \sum_{i=1}^{N}(A_i \times j)$ です。
ここで、 $\sum_{i=1}^{N}(A_i\times i)$ は注文を渡す順番に依存しない定数です。
なので、 $\sum_{i=1}^{N}(A_i \times j)$ を最小にすることだけを考えればよいです。
$A_i$ が大きい方から順にするとこれを最小にできます。

N = int(input())
A = list(map(int, input().split()))
P = [(A[i], i) for i in range(N)]
P.sort(reverse = True)
S = 0
for i in range(N):
    S += P[i][0]*(P[i][1]-i)
print(S)

カフェ2

前問とはうれしさの値の条件が異なります。
注文を渡す順を $1,2,3...,i-1,i+1,i+2,...,N-1,N,i$ とすると $i$ 番目のうれしさは負、 $i+1$ 番目から $N$ 番目に注文した人のうれしさは正になります。うれしさの合計を $-B_i+\sum_{j=i+1}^{N}A_j$ にすることができます。
うれしさを負にする人は高々1人で十分です。全員 $A_i\ll B_i$ のとき順番を入れ替えない場合(すなわち答えが $0$ )が最適となることに注意しましょう。

#include <iostream>
#include <algorithm>
using std::cin;
using std::cout;
using std::max;

int N, A[200000], B[200000];
long long S[200001];

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> A[i] >> B[i];
    }
    for (int i = N - 1; i >= 0; i--) {
        S[i] = S[i + 1] + A[i];
    }
    long long res = 0;
    for (int i = 0; i < N; i++) {
        res = max(res, S[i + 1] - B[i]);
    }
    cout << res << "\n";
}

無限ループ

ちょっとややこしい見た目をしていますが、グラフの問題です。
$i$ 行目から $i+1$ 行目にコスト $C_i$ の辺
$i$ 行目から $A_i$ 行目にコスト $0$ の辺
を貼って $1$ 行目から $N+1$ 行目までの最短経路問題を解くとよいです。
よくわからない人はDijkstra法で調べると有益な情報が得られます。

import heapq
N = int(input())
A, C = [], []
for i in range(N):
    a, c = map(int, input().split())
    a -= 1
    A.append(a)
    C.append(c)
pq = []
D = [-1]*(N+1)
heapq.heappush(pq, (0, 0))
while pq:
    x = heapq.heappop(pq)
    if D[x[1]] == -1:
        D[x[1]] = x[0]
        if x[1] == N:
            break
        heapq.heappush(pq, (x[0]+C[x[1]], x[1]+1))
        heapq.heappush(pq, (x[0], A[x[1]]))
print(D[N])

天体観測

例えば、尺取り法と呼ばれる方法を用いると計算量 $O(NlogN)$ で求めることができます。
幅 $K$ の区間をずらしていき、先頭が $S_i$ を通過したら $+1$ 、末尾が $T_i$ を通過したら $-1$ することで今見ている幅で観測できる星の数を知ることができます。

N, K = map(int, input().split())
S, T = [], []
for i in range(N):
    s, t = map(int, input().split())
    S.append(s)
    T.append(t)
m = 0
p = 0
c = 0
S.sort()
T.sort()
for t in T:
    while p != N and S[p]+0.1 <= t-1+K:
        c += 1
        p += 1
    m = max(m, c)
    c -= 1
print(m)

ともだち

制約に $\sum_{i=1}^nB_i\leqq2\times10^5$ とあります。
毎日「相性のいいほうから全員に確認していき、初めて予定のない人を誘う」というアルゴリズムを考えると、誘おうとした人に予定がある回数の合計が $2\times10^5$ 回で上からおさえられるため、十分高速です。
日と人を指定して予定があるかを高速で確認できるようにしておくことで、この問題を解くことができます。

N, M = map(int, input().split())
A = list(map(int, input().split()))
C = []
bs = 0
for i in range(N):
    tmp = list(map(int, input().split()))
    b = tmp[0]
    C.append(set(tmp[1::]))
    bs += b
    ctmp = 0
    for c in tmp[1::]:
        ctmp = c
P = []
for i in range(N):
    P.append((A[i], i))
P.sort()
P.reverse()
for i in range(1, M+1):
    res = -1
    for p in P:
        if not i in C[p[1]]:
            res = p[1]+1
            break
    print(res)

進捗報告

従業員 $i$ ( $0\lt i\leqq N$ ) が仕事を時刻 $X$ に終えたとすると、上司の確認作業が完了する時刻は $X+1$ 以上です。
逆に、すべての部下の $X+1$ の最大値(部下がいない場合、 $0$ )がその従業員の確認作業が完了する時刻です。
これを計算する木DPを行えばよいです。
今回は上司部下の関係が $i$ の順に並んでいるため、 $i$ の大きい方から計算を行うことでこれが実現できます。

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int N;
    cin >> N;
    vector<int> A(N);
    for(auto&& i : A)cin >> i;
    vector<int> H(N + 1);
    for(auto&& i : H)cin >> i;

    vector<long> child_end_time(N + 1);
    for(int i = N + 1; i--;){
        if(i){
            child_end_time[A[i - 1]] = max(child_end_time[A[i - 1]], child_end_time[i] + H[i] + 1);
        }else{
            cout << child_end_time[i] + H[i] << endl;
        }
    }

    return 0;
}

えんそく

ナップサックDPにbitDPが加わったものです。
$dp\lbrack i\rbrack=$ おいしさの合計が $i$ 以上である選び方のうち大きさが最小のものの大きさ
に、「どの種類のお菓子を選んでいるか」をDPのキーに加えて
$dp\lbrack S\rbrack\lbrack i\rbrack=$ おいしさの合計が $i$ 以上であり、選んだお菓子の種類の集合が $S$ である選び方のうち大きさが最小のものの大きさ
としたDPを行えばよいです。
計算量は持っていくべきお菓子の種類を $k$ 種類として、 $O(ND2^k)$ となり、十分高速です。

#include <iostream>
#include <vector>
#include <tuple>

using namespace std;

int main(){
    int N, D;
    cin >> N >> D;

    vector<tuple<int, int, int>> snacks(N);
    for(auto&& [A, B, C] : snacks)cin >> A >> B >> C;

    vector<vector<long>> dp(8, vector<long>(D + 1, 1000000000000L));
    dp[0][0] = 0;
    for(auto [A, B, C] : snacks){
        for(int i = 8; i--;){
            for(int j = D + 1; j--; ){
                dp[i | (8UL >> C)][min(j + A, D)] = min(dp[i | (8UL >> C)][min(j + A, D)], dp[i][j] + B);
            }
        }
    }
    cout << (dp[7][D] >= 1000000000000L ? -1 : dp[7][D]) << endl;

    return 0;
}

また、お菓子を種類ごとにまとめてしまうことで $O(N(D+k))$ 時間で解くこともできます。

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

int main(){
    int N, D;
    cin >> N >> D;

    vector<pair<int, int>> konpeito, potato_chips, chocolate, senbei;
    for(int i = 0, A, B, C; i < N; ++i){
        cin >> A >> B >> C;
        if(C == 1)konpeito.emplace_back(A, B);
        if(C == 2)potato_chips.emplace_back(A, B);
        if(C == 3)chocolate.emplace_back(A, B);
        if(C == 4)senbei.emplace_back(A, B);
    }

    vector<long> dp(D + 1, 1000000000000L);
    dp[0] = 0;
    for(auto [A, B] : senbei){
        for(int i = D + 1; i--;){
            dp[min(D, i + A)] = min(dp[min(D, i + A)], dp[i] + B);
        }
    }
    for(auto& genre : vector<vector<pair<int, int>>>{konpeito, potato_chips, chocolate}){
        vector<long> dp_tmp(D + 1, 1000000000000L);
        for(auto [A, B] : genre){
            for(int i = D + 1; i--;){
                dp_tmp[min(D, i + A)] = min(dp_tmp[min(D, i + A)], min(dp[i], dp_tmp[i]) + B);
            }
        }
        dp = dp_tmp;
    }
    cout << (dp.back() >= 1000000000000L ? -1 : dp[D]) << endl;

    return 0;
}

宿題

全体攻撃、単体攻撃、とっておきとややこしいです。しかも単体攻撃もどのように敵を選んで攻撃すればよいのかややこしいです。
とりあえず時間を決め打つ二分探索をします。 $T$ 秒で倒しきれるか？という判定問題にします。
すると全体攻撃は前処理さえすれば考える必要がなくなります。先に $T/A\times X$ だけ引き算することで、今後全体攻撃を考える必要がなくなります。
次は、単体攻撃について考えていきます。
とっておきとの兼ね合いを考えつつ、効率よく単体攻撃を敵に割り振りたいです。
時間 $T$ が決め打たれているので単体攻撃で与えられるダメージの合計も決まります。そのため、体力が $0$ を下回って過剰に与えるダメージの合計を最小限にすると最も効率がよくなります。
とっておきを $30$ 回以上使った後の単体攻撃は一撃で相手を倒すことができるので、この回数分だけ前もって体力が大きい方から順に処理しておきます。これをしないとオーバーフローや実行時間制限超過をする可能性があります。
とっておきを $29$ 回, $28$ 回, … , $1$ 回, $0$ 回使った後の単体攻撃について考えます。以下のような戦略が最適になります。
とっておきを使った回数が多い方から見ていく。体力がギリギリ $0$ にならないところまでは適当に削る。そして全員をギリギリ $0$ まで削った後にさらに回数が余っている場合、体力が大きい方から倒していく。
とっておきを使うごとに倍々にダメージが増えていきます。逆順に見ていくとダメージが半々に減ってゆきます。半々なので、逆順で見ていったとき、逆順の早め(とっておきの回数が多い方)に敵を倒した方が逆順の遅め(とっておきの回数が少ない方)に敵を倒した方より過剰に与えるダメージが小さくなる、ということはありえません。なのでこの戦略が最適になります。
計算量は何を定数倍とするかややこしいですが $O(N \log N)$ に $\log$ の二乗がかかります。

import copy

def f(t):
    HP = copy.deepcopy(H)
    HP.sort()
    for i in range(len(HP)):
        HP[i] -= t//A*X
        HP[i] = max(HP[i], 0)
    for i in range(t//B-(C*30)//B):
        HP.pop()
        if not HP:
            return True
    for i in range(29, -1, -1):
        k = min(t, C*(i+1))//B-C*i//B
        k = max(k, 0)
        y = (Y << i)
        for j in range(len(HP)):
            if HP[j]//y > k:
                HP[j] -= y*k
                k = 0
            else:
                k -= HP[j]//y
                HP[j] %= y
        HP.sort()
        for j in range(k):
            HP.pop()
            if not HP:
                return True
    HP.sort()
    if HP[-1] == 0:
        return True
    return False

A, B, C = map(int, input().split())
X, Y = map(int, input().split())
N = int(input())
H = list(map(int, input().split()))
L, R = 0, 10**18
while L+1 != R:
    M = (L+R)//2
    if f(M):
        R = M
    else:
        L = M
print(R)

東京大学きらら同好会

東京大学きらら同好会の公式ブログ