AtCoder Grand Contest 009 - D言語で競プロ

参加しました
Ａしか解けませんでした、難しい

A - Multiple Array

問題文

N 項からなる数列 A_1,…,A_N があり、N 個のボタンがあります。
i(1≦i≦N) 個目のボタンを押すと、数列 A の 1 項目から i 項目までの値が 1 ずつ増加します。

数列 B_1,…,B_N が与えられます。高橋君は、これらのボタンを何回か押して、すべての i に対し、A_i が B_i の倍数になるようにします。

高橋君がボタンを押す回数の最小値を求めてください。

制約

入力はすべて整数である。
1≦N≦10^5
0≦A_i≦10^9(1≦i≦N)
1≦B_i≦10^9(1≦i≦N)

感想

Beginner Contestじゃないから当たり前だけど、いきなり難しくて面喰った
とりあえず飛ばしてB問題見に行ったけど、当然さらに難しそうだったので
真面目に考えようとＡに戻ってきた
考えてると、一番後ろを増やすにはN番目のボタンを何回か押すしかなくて
そうすると全体が押した分だけ増えて、今度は一番後ろから二番目のとこ
を押して、また手前側が増えて、って考えると解けそうだと思った
最初一番後ろのボタンを押した後に手前の全ての要素に増分を足そうと
してたけど、それだとO(N^2)になって計算量的にアウトだなあと思って
一個手前だけに今までの全ての増分の総和を足せばいいと気付いた
これでO(N)なので計算量的にもＯＫ
何回押せばいいかは、B_i - A_i % B_i回で求まるって最初やってたら
テスト通らなくて、これだと良く考えたらA_iが最初からB_iの倍数になってる
ときも無駄にB_i回足しちゃってることになるので
(B_i - A_i % B_i) % B_i に直した

実際に書いたコード

import sys
import math

N = int(input())
A = []
B = []

for i in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

'''
print(A)
print(B)
'''

ans = 0

for i in range(N - 1, -1, -1):
    r = A[i] % B[i]
    ans += (B[i] - r) % B[i]

    if i == 0:
        break

    A[i - 1] += ans

print(ans)

B - Tournament

問題要約

N人のトーナメントが行われました、優勝者は1番目の人でした
他のi番目(2 <= i <= N)の人はa_i番目の人に負けました
このデータからあり得る全てのトーナメント構造のうち
最小のトーナメントの深さを求めてください

制約

2≦N≦10^5
1≦a_i≦N(2≦i≦N)
入力の試合結果と合致するようなトーナメントが存在する

感想

まず問題文を読むのに凄く時間がかかった
特にトーナメントの正式な定義のとこが割と意味不明だった
この条件を満たすものはどんな理不尽な構造でもトーナメントって呼びますよ
ってことを言いたかったんだなって思った
結果論だけどここはちゃんと読まなくてもよかったところだった

やっと読めたところでどうやって解こうか、って感じだった
最近ちょうど木構造の勉強をしたとこだったので、木構造を上手く使えば
解けそうかなと思った
自分が考えてたのは二分木を使うって考えで、iがjに負けたなら
jを親にして子にiとjをつけてっていう感じでそれを先頭からやっていって
既に根とか葉にあったらそこにうまくくっつけて、みたいな感じで
トーナメントの構造を復元して、最後にその木の深さを求めれば解ける？
みたいな感じに考えてた
正しいかは分からないけどそれしかアイデアが無かったのでとりあえず
コーディングしてたんだけど、なんかやたら複雑になって案の定バグって
うんたらかんたらしてるうちにコンテストが終わった

解説見ると二分木じゃなくて、普通の木だった
iがjに負けたらjの子にiを増やしてっていう感じで木を作って
その木に対して再帰的に部分木の深さを求めるアルゴリズムを作って
なんかやったらいけるみたいな感じだった
正直よく分からなかった、「ん、ああー、おおー…」って感じで
とりあえずPythonで通してる人がいたのでその人のマネしてコード書いてみた
再帰深さの限界がデフォルトだと1000ぐらいまでらしいので
そこだけ大き目に設定しなおさないとランタイムエラーになってしまう
各節点ごとに子のソートしてるから計算量的にやばそうな気がするけど
実際はO(NlogN)らしい
こういうのどうやって計算量見積もればいいかよくわかんない
実際Pythonでも1sぐらいで通った
どうでもいいけど添え字のズレってどうすればいいんだろう
全部０オリジンにするのか一個多めに取って問題文の１オリジンとかに
合わせるのかみたいな
自分の中でどっちにするか統一しとかないと添え字のバグが発生しまくりそう

import sys

limit = 10 ** 5 * 2
sys.setrecursionlimit(limit)
 
def calc_depth(n):
    if children[n] == set():
        return 0
 
    depth_l = [calc_depth(child) for child in children[n]]
    depth_l.sort(reverse=True)
 
    return max(depth + (i+1) for (i, depth) in enumerate(depth_l))
 
N = int(input())
 
children = [set() for i in range(N + 1)]
 
for i in range(N - 1):
    a = int(input())
    children[a].add(i + 2)
 
ans = calc_depth(1)
 
# print(children)
 
print(ans)

コンテスト中に生み出されたコード（まともに動かない）

import sys

class Node:
    def __init__(self, key):
        self.key = key
        self.parent = None
        self.sibling = None
        self.degree = 0
        self.left = None
        self.right = None
        self.depth = None
        self.height = None
        self.ntype = 'leaf'

N = int(input())
tree = [None for i in range(N + 1)]
wl = {}
roots = set()
leaves = set()

for i in range(N - 1):
    k = i + 2
    j = int(input())

    if j in roots and k in roots:
        a = Node(j)
        a.left = tree[j]
        a.right = tree[k]
        tree[j].parent = a
        tree[k].parent = a
        tree[j] = a
        roots.remove(k)
        continue

    if j in roots:
        tree[k] = Node(k)
        a = Node(j)
        a.left = tree[j]
        a.right = tree[k]
        tree[j].parent = a
        tree[k].parent = a
        tree[j] = a
        leaves.add(k)
        continue

    if j in leaves:
        a = Node(j)
        tree[k] = Node(k)
        wl[j].left = a
        wl[j].right = tree[k]
        a.parent = wl[j]
        tree[k].parent = wl[j]
        wl[j] = a
        leaves.add(k)
        continue

    tree[j] = Node(j)
    tree[k] = Node(k)
    wl[j] = Node(j)
    tree[j].left = wl[j]
    tree[j].right = tree[k]
    wl[j].parent = tree[j]
    tree[k].parent = tree[j]
    roots.add(j)
    leaves.add(j)
    leaves.add(k)

print(tree)