2019-05-14

diverta 2019 Programming Contest の反省

A問題

題意を勘違いしていて無駄に時間を使ってしまう。AC。コード。

ここまで4:48。

B問題

やるだけ。コード。

ここまで9:30。

C問題

場合分けがややこしそうだったので、最初に「Bで始まる&&Aで終わる」文字列を特別扱いして考えたらすんなりいってよかった。実力が上がって良い場合分けが出来るようになったのか、たまたま運が良かったのかわからん。コード。

ここまで21:15。

D問題

高校数学みたいな問題。nが10¹²の問題は、計算量O(\sqrt{n})かO(1)だなとわかるので考えやすい。コード。

ここまで39:16。

E問題

いきなり難しすぎる。10分くらい考えて無理だったので、諦めてビールを買いに行った気がする。

F問題

ビール。

反省

解ける問題は解けて解けない問題は解けないという感じ。今回のコンテストで言うところのE問題以降を解けるようになるためにはかなり壁がある気がする。順位が300位以内だったのでレートどんだけ上がるんだ...？と思ったらunratedで本当に悲しかった。

2019-05-14

20190502-20190514のatcoder埋め

たまにやってます。

abc104

a - 1:00でAC。
b - 4:50でAC。

abc105

a - 0:50でAC。
b - 4:50でAC。

abc106

a - AC。
b - AC。
c - AC。
d - 解説を見ながら40分くらいでAC。想定解法をpythonで実装するとTLEになったので、二次元累積和を使う方法でやったら通った。二次元累積和について前に勉強してたはずなのにとっさに出てこなくて悲しみ。

abc107

a - AC。
b - AC。意外とめんどくさかった。
c - AC。最初DPかと思って考えてたけどよくわからなくて、冷静に考えたら取るK本は必ず連続するということに気づいて、連続するK本の組み合わせを全て考えるという方針で解けた。
d - 諦め。解説を読んでもよくわからないので一旦おいておく。

abc108

a - AC。
b - AC。
c - AC。方針が立つまでにやや時間がかかった。
d - 諦め。一旦おいておく。

abc109

a - AC。
b - AC。
c - AC。問題文を読んで最大公約数でOKっぽいなと思ったらOKだった。最初、３つ以上数値の最大公約数を再帰でやったらREになったのでスタックオーバーフローかなと思ってfor文に書き換えたら通った。
d - 解説を見ながらAC。発想力が無。

abc110

a - AC。
b - AC。若干ややこしかった。
c - AC。最初、sとtのあるインデックスの文字が同じだった場合を無視してしまっていたが、これも同じ文字への変換とみなして考慮に入れないといけなかった。

abc111

a - AC。
b - AC。
c - AC。番兵的なやつを追加して処理を簡単にするのがうまくできた。

abc112

a - AC。
b - AC。
c - 解説を見てAC。実装の方針が難しくて、解説を見たにも関わらずかなり手間取ってしまった。
d - AC。最初partitionという問題名を見て反射的に分割数の組み合わせを求めようとしてしまったが、冷静に考えて間に合うはずがなかった。よく考えると、単に最大公約数の候補となる整数について、それが実際に最大公約数になりうるか試していくだけでよかった。

abc120

a - AC。
b - AC。
c - AC。なんか難しいことを考えなければいけないのかと思ったら、特にそんなことはなかった。
d - AC。問題を見て、橋を落としていくのではなく追加していくほうが簡単そうだなと思えた＆UnionFindを使うことがすぐわかったので成長を感じた。途中謎のREになったので、何度か怪しいところを直していったら無事ACになった。

abc121

a - AC。
b - AC。
c - AC。C問題にしては簡単すぎる。
d - 解説を見てAC。解けなかったけど、連続する整数のXORについての性質を勉強できたのでよかった。
- 任意の整数nについてn ^ (n+1)は1
- 連続する整数x - yのXORをf(x, y)とすると、自分自身とのXORは０よりf(x, y) = f(0, x-1) ^ f(0, y)

2019-05-11

自然数を分割する方法をpythonで列挙する

分割数の求め方。

def partitions(n):
    if n == 0:
        yield []
        return

    for p in partitions(n-1):
        yield [1] + p
        if len(p) == 1 or (len(p) > 1 and p[0] < p[1]):
            yield [p[0] + 1] + p[1:]


print(list(partitions(1))) # => [[1]]
print(list(partitions(2))) # => [[1, 1], [2]]
print(list(partitions(3))) # => [[1, 1, 1], [1, 2], [3]]
print(list(partitions(4))) # => [[1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3], [4]]
print(list(partitions(5))) # => [[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 2, 2], [1, 1, 3], [2, 3], [1, 4], [5]]

参考

code.activestate.com

2019-05-03

最短経路を求める３つのアルゴリズム

蟻本の2-5節を読んで最短経路を求める方法を学んだのでまとめです。

1 ベルマン・フォード法

ある一点から全ての点への最短距離を求める方法の一つ。辺一つ一つについて、辺の向き先の点へのスタート地点からの距離が短く更新できないかを何回も繰り返し見ていく。負の閉路がなければ、辺の数を|V|として|V|-1回で収束する。逆に、|V|-1回で収束しない場合は負の経路があるということなので、負の経路の検出にも使える。計算量はO(V^2)。

Edge = namedtuple('Edge', ('fr', 'to', 'cost'))

def bellman_ford(n, start, edges):
    dists = [inf for _ in range(n)]
    dists[start] = 0
    while True:
        updated = False
        for e in edges:
            if dists[e.fr] != inf and dists[e.fr] + e.cost < dists[e.to]:
                updated = True
                dists[e.to] = dists[e.fr] + e.cost

        if not updated:
            break

    return dists

2 ダイクストラ法

ある一点から全ての点への最短距離を求める方法の一つ。最短距離を確定している点を一つ一つ増やしていく方法。最初、スタート地点への距離が0で、これが最短ということがわかっている。スタート地点と直接繋がっている点について、それぞれ仮の最短距離をスタート地点と繋がっている辺の長さとする。このうち、仮の最短距離がもっとも短い点については、それが真の最短距離であると確定できるので確定し、その点と繋がっている点について仮の最短距離を更新...ということを繰り返していく。最短距離がもっとも短い点を選び出す処理に優先度付きキューを使うと、計算量はO(E logV)とベルマンフォードよりも小さくなる。

def dijkstra(n, start, costs):
    dists = [inf for _ in range(n)]
    dists[start] = 0

    queue = []
    for (i, d) in enumerate(dists):
        heapq.heappush(queue, (d, i))

    while len(queue) > 0:
        d, i = heapq.heappop(queue)
        if d > dists[i]:
            continue

        for v in range(n):
            if v == i or costs[i][v] == inf:
                continue

            if dists[i] + costs[i][v] < dists[v]:
                dists[v] = dists[i] + costs[i][v]
                heapq.heappush(queue, (dists[v], v))

    return dists

3 ワーシャルフロイド法

全ての点から全ての点への最短距離を求める方法の一つ。dp[k][i][j]を0 - kの点のみを使ったiからjの最短距離として、dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])という漸化式で更新していく。計算量はO(E^3)。実装が単純なので、計算量に余裕があるならば、一点からの最短距離しか必要でない場合にも使うと良い。

def warshall_floyd(n, costs):
    dists = [[costs[i][j] for j in range(n)] for i in range(n)]

    for k in range(n):
        for i in range(n):
            for j in range(n):
                dists[i][j] = min(dists[i][j], dists[i][k] + dists[k][j])

    return dists

2019-05-02

UnionFind木の実装（atcoder ABC097のD問題）

UnionFind木、どういうものでどういう時に使うのかをなんとなく知ってただけで実装したことがなかった。abc097のD問題で実際に使うことになってpythonで実装したのでメモしておく。木の偏りをなくす工夫とかはしてないけど、要素の親だけでなく根からの深さを持つようにすればできるはず。次UnionFind木が必要にな問題に当たったら絶対正解したい。

class UnionFind:
    def __init__(self, elems):
        self.parent = dict()
        for e in elems:
            self.parent[e] = e

    def root(self, e):
        if self.parent[e] == e:
            return e

        self.parent[e] = self.root(self.parent[e])
        return self.parent[e]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        if self.same(x, y):
            return

        self.parent[self.root(x)] = self.root(y)


n, m = map(int, input().split())
p = list(map(lambda z: int(z) - 1, input().split()))

uf = UnionFind(list(range(n)))

for _ in range(m):
    x, y = map(lambda z: int(z) - 1, input().split())
    uf.unite(p[x], p[y])

count = 0
for i in range(n):
    if p[i] == i or uf.same(p[i], i):
        count += 1

print(count)

2019-05-01

20190501のatcoder埋め

今日は蟻本でDPのところを読んでて、DPの練習がしたくなったので Educational DP Contestを解いてた。途中、完全に想定されてる解法なのにpythonだとTLEになり続けるので、きれて今後はc++を使っていくことにした。今日はc++に慣れるために、C問題までを出来るだけ多く解いてみた。なんとなくc++の感覚がわかってきたが、python/rubyで解いていた時と比べると時間がかかってしまう。しばらくは、コンテスト本番ではとりあえずpythonで解いてみて計算量的には間に合うはずなのになぜかTLEになるという時にc++を使うようにするかも。

edpc

時間を計り忘れた。

a - AC。
b - AC。
c - AC。
d - AC。
e - AC。
f - AC。DPの結果をあとで復元するやり方が勉強になった。

abc098

a - AC。
b - AC。
c - AC。

abc099

a - AC。
b - AC。
c - AC。

abc100

a - 2:50でAC。
b - 4:50でAC。
c - 3:10でAC。

abc101

a - 1:40でAC。
b - 5:30でAC。
c - 14:50でAC。

abc102

a - 1:20でAC。
b - 2:40でAC。
c - 10:00でAC。

abc103

a - 2:50でAC。
b - 10:30でAC。
c - 5:00でAC

2019-05-01

20190430のatcoder埋め

abc096

a - 1:20でAC。
b - 1:30でAC。
c - 8:10でAC。
d - 解けずに諦めた。素数を小さい順に見ていって条件に合えば入れていく方針で計算量的に行けそうと思って解き始めると、55555以下の制限に引っかかってうまくいかない。解説見てなるほど…。こういうひらめきを要求される問題が苦手な気がする。考えていた方針がだめだったときにちゃんと１から考え直す余裕を持ちたい。今回は、pythonでエラトステネスの篩を書く練習ができたので良しとしよう。

abc097

a - 3:30でAC。
b - 4:40でAC。
c - 10:30で部分点。その後工夫して少しは早くなったけどACできず。解説を読んで２行足して提出したらACで悲しくなった。
d - 解けずに諦めた。方針はなんとなくわかったが、TLEにならない実装が思いつかず、解説を見たらunion-find木を使うらしい。知識が不足してることを実感したので一旦蟻本を進めることにする。