ABC165

五本指ソックスばかり履いてます。

ko_ya346です。

ABC165をに挑戦したのでその記録です。

というのも、先日行われたABC171の結果が振るわず（ABDの3完）、原因を色々考えたのですが、

①精進に対する集中力が足りない

②古い問題ばっかり解いてた

の2点が大きいかなと思いました（数学センスが足りないことを除く）。

というわけでABC165が不参加だったため手付かずで残っていたので、バチャ形式で挑戦してみました。

感想

このセットむずくね？

A問題でfor文使うの久しぶりだわ。

A問題

atcoder.jp

range(a, b+1)をfor文で回し、Kの倍数があるかチェック

K = int(input())
a,b=map(int, input().split())

f = 0
for i in range(a, b+1):
    if ((i)%K ==0):
        f = 1

if f:
    print("OK")
else:
    print("NG")

B問題

atcoder.jp

小数でそのまま扱うと誤差が発生する場合があるので変換する

バチャ中には最後のケースが通せませんでした。小数の扱いはまだ慣れない…

maspyさんのコードがすごく参考になりました。

年数をitertools.countで数えている点がオシャレ

maspypy.com

C問題

かなりの何問。水色diff近くあります。

制約を見て全ての配列Aを全探索することを考えました。

9乗ループ（！？）で通しましたが、itertools.combinations_with_replacementを使用するのがスマートな解法です。コンテスト後に存在を知りました。

競プロを通して新しい知識を得る瞬間が一番楽しいですね！脳汁ドバドバ出ました！

from itertools import combinations_with_replacement

N, M, Q = map(int, input().split())

A = [list(map(int, input().split())) for _ in range(Q)]

ans = 0
for i in combinations_with_replacement(range(1, M+1), N):
    tmp = 0
    for a, b, c, d in A:
        if i[b-1] - i[a-1] == c:
            tmp += d
    ans = max(ans, tmp)
print(ans)

D問題

atcoder.jp

最近はD問題に数学知識が要求される問題が多いように感じます。

基本的に過去問を解くだけでは不十分で、その性質をきちんと理解し、正しく式変形できることが求められています。

僕が一番苦手なタイプの問題です…バチャ中も解けませんでした。

解説放送でめちゃ丁寧に式変形について説明があるので、そちらを参考にした方がよいです（ただの手抜き）。すぬけさんいつもありがとうございます。。。

from math import floor

a, b, n = map(int, input().split())
# a, b, n = 10, 8, 10

num = min(b-1, n)
#n以下で最大のbの倍数
print(floor(a*num/b) - a*floor(num/b))

E問題以降はさらっと解説読んだだけで実装まではしていないです。

感想

短時間で集中して取り組めたのでバチャの効率は良さそうに感じます。

また、最近の傾向の問題に触れて自分に足りないスキルが浮き彫りになって良かったです。

早く緑になれるように頑張ります！グリーングリーン。あ、間違えちゃった…。わたし、まだ新米なのよ。

ABC040D

最近キックボクシングジムに通い始めました。

ko_ya346です。

Atcoder過去問埋めをやっていきます。

問題はこちら。

atcoder.jp

何を考えた？

道で繋がっている都市の個数を数えるのでUnionFind木を使えば楽そうです。

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

次は入力

道とクエリは新しい順にソートします。

クエリ順に出力する必要があるので、クエリのindexを記録しています（[i]のとこ）。

N, M = map(int, input().split())
road = sorted([list(map(int, input().split())) for _ in range(M)], key=lambda x:x[2], reverse=True)
Q = int(input())

uf = UnionFind(N)
ans = [None]*Q
query = sorted([list(map(int, input().split())) + [i] for i in range(Q)], key=lambda x:x[1], reverse=True)

UnionFind木は簡単に辺を増やせますが辺を削除することは難しいらしいです。

なのでqueryの住民が要求する橋を新しい順にソートし、その住民を満足させる辺を足すことにします。

同じ道を何度も足すのは無駄なので、前回チェックしたindexをr_indに保持し、クエリが始まる度に続きからチェックするようにします。

毎回道を全てチェックするとTLEになるのでご注意ください（3敗）

住民が満足する道を全て足したところで、その住民がいる地点のグループ数を計算します。

#前回追加したところまでのindexを保持して
#木の追加に重複がないようにする
r_ind = 0
for v, w, i in query:
    while r_ind < M and road[r_ind][2] > w:
        a, b, y = road[r_ind]
        uf.union(a-1, b-1)
        r_ind += 1
    ans[i] = uf.size(v-1)

print(*ans, sep="\n")

全体の解法はこちら

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

N, M = map(int, input().split())
road = sorted([list(map(int, input().split())) for _ in range(M)], key=lambda x:x[2], reverse=True)
Q = int(input())

uf = UnionFind(N)
ans = [None]*Q
query = sorted([list(map(int, input().split())) + [i] for i in range(Q)], key=lambda x:x[1], reverse=True)
# print(query)

#前回追加したところまでのindexを保持して
#木の追加に重複がないようにする
r_ind = 0
for v, w, i in query:
    while r_ind < M and road[r_ind][2] > w:
        a, b, y = road[r_ind]
        uf.union(a-1, b-1)
        r_ind += 1
    ans[i] = uf.size(v-1)

print(*ans, sep="\n")

UnionFind木の構造は複雑ですが、使いこなせるとすごく便利ですね！

ドグマブレードシミュレーターに挑戦！（ダメージ理論値も）

導入

ドグマブレードとは2008年頃に流行した

先行1キルを目的としたデッキ。

yugioh-wiki.net

遊戯王史上最も回すのが難しいとか、様々なギミックを活用してデッキをぶん回すことから最も美しいデッキとか言われてます。

僕も現役の時は一度は組んでみたい憧れのデッキでした（使用するカードが当時は軒並み高価）。

そんなデッキがつい最近、シミュレーターで遊べるようになりました！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

tsd0313.github.io

クリア方法

次の相手ターンのスタンバイフェイズに8000ダメージを叩き込めればクリアです。

そのためには

①ドグマガイ＋マジエク1枚（墓地魔法20枚以上）

②マジエク2枚（墓地魔法20枚以上）

が必要です。

頑張ってデッキを掘って行きましょう。

デッキ構成はこんな感じ

基本の動き

基本的にはデッキに干渉する墓地やドローを積極的に行っていきます。

序盤はモンスターゲートと名推理で墓地肥やししていき、ディスクガイやクライス、トレインやディステニードローを駆使してデッキを減らします。

手札が少ないうちは動く手段が限られるので、うまく次の行動に繋げられる動きを心がけましょう。

適宜必要パーツを回収しつつ、次元融合でサイヴァリ含めたモンスを大量展開できるようになれば8000ダメは安定してきます。

ちなみに名推理は8>6>4>1の順に指名し、こちらの公開情報によって指名が変化するようです（墓地に混黒がいると8は指名してこない）

あと召喚権を使うかどうかも結構迷います。アームズホールで早すぎた埋葬を引っ張ってディスクガイorクライスの2ドローの動きはめちゃくちゃ強いですが、召喚権を使わずにモンスターを並べる必要があるので運も必要になってきます。

詰将棋が得意な人は割と簡単に動かせるかもしれません。

上手い人は8割くらい成功するようです（僕は2割…）

18600ダメージを叩き込む！！！

デッキに魔法カード29枚、マジエク2枚、ドグマガイは3枚含まれているので、最大ダメージは

8000/2+8000/2²+8000/2³+29×200×2 = 18600

です。

これを叩き出すためのコツを列挙しておきます。

①除外するのはドグマガイ以外のモンスのみ

除外ゾーンにあるドグマガイ、マジエク、魔法カードを回収する術はありません。

つまり除外できるモンスはエアーマン、ディスクガイ、クライス、混黒、サイバーヴァリーの5枚のみ。

サイバーヴァリーの手札除外コストが何枚必要か常に気を配らなければいけません。

ドグマガイはトレインやデステニードローの恰好のコストですが、理論値ダメを狙うのは控えたほうがいいでしょう。

②サイヴァリ混黒次元融合の無限ドローを序盤に決める

魔力倹約術が発動済み、サイバーヴァリーと混黒が除外ゾーン、次元融合が手札にある場合

１．次元融合を発動、サイバーヴァリーと混黒が帰還

２．混黒効果で次元融合を回収

３．サイバーヴァリー効果で混黒を除外して2ドロー

を繰り返すことでデッキ全部手札にすることが出来ます。

③ドグマガイのリリース要員は次元融合で並べる！

②のループ中にエアーマン、ディスクガイを呼び出せば簡単にドグマガイを並べることも可能です。

エアーマン、ディスクガイはモンゲコストなどで墓地に送り、フェニブレの墓地効果で除外しましょう。

エアーマンはドグマガイをサーチできるので繰り返し特殊能力出来れば強力です。

④魔法カードを全部墓地送りに

ドグマガイ3体、マジエク2枚を回収した後も注意が必要です。

手札の魔法カードを始末するには

１．魔法石の採掘で魔法石の採掘を回収し、コストで2枚送り

２．エアーマン効果、クライス効果で破壊

３．DDRのコスト

が主な手段です。

発動済みの魔力倹約術は２．の方法もしくはハリケーンで回収可能です。うまく調整して手札を減らしましょう。

おわりに、参考リンクなど

こう考えると全てのカードが活躍してますね…さすがに美しい…

うまく行けば20回に1回くらいは成功すると思います。

たくさんプレイしてドグマブレードの構築の美しさに酔いしれてください！！

参考リンク

作者は@toride0313さん。

解説はこちらを参考

you396.hatenadiary.jp