2021-05-16

ABC201 参加記録

4完2ペナ 80分でした

A - Tiny Arithmetic Sequence

数列は増加列でも減少列でも良いので、ソートして差分が等しければ作れると判断できます。

B - Do you know the second highest mountain?

python では、列を指定してソートできるので、それを使います。 list.sort(key=lambda x: x[1], reverse=True) で書けます。

N = int(input())
l = []
for _ in range(N):
    S, T = input()[:-1].split()
    T = int(T)
    l.append((S, T))

l.sort(key=lambda x: x[1], reverse=True)
print(l[1][0])

C - Secret Number

全探索のやり方が思い浮かばなかったのは反省です。。本番では、丸の数が 5 個以上の場合は答え 0 、4個のときは、3個のときは、...とそれぞれで場合の数を求めて加算しました。使う数字の種類で並び替えの計算が変わるので、それぞれで計算する方針です。これは(工夫次第で短くはなると思いますが)実装の時間が取られますね。。

全探索の方針は、0000〜9999 を順に調べて、全ての o が含まれているかどうかチェックする方針です。こちらの方が考え方も実装もシンプルです。

ARC118 参加記録

AtCoder コンテスト参加記録

ACの2完0ペナ 79分でした

A - Tax Included Price

最初からなかなかハードな問題だと思いました。

式から $O(1)$ で求められそうな感じはしますが、わからなかったので実験しました。具体的には、実際に消費税 $t$ を固定して $1$ 円から順番に求めていき、スキップされたもの(税込み価格としては現れない正の整数の金額)を取りだして並べていきました。

そのあと、スキップされた値の差分を隣どうしとって行きます。そうすることで差分の周期性が見えてきます。実験から、以下のような動きをしていることがわかりました。

$t$ が 100 の約数であるときは、差分の周期は 1 で全て値は同じになる。
そうでないときは、差分のループは長さ $t$ の数列で表せる。

これらから、 $N$ をループの長さ $t$ で割ったときの商と余りを駆使して、 $N$ 番目の数字を $O(1)$ で計算することができます。

B - Village of M People

まず $a$ を数列 $A$ の各要素として、 $\frac{Ma}{N}$ を求めます。このとき、小数ではなく整数で扱いたいので、商を $B$ として扱い、余りの列を別で持っておきます。

数列 $B$ はこの時点では $\sum{B} = M$ を満たしていませんが、足りない部分を割り振ることによって数列 $B$ を完成させます。先ほど求めた余りの列の大きい順から割り振れば良くなります。余りは切り捨てたときの整数との距離のような値と解釈でき、余りが小さければ今 $B$ として決めた値に近く、そうでないときは +1 した値の方が近くなります。

C - Coprime Set

以下の2つが成り立つような数列 $A$ を作ります。

全ての $i, j$ で、 $i \neq j$ ならば $A_i \neq A_j$ かつ $\mbox{gcd}(A_i, A_j) \gt 1$ が成り立つ・・・①
$\mbox{gcd}(A_1, \cdots, A_N) = 1$ が成り立つ・・・②

まず $A_i$ に素数をもってくることができません。素数があれば ② を成り立たせるように作るのは簡単になりそうですが、①を成立させるには全てその素数の倍数でないといけません。そうすると結局②を成立させることができず、作れません。

また、4 などの 1種類の素数で構成された数字も使えません。これも、①を成立させるにはその一種類の素数の倍数である必要があり、②を満たせません。

そうしたときに、まず $N = 3$ で考えてみます。素数を使うことはできませんが、ふたつの異なる素数の掛け算で構成された値を使ってみるのはどうでしょうか。例えば、小さい順に、6, 10, 15 を考えてみると、それぞれ①②を満たします。

そして、これら $2\times3, 2\times5, 3\times5$ のどれかの倍数であれば、①②を満たしつつ数列を追加することができます。追加する際に 10000 より大きくならないことに注意すれば、この問題を解くことができます。

2021-05-02

ZONeエナジープログラミングコンテスト “HELLO SPACE” 参加記録

AtCoder コンテスト参加記録

A, B, D の3完0ペナ 40分でした

A - UFO襲来

長さが $12$ で固定のため、単純に調べれば OK です。

S = input(); cnt = 0
for i in range(len(S)):
    cnt += S[i:i+4] == 'ZONe'
print(cnt)

B - 友好の印

本番では切片の二分探索で解きました。今考えてみると、各障害物の座標それぞれについて、その座標と UFO の座標を通る直線の式を求めて、一番高い切片となったものが答えで良いですね。

C - MAD TEAM

解説ACです。本番では $O(N^{2})$ 解法でやってみましたが TLE でした。能力値の最大を持っている人をそれぞれ固定して残りを全探索する方針でしたが、これは嘘解法ですね。。そうでない場合も普通に作れそうです。

竸プロ典型90問でも、最大値の最小化は二分探索、というものがありますが、応用できませんでした。これを使って 0 1 にする発想は覚えておきたいです。

実装は、答えの値を二分探索で決め打ちして、各メンバーの能力がそれ以上かそうでないかを 1 0 で表現して圧縮し、3つ選んだときの組み合わせを探索する方針です。

ここで、5桁の bit で考えて実装するのがやりやすいかと思います。例えば、ある人の能力がそれぞれ [6, 7, 3, 1, 10] として、6 以上かどうかで 1 0 を振ることを考えたとき、これを 5桁の bit で見て、11001 (10進数だと25) とします。

あとは、3つの組み合わせの探索で bit の OR 演算を行い、結果 11111 になれば、二分探索で決め打ちした値は答えになり得ます。

(参考)提出コード

from itertools import combinations
import sys

input = sys.stdin.readline


def ORlist(l:list) -> int:
    res = 0
    for k in l: res = res | k
    return res


def main():
    N = int(input())
    energy = []
    for _ in range(N):
        A, B, C, D, E = map(int, input().split())
        energy.append((A, B, C, D, E))
    
    R = 10**9 + 1 # right side
    L = 1   # left side
    while True:
        if L+1 >= R:
            break
        mid = (L+R)//2
        energyset = set([])
        for ener in energy:
            A, B, C, D, E = ener
            s = 2**4*(A >= mid) + 2**3*(B >= mid) + 2**2*(C >= mid) + 2**1*(D >= mid) + 2**0*(E >= mid)
            energyset.add(s)
        energylist = list(energyset)
        flag = False
        for iters in combinations(energylist, min(3, len(energylist))):
            res = ORlist(list(iters))
            if res == 2**5-1:
                flag = True
                break
        if flag: L = mid # True
        else: R = mid # False
    print(L)


if __name__ == "__main__":
    main()

D - 宇宙人からのメッセージ

ABC199 の C問題と発想は同じです。

操作が二種類あり、そのうち「末尾に加える」は $O(1)$ でできるので良いのですが、「反転させる」操作は $O(|S|)$ かかる操作なので、実際に反転させる処理を書くと TLE になると思います。

したがって、「反転させる」が起こったら、挿入位置の方を反転させて、「先頭に加える」ようにします。末尾にも先頭にも $O(1)$ で追加したいので、collections.deque を使います。

反転しているかどうかは flag で管理しました。

また、問題文では最後に同じ文字が2文字連続したら取り除く操作をしていますが、この操作は挿入した段階で消しても変わりません。むしろ挿入段階でやった方が abba など対応しにくい形も気にせず取り除けるので、挿入段階で消してしまいます。

提出コード

from collections import deque


def main():
    S = input()
    flag = False
    ans = deque([])
    for s in S:
        if s == 'R':
            if flag: flag = False
            else: flag = True
        else:
            if flag: # 反転しているとき
                ans.appendleft(s)
                if len(ans) >= 2:
                    if ans[0] == ans[1]:
                        ans.popleft()
                        ans.popleft()
            else:
                ans.append(s)
                if len(ans) >= 2:
                    if ans[-1] == ans[-2]:
                        ans.pop()
                        ans.pop()
    if flag:
        ans.reverse()
    print(''.join(ans))


if __name__ == "__main__":
    main()

ABC199 参加記録

AtCoder コンテスト参加記録

3完0ペナ 26分でした
DかE解いたら出そうと思ったことで提出が遅れました。。

A - Square Inequality

問題文の通り実装します。

A, B, C = map(int, input().split())
if A ** 2 + B ** 2 < C**2:
    print('Yes')
else:
    print('No')

B - Intersection

全ての $i$ で $A_i \leq x \leq B_i$ が成り立つと言うことは、 $A_i$ の中で最も大きいものが $x$ の最低ラインになり、 $B_i$ の中で最も小さいものが $x$ の最大ラインになります。

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ans = min(B) - max(A) + 1
if ans < 0: ans = 0
print(ans)

C - IPFL

$T_i = 1$ のときは単純に入れ替えをすればよさそうですが、 $T_i = 2$ のときの操作をそのまま実装すると、文字列の結合の計算量は結合される文字列の長さに依存するため、 $O(N^{2})$ になりTLEになることが予想できます。

したがって、前後半を入れ替える操作をするのではなく、入れ替える場所を前後半で変える操作にします。具体的には以下のイメージです。

f:id:Xenous:20210425142432p:plain — 1番目と4番目の入れ替え操作イメージ

0-index で考えると、 $T=2$ の操作で入れ替えが起こった状態のときに、 $T=1$ の操作をするときは、入れ替え先が $(A, B)$ から $(N+A, N+B) \ \mathrm{mod}\ 2N$ となります。

$T=2$ の入れ替えが起こった状態の管理は flag 等で管理して、最後に前後半を入れ替える必要があれば実際に行って出力すれば良いです。

import sys
input = sys.stdin.readline

N = int(input())
S = list(input()[:-1])
Q = int(input())
flag = True
for _ in range(Q):
    T, A, B = map(int, input().split())
    A -= 1; B -= 1
    if T == 1:
        if flag:
            S[A], S[B] = S[B], S[A]
        else:
            a = (N+A)%(2*N)
            b = (N+B)%(2*N)
            S[a], S[b] = S[b], S[a]
    else:
        if flag: flag = False
        else: flag = True
if flag: ans = S
else: ans = S[N:] + S[:N]
print(''.join(ans))

D - RGB Coloring 2

本番では DFS で実装しましたが、いくつか考察が甘いところがあり、結局正解からは程遠かったです。。自分用の戒めとして正解に辿り着くまでの軌跡を残しておきます。

まずサンプルにあるように、非連結の場合があります。したがって UnionFind を使って連結成分ごとの管理をし、各グループに対して配色を探索することにします。頂点が 1 つであれば、3 通りです。そうでない場合は DFS で探索する方針にしました。

(考察が甘かった部分その1) 重複のある探索

最初に実装したのは単純な DFS による探索です。最初の頂点の色を固定して、他の頂点はグラフに沿って「直前の頂点の色と異なる」条件で探索します。この方法は、下記のような重複が発生してしまい、答えが合いません。

f:id:Xenous:20210426215913p:plain — 頂点1 を`R`で固定した DFS の色の重複

※ 頂点 1 を赤で固定します。DFS で、2 が緑、3 が青のパターンと、2 が青、3が緑のパターンをやり切った後、今度は右図のように 3 が緑、2 が青という探索をします。このとき、この並び順はすでに出てきており、重複が発生します。

(考察が甘かった部分その2) 全ての頂点を配色していない

上記を解消すべく、全域木を作る要領で辺と頂点を管理して探索を行うようにしたところ、重複をしない探索が可能になりました。しかし、まだ問題は残っています。下記のようなグラフで DFS をすると、「全ての頂点を塗った状態」を作れません。

f:id:Xenous:20210426224954p:plain — 頂点 1 から DFS を行ったときのイメージ

最初は頂点 1, 2 と色を決め, 頂点 3 で赤, 青の二通りを探索します。その後頂点 4 に向かうわけですが、このとき頂点 3 の色を戻しておかないと、頂点 2 の次の色 (この図だと青) の探索のときに先に進まなくなってしまいます。

ということで、グラフをそのままDFSして探索するのはなかなか難しそうです。下の図の左側のように、頂点3 に行った後、そのまま頂点4 に向かって欲しいわけです。頂点を隣接した順に塗っていくにはどうしたらいいかを考えます。

f:id:Xenous:20210426231354p:plain — 頂点の巡り方イメージ

（図の右側のグラフでは、頂点 1 → 2 → 5 → 3 → 4 と探索する、というようなイメージです。）

巡る頂点の順番を決めてから探索する

上のイメージのように、頂点を隣接している順に見ていくには、配色しないただグラフをたどるだけの DFS を最初に行い、探索した順の頂点リストを用意すればOKです。このリストに対して配色の DFS を行うと、望んだ動きを実現できます。

この方針は、公式解説と同じになります。以下は参考で、提出コードです。

提出コード

import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

# union find は省略

def dfs_vertex(p:int, fr:int) -> None:
    """
    探索する頂点の順番を決めるために DFS しとく
    """
    global graph, vertexlist, goneset
    for to in graph[fr]:
        if to in goneset:
            continue
        goneset.add(to)
        vertexlist.append(to)
        dfs_vertex(fr, to)


def dfs(n:int) -> None:
    """
    色を実際に試す
    自分の色を決める
    """
    global graph, vertexlist, colorlist, res
    colorselect = set(['R', 'G', 'B'])
    fr = vertexlist[n]
    # 色の候補を絞る
    for to in graph[fr]:
        if colorlist[to] in colorselect: colorselect.remove(colorlist[to])
    # 配色を探索する
    for s in colorselect:
        colorlist[fr] = s
        if n+1 < len(vertexlist):
            dfs(n+1)
        else:
            # 全ての頂点を塗れたらカウントする
            res += 1
        colorlist[fr] = '*'


def main():
    global graph, vertexlist, goneset, colorlist, res
    N, M = map(int, input().split())

    # グラフの作成
    uf = UnionFind(N)
    graph = [[] for _ in range(N)]
    for _ in range(M):
        A, B = map(int, input().split())
        A -= 1; B -= 1
        graph[A].append(B)
        graph[B].append(A)
        uf.union(A, B)

    # 答え計算用のリスト
    ans = [1] * N
    # 配色を一時保存するリスト
    colorlist = ['*'] * (N+1)

    # 各グループの代表の頂点ごとに見る
    for p in uf.grouping:
        # 頂点が 1 つだけのときは 3 通り
        if uf.msize(p) == 1:
            ans[p] = 3
        # それ以外は DFS して探索
        else:
            # まずは巡る頂点の順番を作るための DFS
            goneset = set([p]) # 一度通った頂点管理用
            vertexlist = [p]   # 探索した順の頂点リスト
            dfs_vertex(-1, p)
            
            # 各頂点の配色を行う DFS
            res = 0
            colorlist[p] = 'R'
            dfs(1)
            ans[p] = res * 3

    # 答え計算
    r = 1
    for a in ans:
        r *= a
    print(r)


if __name__ == "__main__":
    main()

E - Permutation

2021-05-09 追記. (解説 AC)

bitDP の問題でした。順序の情報が必要かどうかで bitDP ができるかどうかが決まると思うのですが、本番中では順序の情報が不要であることに自信が持てず、解けませんでした。

まず全探索は $O(N!)$ なので間に合いません。bitDP はこれを(多くの場合) $O(N2^{N})$ に改善してくれるわけですが、順序を無くした集合として状態を持っていいのかどうかがポイントになります。

例えば $N = 5$ で、3番目までを $\{1, 2, 5\}$ と持っていたとして、次に 3 を加える操作について考えます。条件で 3, 3, 2、つまり「3番目までの数列で 3 以下の数が 2 つ以下しかない」があったとき、3 を加えると $\{1, 2, 5, 3\}$ となります。

ここで、この集合において、上記の条件を満たさない [3, 1, 2] や [1, 3, 2] は気にしなくて良いのか、と思ってしまい（それ自体は良い）、本番で止まってしまったのですが、結果的には「上記のような条件を満たさない場合はちゃんと除いてあって、すでに正しく計算している」ことになります。DPなので。それぞれ以下のように遷移してきているはずです。

集合 $\{3\}$ に 1 を加えて $\{1, 3\}$ 。さらに $\{1, 3\}$ から 2 を加えて $\{1, 2, 3\}$
集合 $\{1\}$ に 3 を加えて $\{1, 3\}$ 。さらに $\{1, 3\}$ から 2 を加えて $\{1, 2, 3\}$

集合 $\{1, 3\}$ の結果には、1 から並べた場合と、3 から並べた場合の両方を調べた結果が入っています。従って、これまでの並び順によらず、加えた後の長さと等しい条件だけ調べれば良いことになります。

このように考えることができるのは、DPの定義をうまく定めるからです。今回の場合は公式解説の通り、 $\mbox{DP}_S$ （ $S$ は $\{1, 2, \cdots, N\}$ の部分集合）を「 $a$ の先頭 $|S|$ 要素まで決めていて、その $|S|$ 要素で使った数の集合がちょうど $S$ に一致し、 $X_i \leq |S|$ であるような条件は全て満たしているような場合の数」とすると、上記のような考え方が成り立ちます。

さて、実装部分についてですが、大枠の方針は以下の通りです。

$1$ から $2^{N}$ までをループ。各値の bit 列の 1 が立っているところを集合 $S$ として持っている状態と考える（5 なら二進数は 101 で集合としては $\{3, 1\}$ ）
集合 $S$ の中に含まれている要素 $x$ でループ。その要素を除いた集合を $D$ とする。 $S = D \cup \{x\}$ が成り立つ。 $D$ に $\{x\}$ を加える操作として考える。
$|S|$ での条件が存在しない場合は、そのまま $\{x\}$ を加える。すなわち、 $\mbox{DP}_S$ に $\mbox{DP}_D$ を加算する。
$|S|$ での条件が存在する場合は、数列の最後に $x$ を加えたときに全ての条件が成立するかチェックし、成立すれば $\mbox{DP}_S$ に $\mbox{DP}_D$ を加算する。成り立たない場合は $\mbox{DP}_S$ への加算は行わない。

提出コード

import sys

input = sys.stdin.readline

# popcount(x:int) -> int: は省略
# xの立っているビット数をカウントする関数

def main():
    N, M = map(int, input().split())
    condi = dict()
    for _ in range(M):
        X, Y, Z = map(int, input().split())
        if X not in condi:
            condi[X] = []
        condi[X].append((Y, Z))
    
    # 初期化
    DP = [0]*(1 << N)
    DP[0] = 1

    for S in range(1, 1 << N):
        lenS = popcount(S)
        for a in range(N):
            # a が S に含まれていなければスキップ
            if S & (1 << a) == 0:
                continue

            # D = S U {a}
            D = S ^ (1 << a)
            if lenS not in condi:
                DP[S] += DP[D]
                continue
            for y, z in condi[lenS]:
                # 左から lenS 個までの数列を取り出して popcount
                k = popcount(S & ((1 << y)-1))
                if k > z:
                    break
            else:
                DP[S] += DP[D]
    
    ans = DP[(1 << N)-1]
    print(ans)


if __name__ == "__main__":
    main()

2021-04-18

第二回日本最強プログラマー学生選手権参加記録

AtCoder コンテスト参加記録

4完1ペナ 32分でした

A - Competition

数式で解いて $O(1)$ で求めることが可能ですが、コンテスト中は混乱していて、販売価格の二分探索をしました。

販売価格を $W$ としたとき、 $\frac{W}{Z} \lt \frac{Y}{X}$ より、 $W \lt \frac{YZ}{X}$ が成り立つ最大の非負整数を求めれば良いです。

B - Xor of Sequences

集合で言うと、 $(A \cup B) - (A \cap B)$ を求めれば良いです。

以下の要領で求められます。

N, M = map(int, input().split())
A = set(list(map(int, input().split())))
B = set(list(map(int, input().split())))
C = A.intersection(B) # 共通部分
D = A.union(B)  # 和集合
D.difference_update(C)
ans = list(D)
ans.sort()
print(*ans)

C - Max GCD 2

上手いやり方が思い浮かばなかったので約数を列挙する方針で解きました。

$A$ から $B$ までの各値の約数を求め、出現回数をカウントし、2回以上現れたもののうち最大を答えとすれば良いです。約数は $O(\sqrt{N})$ で求められるので、最悪計算量は $O(N\sqrt{N})$ です。

python で提出して TLE になり、pypy では間に合いました。

D - Nowhere P

$P$ の倍数かどうかを判定する際に、 $P$ で割ったあまりを見ると考えやすいです。

最初は $1$ 以上 $P-1$ 以下の数全てが候補になるので、 $P-1$ 通りあります。
次は、加算したあとに $P$ で割ったときのあまりが $0$ にならないように考えます。例えば $P = 6$ のとき、直前で $4$ を選んでいたとしたら、次に $2$ を選ぶことはできません。 $A_1 + A_2$ のあまりが $0$ にならないためには、最初に選んだ数字に対して、あまりが $0$ になるもの以外の $P-2$ 通りが候補になります。
その次は、 $A_1 + A_2 + A_3$ のあまりが $0$ にならないようにします。 $A_1 + A_2\ (\mathrm{mod}\ P)$ の値は $0$ でないので、状況的には一つ前と同じで、 $P-2$ 通りが候補になります。

このように、最初は $P-1$ 通り、それ以降は $P-2$ 通りとなるので、あとは数列の長さ分計算すれば答えになります。

python には組み込み関数に pow(x, y, M) (= $x^{y}\ \mathrm{mod}\ M$ ) が使えるので、これで計算できてしまいます。

F - Max Matrix

和の計算量を落とせず解けませんでした。後日書きます。。

H - Shipping

問題文を読むといけるんじゃないかと思ってやってみましたが、超難問でした。解説読んで理解できたら更新します。。

2021-04-14

バーチャル参加 ABC001

バチャ参加記録

4完2ペナ 81分でした
アルゴリズムというよりゴリゴリの実装問題ですね。意外と実案件ではこのようなデータの整形に出くわす場面が多く、なんだかんだこういう問題も役に立つと思います。

A - 積雪深差

入力を受け取って引き算して返します。

B - 視程の通報

与えられるテストケースの制約の記載があります。ルールにしたがって計算したときに整数にならないことはないので、切り捨ての割り算で整数型のまま計算できそうです。

あとは書かれた条件を if や elif、else を使って記述します。

C - 風力観測

結構面倒な問題です。B問題と同じく if else をたくさん書けば実装はできます。無駄なく書こうとするとちょっと考えてしまいますね。私が思いついたのは次の二つです。

for 文で回せるところは回す
エディタの複数選択を使う

これらで時短しつつ、条件をコードに落とします。誤差については、float で扱わず、Decimal で計算してしまえば問題なさそうです。四捨五入や切り捨てなども Decimal を使います。

小数点の四捨五入(風速の計算で使用)

from decimal import Decimal, ROUND_HALF_UP

# 風向、風程
Dig, Dis = map(str, input().split())

# 条件に合わせるための処理
DDig = Decimal(Dig)/10
DDis = Decimal(Decimal(Dis)/60).quantize(Decimal('0.1'), rounding=ROUND_HALF_UP)  # 秒速にして小数第二位で四捨五入

float 型で小数点どうしの引き算や割り算を行うと誤差が生じます。多少の計算であれば問題ないのですが、大きな数をかけたり複数の処理を噛ませると誤差が大きくなり結果間違えることは往々にしてあるので、気をつけましょう（自戒）。

17.2 - 20.8
# -3.6000000000000014

D - 感雨時刻の整理

これも結構面倒です。入力された時刻を条件通りに丸めることと、結合することの2種類の操作を行います。

条件通りに丸める方法は、次のようにすることでできます。

降り始めの時刻は、5で割ったあまりを引く
降り止んだ時刻は、5で割ったあまりを5から引いた値を足す。ただし5で割ったあまりが0なら何もしない。
さらに、100で割ったあまりに対して、それが「0 でない」かつ「さらに 60 で割ったあまりが 0」なら40を足す。

もっとスマートにやれそうですが、ひとまずこんな感じでできます。

# '-' で分割した値を格納
fr, to = input().split('-')
# 丸める
fr -= fr%5
to += (5 - to%5) * (to%5 != 0)
# 繰り上げ処理
to += 40 * ((to%100)%60 == 0 and (to%100 != 0))

次に時間の結合を行います。まず降り始めた時間でソートしておきます。そうすると、降り止んだ時間が、次の降り始めた時間より遅いのであれば、結合することができます。そうでない時は結合せず別物として扱います。

最後に0埋めをしつつ形式に合わせて表示すれば回答できます。

まとめると、以下のように実装できます。

# 入力
N = int(input())
l = []
for _ in range(N):
    fr, to = input().split('-')
    fr = int(fr); to = int(to)
    fr -= fr%5; to += (5 - to%5) * (to%5 != 0)
    # 繰り上げ処理
    to += 40 * ((to%100)%60 == 0 and (to%100 != 0))
    l.append((fr, to))

# 降り始めの時刻でソート
l.sort(key=lambda x: x[0])

ans = []
bf_fr, bf_to = l[0]
for i in range(N-1):
    af_fr, af_to = l[i+1]

    # 降り止んだ時刻の後に降り始めた時刻が来ている場合は別物扱いする
    if bf_to < af_fr:
        ans.append((bf_fr, bf_to))
        bf_fr, bf_to = af_fr, af_to
    # 降り止んだ時刻の前に降り始めた時刻が来ている場合はまとめる
    else:
        bf_to = max(bf_to, af_to)

# 最後の分を追加する
ans.append((bf_fr, bf_to))

# zfill で先頭を 0 埋めしてから表示する。
for fr, to in ans:
    fr = str(fr).zfill(4)
    to = str(to).zfill(4)
    res = fr + '-' + to
    print(res)

意外と時間がかかってしまいました。昔と今だと問題のテイストも結構違いましたね。

2021-04-12

ABC198 参加記録

AtCoder コンテスト参加記録

4完3ペナ 56分でした

A - Div

お菓子を1つ以上分けるパターンを考えてみると、例えば $N = 4$ のときは、3個と1個、2個と2個、1個と3個という分け方の $3$ 通りがあり、他の $N$ でも試すと、結局 $N-1$ 通りあることがわかります。

B - Palindrome with leading zeros

0 をつけて回文にするということは、与えられた文字列の末尾の 0 を消したときに、残った文字列が回文になっているかどうかを考えればよさそうです。数値は $10^{9}$ までの範囲で与えられますが、桁数に注目すればよく、問題なく回文かどうかを確認することができます。

C - Compass Walking

2ペナもらいました。

まず $(X, Y)$ に到達するまでの最小の歩数を求めるには、直線で向かったときに少なくとも何歩かかるか、を考えました。大体のケースではこれで良いのですが、与えられた $(X, Y)$ が、原点を中心とした半径 $R$ の円内(円周上は含まない)にある場合は、一歩目が大きすぎて、必ず2歩必要になります。

したがって、まずは $(X, Y)$ が半径 $R$ の円内にあるかを判定して、円内なら答えは 2 です。そうでない場合は、そのままユークリッド距離を $R$ と比較すれば良いです。ただし、ルートをとると誤差が生じて正しい答えにならない場合もあるので、なるべく整数のまま扱います。以下を満たす最小の自然数 $k$ を求めることを考えます。

$\sqrt{X^{2} + Y^{2}} \leq kR$

これを両辺2乗します。

$X^{2} + Y^{2} \leq k^{2}R^{2}$

あとは $k$ について二分探索すれば、最小の $k$ を求めることができます。今回の問題では、 $k$ は $\left\lceil\sqrt{2}\times10^{5}\right\rceil$ 以下であることがわかるので、全探索することも可能です。

以下は全探索のコードです。

R, X, Y = map(int, input().split())
D2 = X**2 + Y**2; R2 = R**2
if D2 < R2:
    print(2)
else:
    for z in range(10**6):
        if D2 <= z**2 * R2:
            print(z)

D - Send More Money

バグらせてしまい、本番では AC できませんでした。スマートに書けなかったので、他の方の提出コードを参考にしつつ解きました。

方針は、文字列と0 〜 9 の数字を当てはめる全探索で良いです。計算量は長さが最大 $10$ である 3 つの文字列と、文字種が最大で $10$ 個しかなく、その順列を考えるので $O(3\times10\times10!)$ くらいです。これは $10^{8}$ より少し多いくらいの計算量になり、5sec ありますが重い処理を書いてしまうと TLE します。

まず、使われた文字種が 11 以上だと、0 〜 9 を構成したときに使われない文字が生じてしまうため、UNSOLVABLE です。
次に、どの文字にどの数字を当てはめるかを順列で実装します。0 〜 9 のうち、文字の種類数ぶん取り出して並べます。python であればitertools.permutations() があります。
そして、各文字種と、並び替えた 0 〜 9 の値を入れ替えます。str.replace() で実行可能です(str は文字列型の変数だと思ってください)。実際に足し算をして成立すればそれを答えとします。

ただ、上記の計算だと間に合わないパターン場合があります。今回実装が簡単な枝刈りとして、1桁目の計算をして、正しくなかったら replace 処理をスキップすることで少し軽くなります。

また、0 単体で使えないことと、無駄な 0 がある数字(例えば 0321)は認めないことに注意すれば、ACできます。

個人的に以下の点が反省点です。。

replace が頭から抜けており、for 文で文字列の書き換えを書いていたこと
- 基本は組み込み関数を使った方がシンプルに書けてかつ速いと思ってます。
最初の UNSOLVABLE の判定で桁数の無駄な確認などをしていたこと(OKなのに UNSOLVABLE にしてしまう可能性が生じる)

E - Unique Color

木構造の問題です。

ある頂点から DFS を行うと計算量は $O(N)$ になります。頂点 $1$ から出発したとき、DFS で探索しつつ、色の出現回数をカウントし、到達した頂点の色がまだカウントに現れていなかったら、答えのリストにその頂点番号を追加します。

DFS では、再帰関数で潜った後に戻ってくる際、色の出現回数を元に戻すことができます。具体的なコードは以下のような形です。
colordict はカウンターオブジェクト、ki は隣接リスト、ans は回答を保存するリスト、C は各頂点を保存しているリストです。

def dfs(n:int, p:int) -> None:
    global colordict, ki, ans, C
    # 深く潜っていくときに、色のカウントを行う
    if colordict[C[n]] == 0:
        ans.append(n)
    colordict[C[n]] += 1
    for to in ki[n]:
        if to != p:
            dfs(to, n)
    # 色のカウントを元に戻す
    colordict[C[n]] -= 1

この考え方はよく使うと思います。類題をご参考までに記載しておきます。

python では、再帰の上限が決まっていますが、sys.setrecursionlimit(10**6) を記載しておけば大体OKです。(忘れており1ペナ食らってしまいました）

(考察が甘かった部分 その1) 重複のある探索

(考察が甘かった部分 その2) 全ての頂点を配色していない

巡る頂点の順番を決めてから探索する

(考察が甘かった部分その1) 重複のある探索

(考察が甘かった部分その2) 全ての頂点を配色していない