2020-11-02

ABC181 F - Silver Woods

競プロ

昨日のABCはEまでの5完！やったぜ！

コンテスト本番中はわからなかったFを復習したのでまとめる．

問題概要

下の図のように， $y = 100$ から $y = -100$ の直線に挟まれた通路にいくつか釘（赤い点で表す）が打たれている．円を $(-10^9,0)$ から $(10^9,0)$ まで動かすとき，円の内部に釘や通路の境界が入らないようにしたい．円の半径の最大値を求めよ． f:id:ntk_ta01:20201102142635j:plain

観察

ある2点，もしくは点と直線の距離より円の直径が大きいと，円が通れない．

f:id:ntk_ta01:20201102143252j:plain

解法

全点対間距離と，それぞれの点とそれぞれの直線の距離をすべて求めておく．2点，もしくは点と直線のペアを，その距離でソートしておく．そして，距離が小さい2点，もしくは点と直線から順に，線を結ぶとする．線を結んだ間は，円が通れないとする． $y = 100$ の直線と $y = -100$ の直線が繋がってしまうときの2点，もしくは点と直線の距離が，求める円の直径の最大値であり，これの半分が求めたい半径である．

上の直線と下の直線が，繋がっていなければ円が通れる．

f:id:ntk_ta01:20201102142645j:plain

繋がってしまうと通れなくなる．このときの下図，緑の線で表される距離が，通れる円の直径の最大値．

f:id:ntk_ta01:20201102142653j:plain

線を結ぶ，というのは直線と釘を無向グラフの頂点とみなし，union-findで管理する．上と下の直線が連結になったときの距離が，求める直径の最大値．下のコードでは，ソートを整数で行うほうがいいかも？と思って，距離を二乗で管理している．

コード

class UnionFind:
    def __init__(self, N):
        self.par = [i for i in range(N)]
        self.size = [1 for i in range(N)]

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            self.size[x] = self.size[self.par[x]]
            return self.par[x]

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

    def merge(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.size[x] += self.size[y]
        self.par[y] = x

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


def main():
    from math import sqrt
    import sys
    readline = sys.stdin.buffer.readline
    N = int(readline())
    X = []
    Y = []
    for _ in range(N):
        x, y = (int(i) for i in readline().split())
        X.append(x)
        Y.append(y)

    # 頂点数 N + 2 釘と直線2本
    dist = []
    for i in range(N):
        for j in range(i+1, N):
            d = (X[i] - X[j])**2 + (Y[i] - Y[j])**2
            dist.append((d, i*(N+2) + j))

        # y = 100 との距離 頂点番号N
        d = abs(Y[i] - 100)
        dist.append((d**2, i*(N+2) + N))
        # y = -100 との距離 頂点番号N+1
        d = abs(Y[i] + 100)
        dist.append((d**2, i*(N+2) + N + 1))

    V = N + 2

    dist.sort()
    uf = UnionFind(V)
    ans = -1
    for d, pair in dist:
        u, v = pair // V, pair % V
        uf.merge(u, v)
        if uf.same(N, N + 1):
            ans = sqrt(d) / 2
            break
    print(ans)


if __name__ == '__main__':
    main()

提出コードへのリンク

tatyamさんの公式解説がきれいにまとまっていたので，整理してみたら新しいこと何も言ってないかも．直径や直径の二乗を二分探索してもいいみたい！

コード

class UnionFind:
    def __init__(self, N):
        self.par = [i for i in range(N)]
        self.size = [1 for i in range(N)]

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            self.size[x] = self.size[self.par[x]]
            return self.par[x]

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

    def merge(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.size[x] += self.size[y]
        self.par[y] = x

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


def is_ok(N, V, dist, L):
    uf = UnionFind(V)
    for d, pair in dist:
        u, v = pair // V, pair % V
        if L > d:
            uf.merge(u, v)
    return not uf.same(N, N + 1)


def binary_search(N, V, dist):
    ng = 40000
    ok = 1
    while abs(ok - ng) > 1:
        mid = ng + (ok - ng) // 2
        if is_ok(N, V, dist, mid):
            ok = mid
        else:
            ng = mid
    return ok


def main():
    from math import sqrt
    import sys
    readline = sys.stdin.buffer.readline
    N = int(readline())
    X = []
    Y = []
    for _ in range(N):
        x, y = (int(i) for i in readline().split())
        X.append(x)
        Y.append(y)

    # 頂点数 N + 2 釘と直線2本
    dist = []
    for i in range(N):
        for j in range(i+1, N):
            d = (X[i] - X[j])**2 + (Y[i] - Y[j])**2
            dist.append((d, i*(N+2) + j))

        # y = 100 との距離 頂点番号N
        d = abs(Y[i] - 100)
        dist.append((d**2, i*(N+2) + N))
        # y = -100 との距離 頂点番号N+1
        d = abs(Y[i] + 100)
        dist.append((d**2, i*(N+2) + N + 1))

    V = N + 2

    dist.sort()
    # 直径の二乗を二分探索
    ans = sqrt(binary_search(N, V, dist)) / 2
    print(ans)


if __name__ == '__main__':
    main()

提出コードへのリンク

その他，コンテスト終了後のTLで見かけた類題や発想が近い？らしい問題．グラフにいい感じに帰着させられるようになりたい～．

codeforces.com atcoder.jp atcoder.jp

2020-10-15

AtCoder水色になりました！

競プロ

色変記事のいつもの画像からです． f:id:ntk_ta01:20201012214615p:plain f:id:ntk_ta01:20201012214627p:plain f:id:ntk_ta01:20201012214635p:plain f:id:ntk_ta01:20201012214643p:plain f:id:ntk_ta01:20201012214650p:plain f:id:ntk_ta01:20201012214656p:plain

水色を目指している人が読んでくれることを考えて，オススメの精進方法などを多く書いています．

一番読んでくれるのはTwitterのフォロワーの方々だと思っていて，自分のこれまでの苦労や今後の目標についても書いています．興味のあるところだけでも，読んでもらえたら嬉しいです．

AtCoder緑の振り返り
オススメ色変記事
バチャのススメ
解説ツイート、記事執筆のススメ
今後の目標

AtCoder緑の振り返り

緑の時期、9か月！今年の1月にAtCoder緑になりました．そこから競プロerと繋がるためにTwitterを始め，精進してきました．

していたこと

コンテストに出る

ABC級は必ず出るようにしていました．ARC級企業コンやAGCは出ていません．PAST無料回やヒューリスティックスコン，日本橋ハーフマラソンやChokudai Contest辺りには出ていました．やっぱりコンテストに出るのが一番の精進です．AGCなどは，対象が自分向けでないと感じて出るのをやめていました（それこそAGCはRated対象が1200~に途中で変わりましたし）．

またCodeForcesやTopCoder SRM，yukicoderなんかにもときどき参加していました．こどふぉのレートの増減に慣れると，AtCoderのレートの増減は小さく感じるようになったりならなかったりします．

f:id:ntk_ta01:20201015194021p:plain

バチャ

たくさんバチャをしました．時期によって，やってるバチャが移り変わりました．

2月から5月 あさかつよるかつ

AtCoder Problemsで開催されている（されていた）あさかつとよるかつに取り組んでいました（僕は主催者ではありません）．このぐらいの時期は生活習慣がすごいよくて，毎日朝7時半からバチャをしていました．よるかつは途中から始まったのですが，毎日両方に取り組んでいる時期がありました．生活習慣の鬼か？今は厳しい…

f:id:ntk_ta01:20201015185506p:plain

2月頭はあさかつの参加者が4人くらいだったのですが，少しずつ参加者が増えていって，一番多いときは100人近くいました．バチャによく参加している人（特にレートが近い人など）を意識しながら，とても楽しく精進をしていました．バチャ参加者をフォローしていたらTwitterのFFも増え，競プロerとの繋がりも増えていました（ありがたかったです）．

あさかつのおかげで，緑になる前よりもだいぶ早く簡単な問題が解けるようになりました．またあさかつで解けずに一度解説ACした問題が，しばらくすると再びあさかつ出題されることがあって，それを解けたりすると成長を感じていました．この頃はレートも単調増加だったので，楽しさしかありませんでした．

7月末と，8月末くらいから最近 こどふぉバチャ

Twitterでこどふぉバチャの募集を見て，僕も参加し始めました．数人で毎日やっているところにときどき参加する感じでしたが，初見の問題をバチャ形式で解くことで実力の伸びを感じてました．あとTwitterを見返したら4月あたりもちまちまこどふぉバチャをしていました．

こどふぉ，最初使い始めるまで未知のものという感じがして近寄りがたかったんですが，最近は仲良くなれた気がします（雰囲気をつかんだということです）．

○○埋め

緑diffや300点以下を埋めていました．埋めるぞ！という気持ちになっている期間はコレに集中できるのでいいですね．

そしてそして！緑diff討伐完了！！！！いえーい！！！！！ pic.twitter.com/wTvk1kspjo
— ntk (@ntk_ta01) 2020年5月29日

AtCoder Scoresで300点以下やっと埋められた！ pic.twitter.com/aiIuDxrApp
— ntk (@ntk_ta01) 2020年7月24日

きつかったとき

ABC166からABC170のレート単調減少streak

5回のコンテストでレートが109下がっていた時期です．~~（ん、こどふぉの1回の減少より少ないのでは？）~~

ntk_ta01さんのAtCoder Beginner Contest 170での成績：3066位
パフォーマンス：973相当
レーティング：1061→1052 (-9) :(#AtCoder #ABC170 https://t.co/yY0EPdkRaf

レート単調減少streak5、呪いにでもかかったのか？
— ntk (@ntk_ta01) 2020年6月14日

f:id:ntk_ta01:20201015200613p:plain

茶パフォの回はどちらも茶diffを落とした回です．

レートが落ちているところにさらに茶パフォを出したときは精進のやる気も出ず，AtCoder ProblemsのHeatmapも色がついていません．

f:id:ntk_ta01:20201015201652p:plain

Twitterを見返したら，そういえばこんな感じだったなあと思い出します．

最近めちゃくちゃこれだ… https://t.co/wsmNop56MQ
— ntk (@ntk_ta01) 2020年6月13日

こういうときは，いったん休憩するのもアリだと思います．

ただコンテストには出続けました．すると，ABC171で早解き5完青パフォを出せたのでメンタルが回復しました．

ntk_ta01さんのAtCoder Beginner Contest 171での成績：738位
パフォーマンス：1678相当
レーティング：1052→1133 (+81) :)#AtCoder #ABC171 https://t.co/nMigoGjPre
さようならレート単調減少streak！ありがとう青パフォ！！！！！！！！ pic.twitter.com/LNvCpDROS5
— ntk (@ntk_ta01) 2020年6月21日

そうしてまた精進をし始めたんですよね．7月末に300点以下を埋めたりTopCoderSRMで青になれたり，その後もそれなりに調子がいいつもりでした．しかし…

ABC174での2完

お疲れさまでした…2完…？もうなにもわからない……… pic.twitter.com/qivQ38vixg
— ntk (@ntk_ta01) 2020年8月2日

レートも53持っていかれて，このときが一番メンタルもきつかったです．

この時期になると，春ぐらいに一緒にバチャをしていた多くの人たちはみんな色変をしていました．後から始めた人に抜かれることも頻繁にありました．

数か月前に同色だった人はみんな水色になったなあ…と順位表を見ているとなお実感する…
— ntk (@ntk_ta01) 2020年7月25日

水色になれたとき

それでも何かトピックを決めて（bit DP をやるとか）勉強したり，こどふぉバチャに参加したりと精進をしていました．Highest-100でも気にしないことが大切です（後に書きますがTERRYさんの記事を読んで，9月くらいにはそれ以前と心構えが変わったりしていました）．

そうして精進してコンテストに出ていたら，ARC104で自身の最高パフォが出て，一気にHighestまで来ました．

ARC最高ー！！！！！！！！！！！！！！！ABC3完！！！！！！！！！！！！！！ pic.twitter.com/w8dLb4AB8D
— ntk (@ntk_ta01) 2020年10月3日

Highest！！！！！！！！

ntk_ta01さんのAtCoder Regular Contest 104での成績：516位
パフォーマンス：1880相当
レーティング：1077→1187 (+110) :)
Highestを更新しました！#AtCoder #ARC104 https://t.co/po9lx4qkdF pic.twitter.com/KSMwlsHB15
— ntk (@ntk_ta01) 2020年10月3日

今度こそ，水色になる！！！そう決めて10月の頭は気合を入れて精進をし，ARC105でなんとか，なんとか水色になることができました．

夢みたいにきれいで泣けちゃうな…ありがとうございます！AtCoder水色になりました！

ntk_ta01さんのAtCoder Regular Contest 105での成績：791位
パフォーマンス：1482相当
レーティング：1193→1226 (+33) :)
Highestを更新し、4 級になりました！#AtCoder #ARC105 https://t.co/fHJRzW54Ab pic.twitter.com/wzQzjvY1DJ
— ntk (@ntk_ta01) 2020年10月11日

頑張れたのは応援してくれたフォロワーの方や，バチャを一緒にしているフォロワーの方のおかげです．本当にありがとうございました．ここでまたレート-50などをしていたら，戻ってこれるかわからなかったです（最後のARCで早解きに失敗していたらあり得た数値）．ここで水色になれてよかったです……．

この後は，精進方針の参考，メンタルの管理やモチベの維持に役立った色変記事を紹介したり，こどふぉバチャのやり方などを書いていきます．

オススメ色変記事

pitsuさんの入水記事

やったこと，のところが簡潔です．これをやると水色になれると思います．いや，精選100問をすべてやった上で400点以下を埋めDiv. 3をすべてやる，はすごすぎて参考にならないかもしれませんが…（特に400以下を埋めるが本当にすごいです，300以下を埋めたときに実感しました）．でもここらへんをやるといいんだろうな～ということがまとまっているので参考にするといいと思います．Div. 3バチャはとてもいいです（やり方は下の方に書いておきます）．

精進については，色変記事ではないですが競プロフレンズさんの記事も読んで自分なりの精進方針を決めるといいと思います．僕は解説ACもそこそこ、写経ACもときどきします．解き直しのような復習はバチャが中心です．pitsuさんの色変記事は緑のときと青のときもすぐ見られるので，そちらもオススメです．

TERRYさんの入青記事

参考になることがたくさん書いてあるのですが，中でも心構えのところがすごいタメになります．僕はなりました．コンテストとレートへの向き合い方が変わります．

バチャのススメ

バーチャルコンテスト（略して，バチャ）をするという精進方法があります．模擬コンテストをすることです．緑直前の時期も大学の同期とよくやっていました．が，緑になってからはその数倍くらいたくさんバチャをやりました．とても好きな精進方法です．初めに断っておくと，人間には向き不向きがあるのでバチャが好みの精進方法でない人もいます．そうだとしても自分なりの精進方法を見つければいいと思います．

ただ僕はバチャ精進がレートにだいぶ貢献しました．ここではバチャの利点や，CodeForcesでのバチャのやり方を書いておきたいと思います．

バチャの利点：フォロワーとの繋がりができる

競プロは個人でやることがほとんどです．ABCだけ参加している，過去問を淡々と埋めている，のような状況だとあまり他の競プロerと交流する機会はありません．しかしバチャに参加すると，その機会が生まれます．バチャの順位表でよく見る人を意識したり，結果をツイートし合ったり，こどふぉならフレンド登録もし合うなどの機会です．僕も2月くらいに他の競プロerの開催するバチャに初めて参加しましたが，そこから交流する人が増えていきました．

バチャの紹介：定期的に開催されているバチャ

ここで紹介するのは2020/10/14時点で開催されているフォロワー主催のバチャです．他にも建っているバチャはAtCocder Problemsで確認できますし，自分でAtCoder Problemsでバチャを建ててもいいと思います（建て方を知りたい人は，AtCoder Problems の使い方，という僕の記事などを読んでみてください）．人を集めたいなら定期的に開催して，それこそTwitterで並走者を募集するといいです．

くじかつ¹

AtCoder Problemsで開催されています．毎日21:00 - 22:40．NORMALとANOTHERがあって，それぞれ問題の難易度傾斜が違います．詳しくは，Q&Aを見るといいです．TERRYさん主催です．

あさかつ²

AtCoder Problemsで開催されています．毎日07:30 - 08:30．難易度傾斜はよるかつNORMALと同じです．タキガワくん主催です．

こどふぉバチャ

Twitterでここ1，2か月頻繁に開催されているDiv. 3，Div. 2バチャです．コンテストがない日の20:00～や21:00～に開催されています．えすえふさん主催です．募集ツイートは毎日お昼ごろに見かけます．Twitterで”Div.2 バチャ”と検索すると出てくると思います．

Morningforces

Twitterのハッシュタグ#Morningforcesでバチャ募集や解法ツイートを見ることができます．毎朝07:30～に開催されています．タイヨウさん主催です．僕はまだ未参加ですが，いずれ参加したい…．

人が建てているバチャに参加するのは，すでに述べたように競プロerとのつながりができます．ぜひそこからフォローしに行ってもいいです．さらに解法ツイートや解法記事を書いてくれる方もいることがあり，複数人でのバチャは本当にオススメです（いつも解法ツイートをしてくれる方に感謝しています）．

こどふぉバチャのやり方と役立ちサイト

CodeForces（こどふぉ、とここでは略します）というコンテストサイトがあります．ここではどんなコンテストサイトかは詳しく説明しません（気になる人はココとかを見てください）．何回か言及していますが，こどふぉのDiv. 3バチャは非常にオススメです．アカウントを作成したらContestsからCodeforces Round #677（Div. 3）などと好きな回を選んでコンテストページを開きましょう．上で紹介したこどふぉバチャに参加したい場合は，募集ツイートにある回を選べばいいです．

f:id:ntk_ta01:20201014234658p:plain

コンテストページが開けたら，ページ右側のVirtual participationのところにあるStart virtual contestを押しましょう．すぐには始まらないので安心してください．

f:id:ntk_ta01:20201014235242p:plain

開始したい時間を選んで，Register for virtual participationを押します．これで指定時間からバチャを開始できます！誰か一緒にやりたい人がいる場合は，事前にフレンド登録しておきましょう．

HOMEやTOPのページにおいて，ちょっと下にスクロールするとFind userという欄があります．ここからフレンド登録したい相手のアカウント名を検索して，出てきたページの相手の名前の隣にある星マークを押せばフレンド登録完了です．

f:id:ntk_ta01:20201014235810p:plain

これでバチャ中にSTANDINGSのFRIEND STANDINGSから，フレンドがいる順位表を見ることができます．ぜひこの機能を使って，多くの人と並走することをオススメします．ぜひ，僕ともバチャをしましょう．

f:id:ntk_ta01:20201015000148p:plain

の

f:id:ntk_ta01:20201015000235p:plain

また，こどふぉバチャをやるにあたって，便利なサイトを二つ紹介しておきます．

Codeforces Anytime

f:id:ntk_ta01:20201015000507p:plain

バチャの結果のみからレート変動を記録できるサイトです．やっぱりレートがつくと楽しいです．バチャのみなのでかなり気楽に見れます．

contest mania

f:id:ntk_ta01:20201015001029p:plain

取り組んだコンテストなどがわかります．オススメの機能は，Usernamesのところに複数人のアカウント名を入れることで，対象の人たちがやってない回のコンテストを探せるものです．

解説ツイート、記事執筆のススメ

僕は7月くらいから解いた問題や参加したコンテストについて，ちょくちょく記事を書いていました．記事を書く一番の目的は，解いた問題の整理をすることです．解いた問題を復習し，次に解く問題に活かせることをたくさん吸収できると，競プロで強くなれると考えています．記事まで行かなくても，問題を解いた後に解法ツイートをする，などというのもいいと思います．ただ別に必ずしも記事を書かなくても，解説を読んだりしばらくしてから解き直したりすれば十分な人もいると思います．

しかし他にも記事を書く利点はあって，

その問題をより記憶できる

記事を書いた問題は，書いていない問題よりも記憶に残りやすいです．これは記事を書いた問題に似た問題が出たら，役に立つことです．

読んでくれた人から，よりよい解法を教えてもらえる/誤りを指摘してもらえる

これは読んでもらう機会があって成り立つことですが，ときどきあります．よりよい解法を教えてもらっても，誤りを指摘してもらっても，どちらでもそれを学べば自分の実力は上がります．

あと自身のためではないですが，将来同じ問題を解いてわからなかった競プロerのために記事を書いてもいいと思います．自身がつまづいた点を，同じ道を歩く人がつまづかないと嬉しいです（こういうモチベーションで環境構築記事を書いていたりします）．

また解法記事だけでなく，読んでいる方が色変したら色変記事をぜひ書いてほしいです．読みに行きます（紹介を途中でしたぐらいですから，この記事を書くにあたってもいろんな方の色変記事を読み返したんですが，いろんなことが書いてあってとても面白いです．オススメはたくさんあるのですが，scolさん，テルさん，chacoderさん，kyaさんの記事あたりは特にオススメです）．

今後の目標

まず，開発をしたいです．例えばAtCoder ProblemsにContributeするとかですね．やりたいって気持ちはずっとあるんですが，なかなか手を出せていません．来年はインターンに行けるように非競技プログラミングの実力も欲しいです．

競プロは？と言うと，AtCoder青！が果てしなく遠く感じます．しかしコンテストに参加したり気になるアルゴリズムを学んだりしつつ，まったりと1400を目指したいです（これも結構高い目標だと思っています）³．またヒューリスティックスコンテストにかなり興味があります．次の開催がいつかわからないですが，それに備える意味でも焼きなまし法などに慣れ親しみたいです．これは大学の研究がそういう感じっていうのも関連しているためですね．研究も楽しいので時間を割きたいんですが，最近は競プロばかりしていました．

Div.3 バチャをしよう！って話をこの記事で書いたのですから，それもやりたいです……あれ？結局競プロばかりしていないか？

というわけで，フォロワーの方はこれからもぜひぜひよろしくお願いします．よくやりとりする方なんかは特にこれからも仲良くしてください．

こんな長い記事を最後まで読んでくださって，ありがとうございました．

あさかつに対してよるかつじゃないのか？と思いませんか．そうです，くじかつの前にはよるかつコンテストがありました．みはいるさん主催でした．↩
あさかつには強い思い入れがあります．あさかつがあったからここまで来れました．初期はタキガワくんとポリーナくん，あとしふとさんや凸守さん，定秋さんがいましたね．それからぷちくんが参加していると，かわらさんやotamayさんが来て…そこからはドンドン人が増えていきました．懐かしいです．今見返すと，あの人がこのときにもいたのか…！みたいな驚きがあって面白いです．ちなみに他にも思い入れがあるバチャと言えば凸守さんの早解き大会ですね。楽しかったです。画像はあさかつ初参加のときのものです．↩
AtCoderの段位？で言うと，3級ですか？どこに段位の定義が載ってるかわからないので自信がないですが…．レートグラフの軸に段位も欲しいです！↩

2020-09-17

Codeforces Round #506 (Div. 3) D. Concatenated Multiples

競プロ

D. Concatenated Multiples

問題概要

正整数 $n$ ， $k$ と， $n$ 個の正整数 $a$ が与えられる． $a_i$ と $a_j$ を連結させた数のうち， $k$ で割り切れるペア $(i, j)$ の個数を答えよ．ただし $i \neq j$ ．連結させた数の例としては， $a_j = 12$ と $a_i = 654$ なら $12654$ ． $a_j = 487$ と $a_i = 3$ なら $4873$ とする．

解法パートで， $a_j$ と $a_i$ を連結させた数を $a_j a_i$ という風に書く．

解法

$a_i$ を，mod $k$ で $0$ にしたいと考える． $a_i$ に $k - a_i$ を足したら，mod $k$ で $0$ になる．正整数 $a_i$ は高々 $2 \times 10^5$ 個あるので，一つの $a_i$ に対して条件を満たす $k - a_i$ が何個あるかを高速に求めたい．

ここで， $d(a_i)$ を $a_i$ の桁数とする． $d(12) = 2$ ， $d(12345678) = 8$ と言った感じ．こうすると， $a_j$ と $a_i$ を固定し， $a_j a_i$ という連結させた数が $a_j \times 10^{d(a_i)} + a_i$ と表せる．例えば， $a_j = 57$ ， $a_i = 332$ とすると， $d(332) = 3$ であって $57332 = 57 \times 10^3 + 332$ と書ける．

上のように書いて何がうれしいかと言うと，和の前と後でバラバラにmodを取れることである．つまり， $(a_j \times 10^{d(a_i)} \% k)+ (a_i \% k)$ というように計算できる．上の例では， $k = 11$ とすると $57332 \% 11 = ( (57 \times 10^3) \% 11 + (332 \% 11) ) \% 11 = (2 + 9) \% 11 = 11 \% 11 = 0$ となる．

最初にしたかったことを思い出す．一つの $a_i$ に対して条件を満たす $k - a_i$ が何個あるかを高速に求めたい．前処理として， $(a_j \times 10^{d(a_i)} \% k)$ を取り得る $d(a_i)$ に対してすべて計算し，何個あるかカウントしておくと最初にしたかったことができる．

$d(a_i)$ が取り得る値の範囲を考える．こういうときは制約を見返すとよくて， $1 \le a_i \le 10^9$ である．したがって， $a_i$ は高々 $10$ 桁にしかならないので， $1 \le d(a_i) \le 10$ である．

このようにして各 $a_j$ に対して， $(a_j \times 10^{d(a_i)} \% k)$ を $1 \le d(a_i) \le 10$ の範囲ですべて計算してから個数カウントする前処理をした後で，各 $a_i$ ごとに $k - a_i$ の個数を足し合わせたら，答えが求まる．

TLが2secだとギリギリだったり， $(k - a_i)$ と $a_i \times 10^{d(a_i)}$ が同じになるとき（これをカウントしてしまうと $a_i$ と $a_i$ のペアを数えることになる）に注意しながら実装する．

実装

コード

// #define _GLIBCXX_DEBUG
// #pragma GCC optimize("Ofast")
#pragma GCC diagnostic ignored "-Wsign-compare"
#include <bits/stdc++.h>
// #include <atcoder/all>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define reps(i, s, n) for (int i = s; i < (int)(n); ++i)
using namespace std;
using ll = long long;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
template <class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
constexpr int INF = 1e9 + 7;
constexpr ll LINF = 1LL << 60;

int calc_digit(ll a) {
    int ret = 0;
    while (a > 0) {
        ret++;
        a /= 10;
    }
    return ret;
}

void solve() {
    ll n, k;
    cin >> n >> k;
    V<ll> A(n);
    rep(i, n) cin >> A[i];

    VV<ll> val(11, V<ll>(n));
    rep(i, n) {
        ll v = A[i];
        rep(d, 11) {
            val[d][i] = v;
            v *= 10;
            v %= k;
        }
    }
    map<ll, ll> cnt[11];
    rep(d, 11) {
        rep(i, n) { cnt[d][val[d][i]]++; }
    }
    ll ans = 0;
    rep(i, n) {
        int d = calc_digit(A[i]);
        ll need = (k - A[i] % k) % k;  // A[i] % k = 0のときがあるので，外側でも % kする
        ans += cnt[d][need];
        if (need == val[d][i]) ans--;
    }
    cout << ans << "\n";
}
int main() {
    cin.tie(nullptr);
    // ios_base::sync_with_stdio(false);
    // cout << fixed << setprecision(15);
    solve();
}

提出コードへのリンク

サンプル

# input
6 23
45 1 10 12 11 7
# output
1

以下三枚，サンプルを考えるときのメモ（手書きで読みにくかったらすみません）．

f:id:ntk_ta01:20200917101906j:plain

f:id:ntk_ta01:20200917101928j:plain

f:id:ntk_ta01:20200917101942j:plain

$1012$ だけがmod $k$ で $0$ になる．

mapのアクセスのしかたを変えると，TLEして苦戦した．メモリの局所性を感じる．あとmapを要素とした配列を初めて使った．Pythonならdictを要素としたリスト．言語をあっちこっち使うと混乱しそうになる．

2020-09-09

WSL2とVSCodeでC++環境構築した（AtCoder Libraryを使えるようになるまで）

その他

Pythonで競プロをしていたけれど，AtCoderにてC++限定でAtCoder Library(ACL)が提供されたため，C++とPythonとついでにRustを書けるように環境構築しました．環境構築について詳しいわけではないですが，誰かの役に立つかもしれないと思ったのでメモを残しておきます．

想定読者はVScodeを使ってPythonなどC++以外の言語で競プロをしてたけど，C++の環境を作りたいWindowsユーザーです．ただ，WSL2でACLを使えるようにしたい！みたいなC++使いの人でも参考になるかもしれません．

WSL2を使えるようにするまでは他記事を見に行った方が親切に書かれています．一応ざっくりとは書きました．また，僕が参考にした記事や，これとは違うことがしたくて，dockerで楽にやりたいぜ！って人へのオススメ記事はこの記事の最後に貼っておきます．

既にVScodeを使ってて，WSLも入っててPythonを書いている人はC++を書けるようにするあたりから読むといいかもしれません． Pythonじゃなくて既にC++を使ってるけど，ACLが導入したいぜ！って人はACLを使えるようにする前後から読むといいかもしれません．

Visual Studio Codeをインストールする
WSL2を使えるようにする
gccをインストールする
VScodeでC++を書けるようにする
tasks.jsonを編集する
ACLを使えるようにする
（おまけ）C++が自動整形されるようにする
オススメ記事や参考記事

Visual Studio Codeをインストールする

僕はVScodeを用いて競プロをしていたので入っています．

入ってない人は

code.visualstudio.com

公式からインストールしましょう．インストールが失敗したらzipファイルを解凍して使えるようにするなどの方法もあるみたいなので困ったら下のリンクを見に行ってください．Qiitaとかで「vscode インストール」などと検索するのもいいかもしれません．

code.visualstudio.com

WSL2を使えるようにする

MicrosoftのWSL2インストールガイドを見ます．

docs.microsoft.com

Windowsのバージョンがバージョン 1903 以降、ビルド 18362以上でないと書かれているので，設定>システム>バージョン情報を確認します．

f:id:ntk_ta01:20200908101650p:plain

OK！

OKでなかった人はアップデートしましょう．自動更新が来てなければ手動で更新しましょう． Windows 10 May 2020 Updateというやつです．

www.microsoft.com

次に2個，Windowsの機能の有効化をします．ドキュメントに書かれているようにpowershellを管理者権限で開いて，コマンドを2個打てばいいです．

dism.exe /online /enable-feature /featurename:Microsoft-Windows-Subsystem-Linux /all /norestart

dism.exe /online /enable-feature /featurename:VirtualMachinePlatform /all /norestart

もしくは，コントロールパネル>プログラム>Windowsの機能の有効化または無効化を開いて， Linux用Windowsサブシステムと，仮想マシンプラットフォームのところを有効にすればいいです（ここは言語が英語になっていることもあった気がします）．コマンドを打つのとやっていることは変わりません．

f:id:ntk_ta01:20200908103633p:plain

と

f:id:ntk_ta01:20200908103751p:plain

の2個です．

ここまでやって，再起動するとWSL2がインストールされたと思います．

再起動したら

wsl --set-default-version 2

をpowershellで実行しましょう．WSLの既定のバージョンを2とします．

そして，Microsoft Storeを起動し，Ubuntuと検索しましょう．何個か出てきた中でUbuntu20.04を入れます（僕は18.04やバージョンのついていないモノとの違いが分かっていません，新しい方がよさそう！と気持ちで20.04を入れています．気になる人は調べるといいでしょう）．

インストールしたら起動してみましょう．ストアのページを閉じたりして見失った人は検索窓に打ち込めば出てきます．

f:id:ntk_ta01:20200909171413p:plain

始めに起動すると，ユーザ名とパスワードの入力を求められたはずです．うろ覚えですが．僕はユーザ名をntkにしておけばなあ，と悔やんでいます．適切につけましょう．

gccをインストールする

Ubuntuを起動しておいて，いろいろ入れましょう．

sudo apt update
sudo apt upgrade

をまずします．

それから次のコマンドを打って，gccを入れましょう．

apt install gcc-9 g++-9

続きのことは好きなものがあれば入れてください．

（任意）次にPythonとpipを入れる．numpyとかを入れる．PyPyも入れる．

apt install python3.8 python3-pip
python3.8 -m pip install -U Cython numba numpy scipy scikit-learn networkx
apt install pypy3

（任意）さらにRustを入れる．

curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh

Rustはこの後に

Install Rust - Rust Programming Language

にあるように，パスを設定する必要があります．

g++-9 --version
python3 --version
PyPy --version
rustc --version

などを打って，入れたもののバージョンが表示されていたら成功です．

VScodeでC++を書けるようにする

VScodeとWSL2が入っていて，Pythonで今まで競プロをしてたよ！って人はここらへんから本題な気がします．前節でgccなどを入れたので（入れてない人は上の方にスクロールして入れてください！），VScodeでC++ファイルを作って，コンパイルして実行することはできるはずです．

VScodeを立ち上げます． WSL環境で作業するので，よさげな拡張機能Remote-WSLを使います．これを使わなくてもターミナルの既定のシェルを変更すれば作業できそうですが，ここではRemote-WSLを使います．

f:id:ntk_ta01:20200908123637p:plain

あとC++を使うので，C/C++の拡張機能も入れておきましょう．

f:id:ntk_ta01:20200909173434p:plain

左下の><みたいなやつをクリックして，Reopen Folder in WSLなどを選ぶとウィンドウが開くのでそこで作業をしましょう．

新しいウィンドウでは左下がWSL: Ubuntu-20.04などと表示されていると思います．

f:id:ntk_ta01:20200908124324p:plain

ctrl + shift + P を打ってコマンドパレットを開きましょう．C++の設定をするためにC/C++ edit configurationsと打ってJSONのものを選ぶと，設定ファイルが開くと思います．c_cpp_properties.jsonという名前のファイルです．下のように書くと，C++の補完とかが効くようになると思います．

{
    "configurations": [
        {
            "name": "WSL",
            "includePath": [
                "${workspaceFolder}/**",
                "/usr/include/**"
            ],
            "defines": [
                "_DEBUG",
                "UNICODE",
                "_UNICODE"
            ],
            "compilerPath": "/usr/bin/gcc-9",
            "cStandard": "c11",
            "cppStandard": "c++17",
            "intelliSenseMode": "gcc-x64"
        }
    ],
    "version": 4
}

さっそくC++ファイルを書いて，コンパイルして実行してみましょう．ターミナルはctrl + shift + @で起動できます．

C++のコンパイルは

g++-9 (ファイルの名前) -std=gnu++17 -o (実行ファイルの名前）

のようにできます．g++-9 をg++にしている人もいるかもしれません（切り替えたい人はupdate-alternativesをするといいかもしれません）．-std=gnu++17はc++17の機能を使えるようにしています（参考：処理系 - cpprefjp C++日本語リファレンス）． -o (ファイルの名前）で実行ファイルの名前を決められます．

3枚下の画像では

g++-9 test.cpp -std=gnu++17 -o test

としています．他にもいろいろなコンパイルするときのオプションがつけられます．とりあえずこのままコンパイルしてみましょう．testというファイルができたはずです．エクスプローラーのところを更新して確認するか，lsコマンドを打てばいいです．

f:id:ntk_ta01:20200910225700p:plain

f:id:ntk_ta01:20200910225759p:plain

ファイルができたら実行してみましょう． ./test と打てば実行できます．

f:id:ntk_ta01:20200908124949p:plain

できました．<bits/stdc++.h>もincludeできていてよかったです．

tasks.jsonを編集する

tasks.jsonを編集すると，コンパイルがctrl + shift + B でできるようになります．C++を使うときはいろいろコンパイラオプションをつけたくなりますが，いつも打つのは面倒なので書いちゃいましょう．

上のバーからターミナルを押して，既定のビルドタスクを構成しましょう．うろ覚えですが，g++ ほにゃららとか書いてるのを選ぶと（全然違う感じで出てくるかもしれません．すみません），tasks.jsonというファイルが開くと思います．

f:id:ntk_ta01:20200909161937p:plain

開いたら次のように書くといいです．オプションは僕が使ってるやつも含めています．¹

{
    "version": "2.0.0",
    "tasks": [
        {
            "type": "shell",
            "label": "C/C++: g++-9 compile file",
            "command": "/usr/bin/g++-9",
            "args": [
                "-std=gnu++17",
                "-Wall",
                "-Wextra",
                "-Wshadow",
                "-Wconversion",
                "-fsanitize=undefined",
                "-ggdb",
                "${file}",
                "-o",
                "${fileDirname}/${fileBasenameNoExtension}"
            ],
            "problemMatcher": [
                "$gcc"
            ],
            "group": {
                "kind": "build",
                "isDefault": true
            }
        }
    ]
}

f:id:ntk_ta01:20200909175933p:plain

これを保存して，C++ファイルを開き直してctrl + shift + Bでコンパイルしてみましょう．できなかったらウィンドウを開き直すとできると思います（たぶん）．

ACLを使えるようにする

AtCoder Libararyを使えるようにしましょう．持ってない人はまず

atcoder.jp

からダウンロードしましょう．解凍して作業ディレクトリにac-libraryを持ってきましょう．² そしてこれを使ってコンパイルしたりこれの補完を効かせるためには，c_cpp_properties.jsonとtasks.jsonを書き換えるといいです．

まずc_cpp_properties.jsonからです．includePathを足してあげましょう．ac-libraryのパスを書いてあげればいいです．// 以降のコメントは消していいです．

{
    "configurations": [
        {
            "name": "WSL",
            "includePath": [
                "/mnt/c/Users/ntk/Documents/AtCoder/ac-library/", // 書き足すところ!!!!!
                "${workspaceFolder}/**",
                "/usr/include/**"
            ],
            "defines": [
                "_DEBUG",
                "UNICODE",
                "_UNICODE"
            ],
            "compilerPath": "/usr/bin/gcc-9",
            "cStandard": "c11",
            "cppStandard": "c++17",
            "intelliSenseMode": "gcc-x64"
        }
    ],
    "version": 4
}

上は僕の環境のパスを書いてますが，自分のに書き換えてください．パスがわからない人は，

f:id:ntk_ta01:20200909163605p:plain

と，ac-libraryのところで右クリックをするとパスのコピー，が出てくるのでこれを貼るといいです．

次にtasks.jsonですが，

{
    "version": "2.0.0",
    "tasks": [
        {
            "type": "shell",
            "label": "C/C++: g++-9 compile file",
            "command": "/usr/bin/g++-9",
            "args": [
                "-std=gnu++17",
                "-I", //書き足すところ
                "/mnt/c/Users/ntk/Documents/AtCoder/ac-library/", //書き足すところ
                "-Wall",
                "-Wextra",
                "-Wshadow",
                "-Wconversion",
                "-fsanitize=undefined",
                "-ggdb",
                "${file}",
                "-o",
                "${fileDirname}/${fileBasenameNoExtension}"
            ],
            "problemMatcher": [
                "$gcc"
            ],
            "group": {
                "kind": "build",
                "isDefault": true
            }
        }
    ]
}

と足しましょう．"-I"はそのままで，次の行はさっきと同じac-libraryのあるパスを書きましょう．これで，#include <atcoder/all>とかができるようになったはずです． C++ファイルで <atcoder/all>をincludeして，atcoder::と打った後にctrl + spaceを押したり，コンパイルしましょう．補完が出て，コンパイルもできたら成功です．なにかできなかったらウィンドウをリロードしてみるといいかもしれません（これよくわかってないんですけど，tasks.jsonを書き換えた後に開き直さないと変更が適用されてなさそうなんですよね，自分だけかもしれませんが）．

f:id:ntk_ta01:20200909164122p:plain

できたら終わりです．お疲れさまでした．

（9/10 追記） AtCoderで提出するときに言語切り替えが必要です．忘れないようにしましょう．

f:id:ntk_ta01:20200910214828p:plain

（10/16 追記）切り替えなくてよくなったそうです．

https://atcoder.jp/posts/535

（おまけ）C++が自動整形されるようにする

C++を保存したときに自動整形されるようにしたいです．またctrl + shift + P を打ってコマンドパレットを開いてsettingと打ち，設定を選びましょう．設定の入力にformat on saveと打つと，ファイルを保存したときにフォーマットしてくれるようになります．

f:id:ntk_ta01:20200908125416p:plain

さらに調整したい人は，Clang-Format拡張機能を入れましょう．

f:id:ntk_ta01:20200909174257p:plain

そして.clang-formatファイルを作り，細かい設定を書き込むといいと思います．設定については公式を見るといろいろ変更できることがわかります．

Clang-Format Style Options — Clang 12 documentation

僕のは下の感じです．

BasedOnStyle: Google
IndentWidth: 4
AccessModifierOffset: -4
AllowShortCaseLabelsOnASingleLine: true
AllowShortFunctionsOnASingleLine: InlineOnly
AllowShortIfStatementsOnASingleLine: true
ColumnLimit: 120
BreakBeforeBraces: Custom
BraceWrapping:
    BeforeElse: false
AlwaysBreakTemplateDeclarations: No
PointerAlignment: Right
IncludeBlocks: Merge

あとはこれが適用されるように，設定を書き換えます．コマンドパレットから設定を開いて，clang-format:executableと検索しましょう．あとは.clang-formatファイルのパスを貼ればいいです．

f:id:ntk_ta01:20200909174533p:plain

（TODO!）

launch.jsonについても書く．デバッガを使えると便利です．
Online judge Toolsとか便利そうですよね．僕もまだ導入していません．

オススメ記事や参考記事

環境変数に書きたい人向け．

bakamono1357.hatenablog.com

参考にしました．

qiita.com

Dockerで楽にやりたい人向けです．

scol.hatenablog.com

Dockerで，なんかなんでも入ってそうな感じです．

github.com

オプション，C++に移行したばかりでよくわかってなくてオススメがあれば教えてください↩
僕はwindowsのフォルダで作業しているのでダウンロードしたフォルダも簡単に移動させることができましたが，WSLの方にフォルダを移動させたい人もいますか？cpコマンドを使うか，ubuntuを起動してexplorer.exe . を打ってフォルダを移動させるといいかもしれません．↩

2020-09-05

Codeforces Round #667 (Div. 3)

競プロ

コンテストへのリンク

ABCD4完．Eは解けなかった．

以下問題ごとの感想とACコード．

A問題

問題概要

正整数 $a$ と $b$ が与えられる． $a$ に $1$ から $10$ の数を足したり引いたりして， $b$ にしたい．必要な最小の操作回数はいくつか求めよ．

解法

できるだけ $10$ を足したり引いたりする方がお得．いつまで $10$ を足したり引いたりするかというと， $a$ と $b$ の差が $10$ より小さくなるまでその操作を行う． $a$ と $b$ の差が $10$ より小さくなったとき，その差が $0$ でなければもう一度だけ追加の操作を行う．

$10$ を使う操作を何回できるか，というと $\lfloor \frac{|a-b|}{10} \rfloor$ となる．例えば $a = 2, b = 22$ だったら $2$ 回．追加の操作が必要かは $|a-b|$ を $10$ で割った余りが $0$ かどうか判定すればよい．例えば $a=2, b = 25$ だったら追加の操作も必要になり答えは $3$ 回．

より短くコードを書くならば， $\lceil \frac{|a-b|}{10} \rceil$ が答えになる．

Tips

Pythonで切り捨てを書くなら，vを整数の値として

v // 10

と書けばよいし，切り上げを書くなら

0 -- v // 10

と書けばよい．もちろん切り上げは次のように書いてもよい．

(v + 10 - 1) // 10

コード

def main():
    T = int(input())
    for _ in range(T):
        a, b = (int(i) for i in input().split())
        if a < b:
            a, b = b, a
        ans = abs(b - a) // 10
        if abs(b - a) % 10 != 0:
            ans += 1
        print(ans)


if __name__ == '__main__':
    main()

C++コード

// #define _GLIBCXX_DEBUG
// #pragma GCC optimize("Ofast")
#pragma GCC diagnostic ignored "-Wsign-compare"
#include <bits/stdc++.h>
using namespace std;
using i64 = int_fast64_t;
#define rep(i, n) for (i64 i = 0; i < (i64)(n); ++i)
#define reps(i, s, n) for (i64 i = s; i < (i64)(n); ++i)

void solve() {
    int t;
    cin >> t;
    while (t--) {
        int a, b;
        cin >> a >> b;
        int d = abs(a - b);
        cout << (d + 10 - 1) / 10 << "\n";
    }
}
int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    // cout << fixed << setprecision(15);
    solve();
}

B問題

これは何ですか？コンテスト中は地獄のような実装をした．

問題概要

正整数 $a,b,x,y,n$ が与えられる． $n$ は操作回数で， $a$ を $1$ 減らす操作か $b$ を $1$ 減らす操作ができる．ただし， $a \ge x$ と $b \ge y$ を満たすようにしなければならない．このとき $a$ と $b$ の積の最小値はいくつか．

解法

公式解説を見ると簡潔に書かれていて， $a$ をできるだけ減らしてから $b$ を減らすか，その逆をやればよい．そして小さい方を出力する．

感想

この問題で苦しんだのは，どうやったら積が最小になるかをあまり考えずにとりあえず実装したのが理由だと思う．初めは $a$ と $b$ をできるだけ等しくなるようにも操作をしようとしていた．

ただ公式解説を読んで改めて小さな例を考えてみると，できるだけ等しくなるように操作をするのは無駄だったことがわかった． $a = 9, b = 7$ でどちらを減らした方が得するか考えたい．減らす前の積は $63$ である． $a$ を減らすと $a=8, b=7$ となり，積が $56$ になる．一方， $b$ を減らすと $a=9, b=6$ となり，積が $54$ になる．このように一方を減らすと，もう一方の減らしていない数だけ積の結果が減る．よって小さい数を減らし続ける方が得なので，操作は二種類しか考えれられなくなる．

一回の操作の影響を考え，どうすれば得をし，最適な値が得られるか方針を立ててから実装すべきだった．

$a$ を先に減らす方針を関数で書いた後，コピペして引数を書き換える実装をした．

コード

def check1(a, b, x, y, n):
    s = a - max(x, a-n)
    a -= s
    n -= s
    t = b - max(y, b-n)
    b -= t
    n -= t
    return a*b


def check2(b, a, y, x, n):
    s = a - max(x, a-n)
    a -= s
    n -= s
    t = b - max(y, b-n)
    b -= t
    n -= t
    return a*b


def main():
    T = int(input())
    for _ in range(T):
        a, b, x, y, n = (int(i) for i in input().split())
        print(min(check1(a, b, x, y, n),
                  check2(a, b, x, y, n)))


if __name__ == '__main__':
    main()

C問題

問題概要

正整数 $n, x, y$ が与えられる． $n$ 要素の数列を構築する問題．数列の要素はすべて異なる正整数である．数列を昇順に並べたときに，隣り合う要素の差はすべて等しくしなければいけない．さらに，条件を満たすような数列のうちで，最大値が最小になる数列を出力せよ．このような数列が存在することは保証される．

解法

$x$ と $y$ の差の約数を計算して，その約数のいずれかを用いて条件を満たす数列を構築する．具体的には，ある約数を $d$ としたときにまず $y$ から $d$ を減らしていったものを数列の要素とする．つまり $(y, y-d, y-2d, ...)$ のような数列になる．要素数が $n$ になったら構築を終了し，要素が $1$ より小さくなったら逆側に構築する．つまり $(y+d, y+2d, ...)$ を追加すればよい．作った数列のうちで，最大値が最小の数列が答え． $x$ が含まれているか，もしくは $x$ が二個含まれていないか，数列の二要素間の差がすべて等しいかなどに注意する．

これはサンプルが親切で， $2, 1, 49$ や $5, 3, 8$ を見て最初は差だけを用いて数列が作れそうな気を感じ取る．ただ $5, 20, 50$ を見ると，単に差ではいけず，差の約数を用いれば作れそうだとわかる．

ただ、制約が小さいのでもっと愚直に解けて $O(n^3)$ 解法もある．これは数列の開始の数 $start$ と差 $d$ を全探索すればよい．

コード

def main():
    def enum_divisors(n):
        divs = []
        for i in range(1, n+1):
            if i*i > n:
                break
            if n % i == 0:
                divs.append(i)
                if n//i != i:
                    divs.append(n//i)
        return divs

    T = int(input())
    for _ in range(T):
        n, x, y = (int(i) for i in input().split())
        diff = y - x
        divs = enum_divisors(diff)
        ans = []
        ans_max = 10**18
        for d in divs:
            A = [y]
            v = y
            while len(A) < n and 0 < v - d:
                v -= d
                A.append(v)
            v = y
            while len(A) < n:
                v += d
                A.append(v)
            maxA = max(A)
            A.sort()
            if x not in A or any(A[i+1] - A[i] != d
                                 for i in range(len(A)-1)):
                continue
            if len(A) == n and maxA < ans_max:
                ans = A
                ans_max = maxA
        print(*ans)


if __name__ == '__main__':
    main()

全探索解法のコード

def main():
    T = int(input())
    for _ in range(T):
        n, x, y = (int(i) for i in input().split())
        ans = []
        ans_max = 10**12
        for start in range(1, 50):
            for d in range(1, 50):
                A = [start+i*d for i in range(n)]
                if x not in A or y not in A:
                    continue
                maxA = max(A)
                if maxA < ans_max:
                    ans = A
                    ans_max = maxA
        print(*ans)


if __name__ == '__main__':
    main()

D問題

問題概要

正整数 $n, s$ が与えられる． $n$ の桁和が $s$ 以下になるまでに必要な最小の操作回数を求めよ． $n$ に $1$ 足す操作が許されている．

解法

繰り上がりが起きると，繰り上がり前より桁和は小さくなるか変わらない．例えば $22$ と $30$ の桁和は $4$ と $3$ である．また $n$ が $18$ 桁くらいしかないので，毎回桁和を計算してよく，桁和が $s$ より大きいならば下の桁から繰り上がりを計算することを繰り返す．

具体的な実装は，何桁目を見ているかの0-indexedの変数 $d$ を持ちながら，各桁を $10$ で割った余りを計算していく． $d$ 桁目は $n // 10^d$ で表現できる．その余りを $dig$ とすると，計算した桁を繰り上げるために必要な数は $(10 - dig) \% 10$ になる． $dig = 0$ のことを考えて $10$ で割った余りとしている．ただし， $d$ 桁目を見ているときは，操作回数としては $(10 - dig) \% 10$ に $10^d$ を書けた数を足すようにすることに注意する．

ABC158Eを思い出した．

コード

def main():
    T = int(input())
    for _ in range(T):
        n, s = (int(i) for i in input().split())
        cur = sum(int(v) for v in str(n))
        ans = 0
        if cur <= s:
            print(ans)
        else:
            d = 0
            while cur > s:
                dig = (n//(10**d)) % 10
                # dig = int(str(n)[::-1][d]) でもOK

                ans += ((10-dig) % 10) * (10**d)
                n += ((10-dig) % 10) * (10**d)

                cur = sum(int(v) for v in str(n))
                d += 1

            print(ans)


if __name__ == '__main__':
    main()

E問題

koboshiさんの解説を見て通しました．これ以上に説明することはありません（え？）．

ただ自分でも整理するために言語化する．

問題概要

2次元平面上に $n$ 個の頂点が与えられる． $x$ 軸方向に水平なプラットホームの長さ $K$ も与えられ，プラットホームを2個配置したときに救える頂点の最大値を求めよ．頂点を救う，とは頂点が $y$ 軸の負方向に"落ちてくる"と想像し，落ちた頂点の下にプラットホームがあるときのことをいう．問題のサンプル下の絵を見るのが，よりよい理解のためになる．

解法

$y = - \infty$ にプラットホームを配置すると考えれば，頂点の高さを気にしなくてよくなる．よって， $y_i$ は無視する．

一つのプラットホームを固定したとき，救える頂点の個数は二分探索により求まる．これは，固定したプラットホームの左端を $x_i$ とすると $x_i + K$ を超えない頂点の最大の添え字を $j$ としたとき， $j - i + 1$ 個である．これを $count_i$ とする．なお $x_i$ を二分探索するため，先にソートしておくのを忘れないようにする．

また，その固定したプラットホームの左端より，Kよりも大きい距離が離れたプラットホームの左端で最大の値を $x_j$ とする．つまり， $x_j \lt x_i - K$ ． $j$ も二分探索によって求まる． $j$ 番目までのプラットホームが救える頂点の最大値を $countmax_j$ とし，これがわかっていれば， $i$ 番目のプラットホームを固定したときの救える頂点の個数は $count_i + countmax_j$ である． $count_i$ を計算するときには， $i$ より小さい $j$ について $count_j$ がわかっているので， $countmax_j$ も計算できる．

あとは $x_i$ から見て $K$ より大きい距離が離れている頂点がなければ $x_i + K$ までの頂点はすべて救えることに注意して，固定するプラットフォームを全探索し，上の計算をすれば答えが求まる．

感想

二つ操作できる対象があったときに，同時に動かそうとするのではなく，一方を固定するなどバラバラに考えるようにしたい．一方を固定したときに何が計算できるか，もう一方については簡単に最適な状況の値が求まらないかを考えたい．

コード

def is_ok(X, K, i, mid):
    if X[mid] - X[i] <= K:
        return True
    else:
        return False


def binary_search(X, K, i):
    ng = len(X)
    ok = i
    while abs(ok - ng) > 1:
        mid = ng + (ok - ng) // 2
        if is_ok(X, K, i, mid):
            ok = mid
        else:
            ng = mid
    return ok


def is_ok2(X, K, i, mid):
    if X[mid] < X[i] - K:
        return True
    else:
        return False


def binary_search2(X, K, i):
    ng = i
    ok = 0
    while abs(ok - ng) > 1:
        mid = ng + (ok - ng) // 2
        if is_ok2(X, K, i, mid):
            ok = mid
        else:
            ng = mid
    return ok


def main():
    T = int(input())
    for _ in range(T):
        N, K = (int(i) for i in input().split())
        X = [int(i) for i in input().split()]
        _ = [int(i) for i in input().split()]
        X.sort()
        count = [0] * N
        for i in range(N):
            ret = binary_search(X, K, i)
            count[i] = ret - i + 1
        ans = count[0]
        count_max = [0]*N
        count_max[0] = count[0]
        for i in range(1, N):
            cur = count[i]
            if X[i] - X[0] <= K:
                cur += i
            else:
                j = binary_search2(X, K, i)
                # j までのcount のmax　を足す
                cur += count_max[j]
            ans = max(ans, cur)
            count_max[i] = max(count_max[i-1], count[i])
        print(ans)


if __name__ == '__main__':
    main()

こどふぉ参加前のくじかつが1完だったので調子悪いかと思ったけど、4完できてよかったぜ……．いや，KEYENCE String難しかったんだよ……．あとEを読んでいるときに作問者はFall Guysをやっていると思った．コンテスト中に思った．

f:id:ntk_ta01:20200905134127p:plain

2020-08-30

ABC177 E - Coprime

競プロ

E - Coprime

問題概要

$N$ 個の整数からなる集合{ $A_i | 1 \le i \le N$ }が，pairwise coprime，setwise coprime，もしくはnot coprimeであるか判定せよ． pairwise coprimeとは， ${A_i}$ について $GCD(A_i, A_j) = 1 ( 1 \le i \lt j \le N )$ が成り立つときのこととする．setwise coprimeとは，pairwise coprimeでない，かつ $GCD(A_1, ... , A_N) = 1$ が成り立つときのこととする．どちらでもないとき，not coprimeとする．

解法

まず， ${A_i}$ 全体のGCDを取り，それが1でなければnot coprimeとする．全体のGCDが1でなければ，setwise coprimeでないし，pairwise coprimeなら全体のGCDは1になるので，pairwise coprimeでもないからである．

次に，pairwise coprimeでないかを判定したい．pairwise coprimeでなければ，ある1つの $GCD( A_i, A_j )$ が1でないはずである．これは，ある $( A_i, A_j )$ が1より大きい公約数を持つことを意味する．そこで，各整数 $A_i$ を素因数分解して，どれか一つでも素因数が被っているようなら，ある $( A_i, A_j )$ が1より大きい公約数を持つことに気がつく．

よって， $N$ 個の整数 $A_i$ を高速に素因数分解したい．前処理なしである一つの整数 $n$ を計算量 $O(\sqrt{n})$ で素因数分解する方法は，けんちょんさんの記事などに書かれていて有名である．ただし今回それを用いると， $O(N\sqrt{N})$ かかってしまい，間に合わない¹．

そこでosa_k法を用いる．これを用いると，素因数分解したい最大の整数を $n$ としたとき，前処理 $O(nloglogn)$ で，素因数分解クエリ $O(logn)$ ができる．前処理はエラトステネスの篩²をしながら，各整数を割り切る最小の素因数を求める．素因数分解は，nを割り切る最小の素因数で割り，nをその割った結果で置き換えながら，nが1になるまで割り続けることでできる．

あとは，各整数 $A_i$ を素因数分解し，出てくる素因数が被っていないかチェックする．被りのチェックは，(Aの最大要素 + 1)の長さの配列を用意しておき，それぞれの整数の素因数ごとに1を足していき，配列の最大値が1以下か確認するなどでできる．

コード

def main():
    from math import gcd
    _ = int(input())
    A = [int(i) for i in input().split()]
    maxA = max(A)

    def Eratosthenes(sup: int) -> set:
        primes = [True]*(sup+1)
        primes[0] = False
        primes[1] = False
        for i in range(2, sup+1):
            if primes[i]:
                MINFact[i] = i
                mul = 2
                while i*mul <= sup:
                    primes[i*mul] = False
                    if MINFact[i*mul] == -1:
                        MINFact[i*mul] = i
                    mul += 1

    def prime_factor(n):
        while n != 1:
            prime = MINFact[n]
            while MINFact[n] == prime:
                n //= prime
            B[prime] += 1

    MINFact = [-1] * (maxA + 1)
    MINFact[0] = 0
    MINFact[1] = 1
    Eratosthenes(maxA)

    g = A[0]
    for a in A:
        g = gcd(g, a)

    B = [0]*(maxA+1)
    for a in A:
        prime_factor(a)

    if g != 1:
        print("not coprime")
    elif max(B) <= 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")


if __name__ == '__main__':
    main()

提出コードへのリンク

コンテスト中は「素因数分解高速」とかでググって，なんとか実装した．

以下，参考にしました．

drken1215.hatenablog.com

tutuz.hateblo.jp

・エラトステネスの篩の要領で1<=i<=10^6の各iについて「iの最小の素因数」を記録しておきます

・素因数分解のときは配列を参照してO(1)で素因数が1つ分かります。その素因数をpとして、i/pのもつ素因数も配列に既に記録されています

・素因数がO(1)で求まるので素因数分解をO(log N)で出来ます
— 十六夜　龍 (@Izayoi_R_sakura) 2020年8月29日

また，10⁶以下の素数が78498個しかないことから，1以外の数がこれより多ければpairwiseにはならないというツイートを見た．1以外の数がこれ以下なら $O(\sqrt{N})$ の素因数分解をしても，実行時間は2secに収まる．え，すげー．

コード

def main():
    from math import gcd
    _ = int(input())
    A = [int(i) for i in input().split()]

    def prime_factorize(n):
        for i in range(2, n+1):
            if i*i > n:
                break
            if n % i != 0:
                continue
            while n % i == 0:
                n //= i
            B[i] += 1
        if n != 1:
            B[n] += 1

    # 10**6 以下の素数は78498個しかない
    # よって，1以外の数がこれより多ければpairwiseにはならない
    check = True if sum(a != 1 for a in A) <= 80000 else False
    maxA = max(A)
    B = [0] * (maxA + 1)
    if check:
        for a in A:
            prime_factorize(a)

    g = A[0]
    for a in A:
        g = gcd(g, a)

    if g != 1:
        print("not coprime")
    elif check and max(B) <= 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")


if __name__ == '__main__':
    main()

提出コードへのリンク

C++なら間に合うのかも？Pythonは厳しいと思います．↩
素数列挙したいときに使うアルゴリズム．蟻本p.110に書いてある．↩

2020-08-29

Codeforces Round #595 (Div. 3) C2. Good Numbers (hard version)

競プロ

C2. Good Numbers (hard version)

バチャをした．4か月くらい前にも解いたのだけれど，3ペナ出した．うーん．

整理のために言語化しておく．

問題概要

$n$ 以上の整数のうちで，最も小さな「良い数」 $m$ を出力せよ，というクエリがいくつか与えられる．整数 $n$ はクエリごとに与えられる．「良い数」の条件は，異なる3の累乗数のみの和で表せる，である．例えば，4は3⁰ + 3¹と異なる3の累乗数のみの和で表せるので良い数であり，2は3⁰ + 3⁰のように異なる3の累乗数のみの和では表せないので良い数でない．

解法

与えられた整数 $n$ を3進数に直す．このとき，'0'か'1'のみからなる3進数であれば異なる3の累乗数のみの和で表せている．例えば，12は3進数に直すと $110_{(3)}$ であり，12 = $3^2 + 3^1$ でもあるから「良い数」である．逆に3進数に変換したときに'2'が存在すると，異なる3の累乗数の和では表せない．例えば，15は3進数だと $120_{(3)}$ である．3¹が2つ（ $15 = 3^2 + 2 \times 3^1$ ）や，3⁰が6つ（ $15 = 3^2 + 6 \times 3^0$ ）は必要であり，15は異なる3の累乗数のみの和では表せない．よって，'2'があれば，その桁に'1'を足して繰り上げるようにする．繰り上げた時点で，元の数 $n$ より大きくなるので，'2'があった桁と，それより小さい桁はすべて0にしてよい．このようにして構成した3進数を10進数に直したものが答え．

サンプル

input:96

output:108

それぞれ3進数に直すと， $10120_{(3)}$ ， $11000_{(3)}$ ．

実装

解法の前半はその通りに，3進数に直す．cnv_baseという基数変換の関数を書いた．解法の後半は実際に3進数を保持するのではなく，10進数の計算結果だけ持てばよい．r_cnvという関数を作成した．

コード

def main():
    def cnv_base(n, base):
        if n == 0:
            return 0
        digits = []
        while n != 0:
            digits.append(str(n % base))
            n //= base
        return "".join(digits)

    def r_cnv(S):
        d = 1
        ret = 0
        carry = 0  # 繰り上がり
        for s in S:
            v = int(s)
            if carry == 0:
                if v <= 1:
                    # 0か1なら足す
                    ret += v * d
                else:
                    # 繰り上げる
                    carry = 1
            else:
                ret = d
                # 繰り上がりがあったら，繰り上げた桁に1をたてる
                # 10120で考えてみるといいかもしれない
                # s = "2"でcarry = 1になったあと始めてret = d
                # が行われて，ret = 9になる．9は3進数に直すと100_{(3)}
                if v == 0:
                    carry = 0
                # else v が 0でないとさらに繰り上がりが起きる
            d *= 3
        if carry:
            # 117 = 11100_{(3)}のように繰り上げたときに100000になると
            # forの外にもif文が一つ必要
            ret = d
        return ret

    Q = int(input())
    for _ in range(Q):
        N = int(input())
        S = cnv_base(N, 3)
        print(r_cnv(S))  # , cnv(r_cnv(S)))


if __name__ == '__main__':
    main()

提出コードへのリンク

上手く言語化できた気がしないな…．おおまかな考察が進んだ後に，きれいな実装ができないのは考察を詰め切れていないからな気がする．ただその考察を詰め切るのが難しい……．

記事ツイートしたら反応もらった．bbgeさんすげ～～～になっています．簡潔な解法．こういう風にやるとわざわざ3進数に直さなくてよい．