2020-06-08

ARC034 C - 約数かつ倍数

競プロ

問題原文

atcoder.jp

解法

制約が本質。
↓こういう感じになってる。

f:id:AT274:20200608202814p:plain

実際に約数の個数を考える必要があるのは、 $B!$ より上の部分。
これは最大でも100個なので、それぞれについて素因数分解しても全然間に合う。

実装

from collections import Counter
A, B = map(int, input().split())
MOD = 1e9 + 7
C = Counter([])


def prime_factorization(n):
    table = []
    for x in range(2, int(n ** 0.5) + 1):
        while n % x == 0:
            table.append(x)
            n //= x
    if n > 1:
        table.append(n)
    return table


for n in range(B + 1, A + 1):
    table = prime_factorization(n)
    C += Counter(table)

ans = 1
for v in C.values():
    ans *= (v + 1)
    ans %= MOD

print(int(ans % MOD))

感想

まぁこれはサクサク。
なんかもっと綺麗な図を書きたいのでタッチパッド的なやつが欲しくなる。

2020-06-07

CodinGame Spring Challenge 2020 参加記

これはなに

5/8 00:00 ~ 5/18 17:00 の期間で開催されたゲームAI開発コンテスト、CodinGame Spring Challenge 2020 の参加記録になります。
もう１ヶ月も前の話なのですね。遅くなって申し訳ないという気持ちです。ゆるして。
ちなみにコドゲに参加した人向けに書きます。ゆるして。

ルール

結構ややこしいです。ツカモさんの記事を見ていただければと思います。
tsukammo.hatenablog.com

ありがとうございます、ツカモさん。

結果

世界111位/4955人、日本18位 / 227人でLegendLeagueでした。 f:id:AT274:20200607163154p:plain

コンテスト後は何も触ってないんですが、今見たら世界80位/5089人、日本16位 / 233人まで上がってました。何でだろう。

戦術について

本題です。

探索について

「どうペレットを探すか」です。ここに無限に時間を使い、実に５日間ほどハマりました。

結局探索については以下のようなロジックで行うことになりました。
このロジックはWood1で考えたあと、最後まで使い続けることになりました。

自分のパック全てについてどの方向に動くのかを決める。
例えば、今回自分のパックは最大５体ですから４方向を考えて、最大ケースで 4 × 4 × 4 × 4 × 4 = 1024通りの探索を行いました。
実際には上記のようなケースは極めて稀で、壁があったりとかしてまぁまぁ少なくなります。
１ターン後の移動したパックの位置から、全位置について最短距離を計算。
これは多始点幅優先探索をして計算しました。
最短距離の情報から各セルに対する価値を求め、その総和を「その移動の評価値」とする
あるセルの価値を以下のように定めました。
$value = \frac{1}{距離 + 1}$
+1をしているのは、最短距離が0だとゼロ徐算をしてしまうためです。（この式は記事が進むにつれて進化していきます）これで 近くのものがより近くなったらかなり嬉しい。遠くのものがもっと遠くなっても割とどうでもいい が実現されるかなと思いました。
あとは $value$ の総和を「その移動」の評価値として、最も評価値の高い移動方法を選びます。

不完全情報について

今回のゲームは不完全情報ゲームで、手に入る情報は自パックの視界にあるもののみです。
これをどうしようか迷った結果、各セルには以下の３種類の状態がある と定義することにしました。

実在セル
目に見えるペレットがあるセルです。
空セル
ペレットがないとわかったセルです。
一度取られたペレットが復活することはないため、一度空セルになったセルはずっと空セルです。
不定セル
ペレットがあるかもしれないし、ないかもしれないセルです。かっこいいので不定セルと呼んでました。
この不定セルの価値をいかに正しく見積もるのかが１つのカギだと考えました。

では不定セルの価値をどう見積もるか、ですがゲーム開始直後はだいたいどの不定セルにもペレットがあるし、逆にゲーム終盤はほとんどの不定セルにペレットがない な、と思いました。
そういう訳で不定セルの価値を以下のように定めることにしました。実在セルの何%の価値があるか、とも言い換えられます。
$(不定セルの状態価値)= \frac{残ペレット数}{最初にあったペレット数}$
これらは入力から与えられる得点情報から計算できます。スーパーペレットは１０点ですが、丁寧に取られているかを追うと残りペレット数が計算できます。

そういう訳で、各セルに対する評価式は以下のようになりました。
$value = \frac{1}{距離 + 1} × (セルの状態価値)$

実在セルの状態価値は１として、空セルの状態価値は０として扱います。

スーパーペレットについて

これは間違いなくとるべきです。
なので、最優先でスーパーペレットを取りに動いてくれるよう、評価式を以下のように修正しました。

$value = \frac{1}{距離 + 1} × (セルの状態価値) × （スーパーペレット補正）$

補正値は100とかだった気がします。
さらに、ライバルの方が近いスーパーペレットについては、最初から空セルとして扱うことにしました。
強い人がスーパーペレットを取り逃がすことはないだろう & スーパーペレットを取り逃がすような人には結局自分のスーパーペレット分勝つからいいや
という気持ちです。

じゃんけんについて

見えている相手のパックから周囲１マス（SPEED状態なら２マス）を「（グー・チョキ・パー）で殴られるゾーン」して、近づかないようにしました。
相手パックがアビリティを使える状態なら、そのマスを「全部の手で殴られるマス」にしたんですが、なんか弱くなりました（なんでだろう。どこかバグってるのかな）

また自分のパックについては、「あ、このままだとどうやっても死ぬわ」という時に、アビリティがあれば相手パックを狩る手にSWITCH、というようにしました。SWITCH使い始めたのはGoldからですね。

SPEEDについて

大事です。打っても死なない時にはガンガン打っていきました。厳密には損することもある（スーパーペレットを挟んでいる時とか）んですが、めんどくさいので処理しませんでした。
SPEEDを使い始めたのはSilverからでした（は？）

で、ここまででGold80位ぐらいでした。
最後の工夫として、以下を取り入れました。

相手の方が距離が近いセルについては、価値を大きく落とす

負けたゲームを眺めていると、相手の後ろを丁寧についていって「ペレットないよぉ。。。」をしている試合がたくさんありました。
なので、見えている相手パックから多始点幅優先探索を行って、相手の方が距離が近いセルについては価値を落とすことにしました。
この工夫を取り入れて、評価式は最終的に以下のようになりました。

$value = \frac{1}{距離 + 1} × (セルの状態価値) × （スーパーペレット補正）×（相手が取っちゃいそう補整）$ 相手が取っちゃいそう補正は最初は0.1にしてたんですが、Gold10位とかで停滞したので、0.2にしたらLegendにいきました。
ほんとはこれも距離に応じて「相手がとりそうな確率」を出すべきなんでしょうが、時間ギリギリだったのでできませんでした。（あと面倒）

DEADについて

DEADはとりのぞきました。

感想

平日５時間、休日１２時間ぐらいやりました。５日目まで進捗０だったので死んでました。まじでWood１で終わるかと思った。
Pythonで書いたらTLEしたので泣きながらC++に書き直しました。
C++で書いてもTLEしやがるので頑張りました。

Legendに上がれたのは嬉しいんですが、Legend内ではボコられたので結構悔しい気持ちが残っています。次は最終日に有給を使うぜ！という気持ちになりました。

こんな調子なので楽しむ余裕などなく、ほとんどの時間を苦しい思いをしながらやってました。
７日目ぐらいからようやく楽しくなってくれてよかったです。
（もちろん思い出として振り返るとYeah~~って感じです。よくがんばったねME.）

次回のコンテストも必ず参加します！もっといい成績とってやるぞ〜〜〜〜〜〜〜〜〜〜！！！ではではお疲れ様でした！！！！

戒め

体調管理は大事です。本当に大事。次回は気をつけてください。

あっとより

2020-06-07

CODE FESTIVAL 2014 Easy C - 身体バランス

競プロ

問題原文

atcoder.jp

解法

$A→ x → B$ みたいなのがあるときには、真ん中を軸として考えると嬉しいことが多いんですが、今回は真ん中を全部調べる必要があります。

ということでダイクストラで $S$ からの最短距離と $T$ からの最短距離を調べておけば、各 $x$ について高速に判定ができます。

連結グラフではないのでちょっと注意。

実装

N, M = map(int, input().split())
S, T = map(int, input().split())
S, T = S - 1, T - 1
G = [[] for _ in range(N)]
for i in range(M):
    x, y, d = map(int, input().split())
    x, y = x - 1, y - 1
    G[x].append((y, d))
    G[y].append((x, d))


def dijkstra(graph, start, inf=float('inf')):
    import heapq
    n = len(graph)
    distances = [inf] * n
    distances[start] = 0
    visited = [False] * n

    # 距離・頂点
    hq = [(0, start)]
    while hq:
        dist, fr = heapq.heappop(hq)
        visited[fr] = True

        for to, cost in graph[fr]:
            new_dist = distances[fr] + cost
            if (visited[to]) or (distances[to] <= new_dist):
                continue

            distances[to] = new_dist
            heapq.heappush(hq, (new_dist, to))

    return distances


S_distances = dijkstra(G, S)
T_distances = dijkstra(G, T)
for u in range(N):
    if S_distances[u] == T_distances[u] and S_distances[u] != float('inf'):
        print(u + 1)
        break
else:
    print(-1)

感想

いつかPASTで出そうだなぁ（こなみ）

2020-06-07

第三回 PAST M - 行商計画問題

競プロ

問題原文

atcoder.jp

解法

$K$ の制約が小さいのがポイント。
訪れたい $K$ 個の頂点について、全点間最短距離は $T_1, T_2... T_K$ からそれぞれBFSをすれば求められる。

これで巡回セールスマンっぽい問題になったので、あとはbitDPで解ける。

実装

枝刈りしてないけど。。。まぁいいか！

from collections import deque
N, M = map(int, input().split())
G = [[] for _ in range(N)]
for i in range(M):
    u, v = map(int, input().split())
    u, v = u - 1, v - 1
    G[u].append(v)
    G[v].append(u)

S = int(input())
S -= 1
K = int(input())
T = list(map(lambda x: int(x) - 1, input().split()))
T = [S] + T
K += 1
A = [[float('inf')] * K for _ in range(K)]

def bfs(sn):
    distances = [float('inf')] * N
    distances[sn] = 0
    que = deque([sn])

    while que:
        n = que.pop()
        for to in G[n]:
            if distances[to] != float('inf'):
                continue
            distances[to] = distances[n] + 1
            que.appendleft(to)

    return distances

for i, sn in enumerate(T):
    distances = bfs(sn)
    for j, to in enumerate(T):
        A[i][j] = distances[to]

# dp[bs][t] := 集合bsをすでに訪れていて、最後にtを訪れているような場合の最小コスト
dp = [[float('inf')] * K for _ in range(1 << K)]
dp[1][0] = 0
for bs in range(1, 1 << K):
    for t in range(K):
        for nx in range(K):
            dp[bs | (1 << t)][nx] = min(dp[bs | (1 << t)][nx], dp[bs][t] + A[t][nx])

print(min(dp[-1]))

感想

スーパーマーケットの方が普通に苦手だった説がある。
後半３問をチャレンジ枠と捉えた時点で私は敗北していたのだ。。。

2020-06-06

CODE FESTIVAL 2015 あさぷろ Middle B - ヘイホー君と削除

競プロ

問題原文

atcoder.jp

解法

２つの文字列 $L$ と $R$ があったとして、削除のみを用いて $L = R$ にする場合、 $L$ と $R$ の最長共通部分列を残すのが最適。
よって $S$ をどこかで二分し、それらを $L$ , $R$ として最長共通部分列長を計算すればよい。
全ての切り分け方を試して、最小値が答え。

実装

N = int(input())
S = input()

ans = float('inf')
for m in range(N + 1):
    L, R = S[:m], S[m:]
    dp = [[0] * (len(R) + 1) for _ in range(len(L) + 1)]
    for l, ls in enumerate(L, start=1):
        for r, rs in enumerate(R, start=1):
            if ls == rs:
                dp[l][r] = dp[l - 1][r - 1] + 1
            else:
                dp[l][r] = max(dp[l - 1][r], dp[l][r - 1])
    ans = min(ans, N - 2 * dp[-1][-1])

print(ans)

感想

えっ、難しかったえっ
個人的には次の一次元オセロの倍ぐらい難しかったです。。。解けてよかった

2020-06-04

CODE FESTIVAL 2015 あさぷろ Hard A - 一次元オセロ

競プロ

問題原文

atcoder.jp

解法

$N$ は奇数 と制約にあるので、白, 黒, 白, 黒, 白みたいになっている。
おける黒は両端のどちらかで、どちらかに黒を置いた後、白の選択は一意に定まる。

これで

左端に黒を置いた時にひっくり返す枚数（次の白の手番まで考慮）
右端に黒を置いた時にひっくり返す枚数（次の白の手番まで考慮）

がわかる。

で、実は次の一手（白の手番まで考えると二手）までで、ひっくり返す枚数がより小さい方に置く貪欲法で解ける。
二手後の選んだ方に出現する白の連続は、当然今見ている白の連続より長くなるのでそれはそうという感じ。
ざっくりいうと、あえて損して次にそのおかげで得するようなことがない。

実装

なんだこのくそこーどはぁ！！！

from collections import deque
N = int(input())
A = list(map(int, input().split()))
que = deque(A)

ans = 0
while len(que) > 1:
    l_cost = 2 * que[0] + que[1] + 1
    r_cost = 2 * que[-1] + que[-2] + 1

    if l_cost < r_cost:
        ans += l_cost
        append_l = que[0] + que[1] + que[2] + 2
        que.popleft()
        que.popleft()
        que.popleft()
        que.appendleft(append_l)
    else:
        ans += r_cost
        append_r = que[-1] + que[-2] + que[-3] + 2
        que.pop()
        que.pop()
        que.pop()
        que.append(append_r)

print(ans)

感想

推定diff1600弱らしい〜
令和ABC-Dに置かれて3000人解きそう。（個人の感想です）

2020-06-02

ABC169 F - Knapsack for All Subsets

競プロ

問題原文

atcoder.jp

解法

$A$ → $A$ に部分集合 $T$ → $T$ の部分集合 $U$ みたいな構造をしている。

$dp[i\rbrack[j\rbrack :=$ $i$ 番目までみて $U$ として選んだものの総和が $S$ になるような通り数
とする。

ある $A_i$ に着目した時、遷移先は

$T$ として選ばない
$T$ としては選ぶが $U$ としては選ばない
$U$ として選ぶ

の３つがある。

実装

N, S = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353

dp = [[0] * (S + 1) for _ in range(N + 1)]
dp[0][0] = 1

for i, a in enumerate(A):
    for j in range(S + 1):
        dp[i + 1][j] += 2 * dp[i][j]
        dp[i + 1][j] %= MOD
        if j + a <= S:
            dp[i + 1][j + a] += dp[i][j]
            dp[i + 1][j + a] %= MOD

print(dp[-1][-1] % MOD)

感想

解けなかったけど大変ためになった。すごい典型っぽい。
なんだろう、新しい視点を手に入れた感じ。
成長した〜wって感じがする（単純）