黄色になった

こんにちは、まつかわです。

つい最近のAGCとdiv1でそれぞれ黄色と薄橙になりました！

f:id:Tallfall:20200106135430p:plain
精進グラフ、棚畑かよ
f:id:Tallfall:20200106132009p:plain
Codeforces, すぐ落ちそう

競プロ始める頃に立てた目標が黄色なので一応達成できたって感じですね。素直にとても嬉しいです。

こういう記事書くの初めてなんでやってみたかった恒例（？）の〇色までに何したか書きます！文章力が壊滅的なので箇条書き風です。

灰色まで

2018年の10月頃だったかなんか競技プログラミングで先輩がすごいみたいな噂が流れてくる
（後から知ったけどてんぷらさんだった）
プログラミングの勉強にもいいしやってみるかーと、とりあえず目についたけんちょんさんの記事を読みつつ適当なABC過去問に挑戦するも、
A問題で30分くらい掛けたしB問題が普通に分からなかった
（今見るとdifficulty20らしい、人は成長する生き物だなぁ）
（これ: B - Stone Monument）
それでこれはやりがいがあるぞと思った記憶がある
そのあと土曜夜に都合がつかないのもあって初コンテストまでABC-B, Cを中心に20~30問解いた。
でその初コンテストはCまで3完だった（当時ABC-Cの勝率は２～３割くらいだったからラッキーだったと思う）

茶色まで

300の勝率を上げようということで、土日を使ってAtCoderProblemsにある300点問題を70問くらい解いた。今は1日30ACとかこなせないからこのせいでProblemsのDailyEffortが死んだ。
ただその甲斐あって二回目のratedで茶色になれたし結構効いた気がする。

緑色まで

当時は3完で水perf結構出てたんで300解ければ...っていうのはあったので、その点300解くのはいい戦略だったように思う。よく昔の方がパフォ出易かったなんて話を聞くけど人によってはそうなのかもしれない。（昔の方がC自体の難易度は高いと思うけど）
ということで300埋めを主にやって緑になった

水色まで

ここから結構停滞し始めて、300埋め終わった（当時）ので400を埋めていたんだけど、当時の方針としてはどちらかといえば自分の挑戦域を広げるよりは確実に解ける問題を増やしていたように思う。
個人的には水色になるにあたって押さえておくべき（知らないと同レート帯に差をつけられる）アルゴリズム的知識がジャンプするような気がしていて、自分も結構ライブラリを色々書いていたような記憶がある。
企業コンに負け続けつつもABC全完して何とか水色になった
（Various Sushiの回50分全完は何気にえらいと思う）

青色まで

twitterを始めた
Codeforcesを始めた
水色になってABCがunratedになったのでratedが激減した。丁度行き詰まりを感じ始めていた時期と重なり、自然とモチベが減っちゃったので、
精進グラフもかなり緩やかになってしまった。当たり前だと思うんですけど自分の適性以上の問題を解き続けないと天才じゃない限り実力は停滞（相対的に減少）しちゃうし完全に悪循環だったように思える。
ただ何の気なしに申し込んだ関西のオンサイトコンCPSCOに行ってめちゃくちゃ楽しかったので（コミュ障気味な自分でも凄い楽しかった）
それでモチベが爆上がりしてそのおかげで青になれました、感謝。

黄色まで

ちょっと他のことが忙しくなり精進とかは片手間でやりつつ帰省も兼ねてHUPCに行ったりした、すげえ楽しかった。
学生最強コン予選通過できて初の（予選がある）オンサイトに行ったりもした、前の方座ってたので表彰者写真撮影のとき頭が邪魔だから平伏することになって何かを感じた。9~11月は色々あってコンテスト以外で問題を解かないみたいな生活してたけど当然レートは停滞した、令和ABCが無かったらレート的にモチベ的にもやばかったと思う、12月入ってからは結構解き始めてProblemsの黄diffを埋めた。期間的には長いけど振り返ってみるとあんまり中身がないなぁ。やっぱりやらないと伸びないね。
で年末のtourist回AGCで黄色になれた、嬉しい、tourist最高！！

これから

丁度年始だし今年の目標みたいなのを残しておきます、とりあえず今半分弱終わった橙diff埋めを終わらせて赤diffをゆっくり解いていければなぁと思ってます、あとそろそろ自分の問題解くスピードが周りに比べて顕著に遅いと痛感しだしたのでCFdiv2バチャとかを（中々まとまった時間とりにくいけど）やっていきたいですね、TLで流れているやつとかは積極的に参加したいです。数字的な目標でいえばやはりもう一つ上の色に行ってみたいという思いはありますが、まずはAtC2200あたりを目指すべきかなぁと思ってます（そのくらいの人にあまり勝てるビジョンが見えないくらいには実力差ありそう）

f:id:Tallfall:20200107055039p:plain
埋め具合, Problems, Scoresには本当にいつもお世話になってます

pythonでやる競プロについて

まぁよく見る話題なので...実際雑談のネタとしてはありだと思います。正直使いたければ使えばいいという言葉に尽きる気もしますが、自分のレートの律速は使用言語ではなくまだまだ自分の頭の悪さや経験不足です。逆にそれが大きく響くくらいの実力に早くなりたいものです。


ライブラリ

上でもあったんですが、自分はパターンマッチングとかそういうのがまだまだ遅くて、それが響いてN完激遅とかN+1問目を逃すとかが多いです。後者は特に悔しいですよね、なので最近は意識的にライブラリを増やしたり、思考の類型分類をするようにしています。折角なので書いたやつを列挙していきます、気持ち使う頻度の昇順です

  • オイラーパス復元
  • 最大長方形
  • BinaryTrie
  • Baby-step Giant-step
  • LiChaoTree
  • 最近点対（分割統治） - 最近ランダムな軸でsortする奴の方が実用的かなーと思ってる
  • GrahamScan
  • Trie
  • rollinghash
  • SCC
  • 行列累乗　 - python使ってるのにこれ書くのあほくさすぎる
  • LIS
  • LCS
  • LCA
  • Dinic
  • ランレングス圧縮　 - 使うようで使わない
  • メビウス関数求めるやつ（Aのすべての約数について求めるのと1..Nのを列挙するやつ）
  • ガウスの消去法　 - 任意modで2のときだけbit演算使ってるけどmod2以外使ったことない
  • Z-algorithm
  • 双対セグ木
  • 遅延セグ木(RAQ, RSQ)　 - 二分探索も付けたけどいる？ってなってる
  • トポロジカルソート
  • オイラーツアー
  • BIT 　 - 最近セグ木で良くね？ってなりがち
  • BIT上の二分探索でmultisetの真似 　 - 超便利, pythonにはstd::setがないからこういうのか平衡二分探索木は必携だと思う
  • 二項係数とかの前計算 　 - まとめとくと便利
  • 素因数分解等 　 - 色々できる
  • dijkstra
  • Union-Find 　 - ctrz もつけてる
  • セグ木 　 - い つ も の
  • popcount 　 - bin(x).count('1')はありえないほど遅いので。 多倍長でも使う
  • 木のテンプレ 　 - 便利,辺の入力と 親とトポロジカル順序と子を全て出す、主に木dp用
  • 座圧　 - とりあえずしちゃう

需要があればどこかに適当に置いておきます

まとめ

黄色になるとワートリの二期が決まる

ABC129

python 競プロ AtCoder ABC

こんにちは、まつかわです。最近寝不足です。

19/06/10のABC129に参加しました。反省が多い回だったので記事にすることにしました。

f:id:Tallfall:20190610040640p:plain
F解きたかった

問題文
AtCoder Beginner Contest 129

A - Airplane

必ず丁度二回飛行機を使うので、使わない飛行機を考えると楽そうですね。

提出: Submission #5835600 - AtCoder Beginner Contest 129

B - Balance

問題文に書かれていることをそのまま実装すればよいですね、累積和は使う必要無かったですけどどっちが実装早かったかは微妙。

提出: Submission #5850684 - AtCoder Beginner Contest 129

C - Typical Stairs

件の入力形式でかなり焦りました。
EDPC解いてればほぼ間違いなくdpは見えるんじゃないですかね。
早く全部解かなきゃ...

提出: Submission #5841174 - AtCoder Beginner Contest 129

D - Lamp

やりたいことはすぐ見えるけれども、実装の方針で結構難度が変わりそうな問題でしたね。
自分は一往復する感じで行を見ていきました。転置して同じ処理をするとコピペができて楽ですね。
.split('#')を使って実装してる人がいて（本質的にはランレングス圧縮）賢いなと思いました（こなみ）
AtCoderはかなりpythonに優しいのでpypyで書くと通ります。
汎用的なこととして、二次元grid系の問題がTLEしそうだなと思ったら

  • PyPyを使う（前提）
  • 文字列をやめる（.find()や.split()を効果的に多用してない限りかなり効くし実装も楽になりがち）
  • 一次元に書き直す（効くけど実装がすこし大変）

あたりをしとくといいと思います。

提出: Submission #5846943 - AtCoder Beginner Contest 129

E - Sum Equals Xor

a^bは（ここで＾はbitwiseOR）繰り上がりのない足し算だというのは典型で、
制約から桁dpっぽいのも典型で
区間の分割も典型でした。イメージとしては
[0, 12345]を
[0, 10000),[10000,12000),[12000,12300),[12300, 12340),[12340,12345]に分割するみたいな感じです。
典型の詰め合わせで面白かったです。全体的にここまで遅かったです、反省。

提出: Submission #5850684 - AtCoder Beginner Contest 129

F - Takahashi's Basics in Education and Learning

制約からLに対して O(\log{L}) か O(1)で解くべきなのはそんな気がします。
s[i]の桁が一定の区間をまとめて処理すると楽そうだなぁとは思ってたのですが、式をぐりぐりしていると
分数を用いた表式が出てきてこれは解けたなとか思ってました。まぁ法と分母が互いに素とは限らなかったので逆元が使えないので駄目でした。残念。

さて、s[i]までに対するこの問題の答えをans[i]とします。ここでs[i+1]の桁数をkとすると
この時、ans[i+1] = ans[i]*10**k + s[i+1]
が成り立ちます。この視点がコンテスト中には足りませんでした。ここで固定されたkについてまとめて考えて(単調性からこれは区間になる)10進表記でk桁になる要素がp個あるとすると、
ans, T の初期値を適切に考えるとして
ans \to 10**k*ans + T
T \to T + B
という変換をp回してやれば良いことになります。
これは
\begin{pmatrix} ans \\ T \\ 1 \end{pmatrix} \gets \begin{pmatrix} 10^{k} & 1 & 0 \\ 0 & 1 & B \\ 0 & 0 & 1\end{pmatrix}^{p}\begin{pmatrix} ans \\ T \\ 1 \end{pmatrix}
を計算することに他ならず、行列累乗でO(N^{3}\log(p))で求まります（Nは行列のサイズ = 3）。実装は案外軽いですね。
同桁長の列挙でバグらせて2WAしました。

提出: Submission #5861678 - AtCoder Beginner Contest 129

オフラインクエリのset実装

競プロ python ライブラリ

この記事はpythonで競プロやってるひねくれた人向けです。

最近ボンタン飴がマイブームなまつかわです、
この前のCPSCOの記事
CPSCO2019参加記(1日目) - Tallfallの日記

でpythonにstd::setをくれと書いたらなんとそれっぽいのをnadareさんとfineさんが実装してくれたので記事にまとめてみることにします。
というよりは自分のための実装のメモに近いです。
参照: Submission #5671536 - CPSCO2019 Session1


やりたいことは主に以下の３つ

  • add(i, x) : iを集合にx個挿入(削除)する
  • get(v) : 集合の要素中v番目に小さい値を取得
  • count(i) : 集合の要素であってi以下(未満)の個数を取得(iが何番目か分かる)

これに加えてv番目までの和とかi以下の和とかを求めるクエリなどにも応用できる

これらを扱いたい値全体の要素数をnとして O(\log{n})で処理する



実装にはBIT上の二分探索を使用している
分かりやすい記事をけんちょんさんが書いているので未読の方は読んだ方が以下が分かりやすいかと思います。
k 番目の値を高速に取り出せるデータ構造のまとめ - BIT上二分探索や平衡二分探索木など - Qiita

以下メモ

  • クラス名は参照元に従ってDammyMapとしてます
  • 挿入もしくは削除する値は予め分かっている必要があります
  • 分かりやすいようにaddで座圧したりgetで戻したりして値自体で扱えるようにしてますが、どうしてもTLEしそうとかだったらindexでやり取りするのが速いと思います
from itertools import accumulate
from collections import Counter
from bisect import bisect as br, bisect_left as bl
class PMS:
    #1-indexed
    def __init__(self, A, B, issum = False):
        #Aに初期状態の要素をすべて入れる,Bは値域のリスト
        self.X, self.comp = self.compress(B)
        self.size = len(self.X)
        self.tree = [0] * (self.size + 1)
        self.p = 2**(self.size.bit_length() - 1)
        self.dep = self.size.bit_length()
        
        CA = Counter(A)
        S = [0] + list(accumulate([CA[self.X[i]] for i in range(self.size)]))
        for i in range(1, 1+self.size):
            self.tree[i] = S[i] - S[i - (i&-i)]
        if issum:
            self.sumtree = [0] * (self.size + 1)
            Ssum = [0] + list(accumulate([CA[self.X[i]]*self.X[i] for i in range(self.size)]))
            for i in range(1, 1+self.size):
                self.sumtree[i] = Ssum[i] - Ssum[i - (i&-i)]
    
    def compress(self, L):
        #座圧
        L2 = list(set(L))
        L2.sort()
        C = {v : k for k, v in enumerate(L2, 1)}
        # 1-indexed
        return L2, C
    
    def leng(self):
        #今入っている個数を取得
        return self.count(self.X[-1])
    
    def count(self, v):
        #v(Bの元)以下の個数を取得
        i = self.comp[v]
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def less(self, v):
        #v(Bの元である必要はない)未満の個数を取得
        i = bl(self.X, v)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def leq(self, v):
        #v(Bの元である必要はない)以下の個数を取得
        i = br(self.X, v)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, v, x):
        #vをx個入れる,負のxで取り出す,iの個数以上取り出すとエラーを出さずにバグる
        i = self.comp[v]
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def get(self, i):
        # i番目の値を取得
        if i <= 0:
            return -1
        s = 0
        k = self.p
        for _ in range(self.dep):
            if s + k <= self.size and self.tree[s+k] < i:
                s += k
                i -= self.tree[s]
            k //= 2
        return self.X[s]
    
    def addsum(self, i, x):
        #sumを扱いたいときにaddの代わりに使う
        self.add(i, x)
        x *= i
        i = self.comp[i]
        while i <= self.size:
            self.sumtree[i] += x
            i += i & -i
    
    def countsum(self, v):
        #v(Bの元)以下のsumを取得
        i = self.comp[v]
        s = 0
        while i > 0:
            s += self.sumtree[i]
            i -= i & -i
        return s
    
    def getsum(self, i):
        #i番目までのsumを取得
        x = self.get(i)
        return self.countsum(x) - x*(self.count(x) - i)
verified

ネタバレ注意

Submission #5708437 - CPSCO2019 Session1
Submission #5709342 - AtCoder Beginner Contest 128
Submission #5710866 - AtCoder Beginner Contest 127
Submission #5711262 - AtCoder Grand Contest 005
Submission #5711745 - AtCoder Regular Contest 033
よく平衡二分探索木のverifyに使われているのを見る問題。PyPyでfastestだったので悪くないですね
Submission #5715765 - 全国統一プログラミング王決定戦本戦
流石にセグ木の方が速いですね

追記

fineさん的には名前があんまり気に入ってないそうです、 響きはともかく意味的にはpseudo multisetとかが近いでしょうか
setよりmultisetに近いですね

CPSCO2019参加記(3日目)

競プロ python cpsco

この前の
CPSCO2019参加記(２日目) - Tallfallの日記


の続きです。

3日目

最終日で前夜に飲み会があったということで参加者が半減位するかなと思いましたが結構人来てました。
この日は個人戦だけだったので気楽ではありました。

Session4

writerはチョコラスクさん、個人戦とあって難易度は控えめとのことでした(ほんとかなぁ～みたいに思ってました笑)
全体的にかなり必要知識が少なめでいいなぁと思いました。

問題文
 CPSCO2019 Session4

A - Swimming
長さLメートルのプールを往復しながら泳ぐとき、Xメートル泳いだ時の位置を答える問題。
格好つけて絶対値とか使おうと思ったら時間かかりました。

提出:
Submission #5285008 - CPSCO2019 Session4


B - Meeting
要約すると集合がD(10以下)個与えられるのでそのうち二つの和集合の要素数を最大化する問題。
こう書くとかなり簡単に見えますけど200にしては少し難しめかな？といった印象でした(趣旨的にはその方が良さそう)
NとDを逆にして実装しました。
提出:
Submission #5285153 - CPSCO2019 Session4


C - Make a Team
N人のレートRiが与えられ、チーム内の最大レート差がD以下になるようなチームの振り分け方を数える問題。
modの逆元使わなくていい所がいいですね。見てすぐはマッチングだと思いました。
問題文はちゃんと読もう!

提出:
Submission #5285387 - CPSCO2019 Session4

D - Boring Sequence
数列Aの要素をK個まで変えて同じ要素が連続する長さを最小化する問題、二分探索は比較的見えやすいかなと。
二回目の二分探索だったのでオンサイトの人たちはCが解けていたら大体解けていたのが印象的でした(逆に解けていなかったら次は大丈夫ですね！)
途中で二分探索する対象を間違えて最初に出したコードはKを使っていなかったという...(あほすぎた)
priority queue を使う別解は思いつかなかったです。すごい。

提出:
Submission #5285602 - CPSCO2019 Session4

E - ox Concatenation
与えられたoxooxxxoxのような文字列を与えられた文字列で作れるかを判定する問題。
かなり問題の意味が分かりやすく、解いている時は少しづつ階段を上っているような感じがして楽しかったです。
部分点のboolを持つdpは無駄なことが多いので添え字を一つ削減できる、みたいなのも典型要素で勉強になりました。

提出:
Submission #5286091 - CPSCO2019 Session4

F - Lost Tree
コンテスト中は残念ながら解けなかったです。木の頂点のある部分集合のすべての点対の距離が与えられるのでそれを復元する問題。
解いている時は木の直径みたいなのは出せるけどそこからどうしようかなぁみたいな感じで終わりました。
再帰という発想が出てこなかったのは反省ですね(絶対実装終わってないけど)
どんな時に他の頂点が必要かを考えると比較的ナチュラルな道筋で根から決めていくみたいなのが出るんすかねぇ。
面白かったです。

提出:
Submission #5415083 - CPSCO2019 Session4



A~Dは問題の意味を理解してからほぼすぐに解法は生えてるのに全て実装で詰まって時間をかけたのは本当に改善したいところです。ペナ込みでDまで44分は流石に遅すぎる(実装するだけなのにの意)。
Fすき

Session4が終った後表彰式があって(優勝された方のアカウントはなんとrated未参加(黒)らしい...)、そののちに解散となりました。
終わった後梅田でてんぷらさんラスクさん煎茶さんと寿司としゃぶしゃぶを食べました、優勝できてよかったです。
帰りに蟻本を買いました、鯵本はなかったです。





三日間本当に楽しくて実りのあるイベントでした！主催とwriter陣には本当に心から感謝です。参加者の方々もほぼ初対面の方ばかりでしたけど競プロerは優しいですね...皆さん有難うございました。
来年あればwriterお手伝いできるくらいには強くなっていたいものです。

CPSCO2019参加記(２日目)

cpsco python 競プロ

昨日(一週間前のこと)の
CPSCO2019参加記(1日目) - Tallfallの日記
の続きです。

2日目

この日は本当に眠かった。例え4時に終わるコンテストだとしても4時に寝れる訳ないんですよね。

2日目位になると人見知りの僕でも色んな人と話ができました、同チームになった人と運営と同大以外だとくるさんとかnadareさんとかしいさんとか（他にもたくさんですが割愛）ですね、なんだかんだ緑～青の人と話すことが多かったです、次あったらそうじゃない人とも色々話したいですね。

話していて少し意外だったのは皆さんAtCoder以外はそこまで出ていないということでした、まぁ時間が日本向きではないですものね。Codeforcesの過去問バチャとか立てたら人集まるでしょうかね、需要あるなら自分のペースメーカーにもなるしやりたいですね。

さて、はにーまさんの買ってきたお菓子を食べていたら(チョイスが良かった)チーム分け後すぐにSession2が始まりました。人来るの結構待ってんのにあの速さで割り振りできるの凄い。

この日は記憶が死んでるのでところどころ変なこと書いてるかもしれません、すいません。

Session2

writerはゴジラさんとやむなくさん、ゴジラさんは会場で二人しかいない元々お会いしたことのある人でした（学部で結構有名でしたし）。やむなくさんはTwitterで見たことあるくらいでしたが強そうなオーラが出てました笑。

チームはpmh(それぞれの頭文字)、調べたら既往歴って意味らしいです。

問題文
 CPSCO2019 Session2

A - Scholarship Repayment
奨学金を返す問題、実際のシステムと同じらしい、面白い。実際にN-1月でどれだけ払ったかを求めて、Mから引いたのが答えです。
はにーまさんがAC

提出:
Submission #5304809 - CPSCO2019 Session2


B - Telephone Q
知ってる人少なそう。「こんばんはゴジラです」、普通に災害では？
＋かーか*が書かれたパネルを開けていき、書かれた数字だけ対応する操作をする問題。
(a \geq 0), b\geq 1, c\geq1 \Rightarrow (a+b)c \geq ac + b
なので+0は無いも同然だから+全部取って*全部取るのが最適、コーナーケース(?)の*0がサンプルにおいてあって優しさを感じました。
はにーまさんがAC

提出:
Submission #5304825 - CPSCO2019 Session2


C - Delicious Burgers
美味しいハンバーガーを作る問題、各文字列の隙間における括弧の深さを求める問題に帰着できます。そういう時は(を+1,、)を-1に置くといいって誰かが言ってた。担当僕でしたが最初誤読してて閉じた括弧の中にしか|を置けないと思って2WA、死ぬほど焦りました。問題文はちゃんと読もう!

提出:
Submission #5304857 - CPSCO2019 Session2


D - Two Piles
これ好き、ゲームの問題。二つの山から合計が片方の山にあるコインの数になるようにとっていき、取れなくなったら負け
なんか見た感じ偶奇っぽいので(和とか差をとって変化しない状態量になりやすい)少し考えると奇数奇数はめっちゃ弱そうみたいなことやただ0,0の時は負けだからうーん？ってなってました。1,Xの状態を考えれば一発だったっぽいです。
pelnoさんが通してくれました。

提出:
Submission #5304877 - CPSCO2019 Session2


E - Mogu Mogu Gummi
制約がO(n^{2}) で間に合い、かつ木の問題で部分木の情報をもっておけば解けそうなので二乗の木dpかなと思いました。ただ実装したことなかったのでaisingの奴ちゃんと復習しておくべきだったと結構後悔しつつ(その時まだレート1000とかだしまだ早いとか考えた気がする、駄目駄目でした)実装を進めることにしましたが残念ながら時間切れでした、流石に解くべき問題だったかなぁとは思います。DとEでそんな崖にはならないはずだった難易度差なんじゃないすかね。

提出:
Submission #5304962 - CPSCO2019 Session2

F - Treasure Collector
コンテスト中は見てません。
任意の列か行についてロボットがただ１つ存在する正方形のグリッドをなんやかんやする問題。
解説を聞いてから解き始めたので、燃やす埋めるだということはわかっていました。ただコインをとる方法が二個ちょうどだったり制約が小さかったり、複雑にそれぞれのコインの取り方の条件が絡んでいるのでフロー使いそうだなとは思ってた気がします。
まぁ実装は一回しか(むる)やったこと無かったんでコンテスト中に通すのは無理でしたね。
(コイン)Aが縦(向きでロボットに取られる)ならBも縦\iffBが横ならAも横
が成り立つのが面白いですね。少し込み入った場合分けの時はelse使わない方がミスらないんじゃないかということを学びました。

提出:
Submission #5333709 - CPSCO2019 Session2


G - MSTX
これ面白い、辺の重みが変数になっているグラフのMSTをクエリ毎に答える問題。コンテストの序盤でちらっと見たんですけど、結構悩んでもしかしたらクエリ先読みして少しずつ頂点をマージしていくのかな、とか最初から変数辺以外をまとめて尺とりかなーとか適当なことを考えました。自力ACしてたら気持ちよさそうですね。
x=0でも使う辺は絶対使うので最初からつなげておいた状況で定数辺(この場合c=0の意)のみでクラスカル法を行います。u, vを結ぶコストwの辺に着目するとこの辺で初めてuとvが連結になった時、この辺が予め使われていなかったことを考えると、
この辺が実際に使われる\iff x\geq w
ということが分かります。これらの情報を使うと二分探索でクエリにO(log{N})で答えられます。

提出:
Submission #5380237 - CPSCO2019 Session2




個人的にはめちゃくちゃ勉強になったセットでした。チーム戦としては2WA生やして300しか通してないので悲しくなりました。

さて、解説の後すぐSession3が始まりました、もう死ぬほど眠かったです。

Session3

Nキチさんとぺいさんとでした、水緑緑でいい感じでした。Nキチさんとは初日にそこそこ雑談してました。この回については記憶が半分くらい無く、本当に他の二人には申し訳無い限りです。

writerはけんちょんさんでした
やっぱり頭文字には気づかなかったです

A - ASOKO
文字列のAとOを入れ換える問題、言語によって色々違うらしくて面白いですね、pythonだと文字列はイミュータブルなので少し面倒ですね。
ぺいさんが通してくれました、流石に速かったです。
提出:
Submission #5380680 - CPSCO2019 Session3


B - Balloons
手持ちの風船からM個選ぶ、この時色の種類を最小化したい！という問題。
ソートして大きい方から選べば良さそう、複数のクエリに答えるわけではないのでそこから累積和して二分探索とかはやらなくて良さそう。
ぺいさんが通してくれました。

提出:
Submission #5380727 - CPSCO2019 Session3


C - Camp Reception
一次元の区間が挙げられてその連結成分の個数を数える問題。sとtの大きさがO(n)しても間に合うのでテーブルを作って[s, t]を塗りつぶして塗られてないところで分ければ良さそうです、imosで世界を変えられるので世界を変えるとAC出来る(解説見てないと意味不明ですね)
もしs,tがもっと大きいならSession1のFみたいにしてキューが空になる度答えをインクリメントすれば良さそうです(提出はこっちです)。
NキチさんなんとFA!つよい

提出:(かなりギリギリでびっくり,whileが遅いのかな？)
Submission #5380851 - CPSCO2019 Session3

D - Decode RGB Sequence
はい戦犯は僕です。
かなり難しそうな第一印象で、必要条件を列挙するくらいしか思い付かなかったです(RGBと塗られたところから左右に見ていくみたいな実装も考えたけどあのときの頭じゃ実装無理なので...）
で、普段はこういうことしないんですけどプレッシャー等で取り敢えず投げてみると4WAでそのあと少し変えて3WAだったのでその事を伝えてチームメイトに任せました。十分性を証明できぬまま出したので結構後悔と反省してます(証明が間違っていた時との心理的な差がよく分からない。)
割と十分性は非自明だと思うんですけどどうやったらコンテスト中に素早く分かるんですかね...
そのあと条件を厳しくしてぺいさんが通してくれました。（本当に感謝）

提出:
Submission #5381069 - CPSCO2019 Session3

E - Enumerate Xor Sum
戦犯2。
タイトルが凄い怖かったです、400詰まって問題眺めてたら取り敢えず桁毎に見れて、その時の1の個数だけ見れば良いのと遷移が簡単だと言うことには気づきました。ただその実装ができる気がしないのと(この時半分夢の中でした)pythonで通るか微妙な計算量(実際一回TLEした、流石にこちらが主理由)だったこともあり、C++でこんな奴書いて欲しいみたいな事になったんですけど僕の説明が下手すぎました...本当に申し訳ないです。
コーラをがぶ飲みして少し目が覚めたのでpypyで通しましたが遅かったですね。
(本当にすいませんでした)

提出:
Submission #5381097 - CPSCO2019 Session3


F - Flexible Permutation
戦犯3。
順列Pの元の位置との大小が指定され、それを数え上げる問題。
残り３０分位から見始めました。
位置が変わらないのは(前もって掛けとけば)無視していいことにはすぐ気づけて残りは大きいのと小さいのだったのですが。dpの遷移が見えず(変えたくないのは絶対位置なのを考えると出さないといけない発想な気はする)挙げ句の果てに
「うーん、何か挿入dpとかでは無さそうだしdpじゃないかもなぁ」
とか言ってたのでチームの足引っ張りまくりでした。とてもとても反省してます。
次例えば順列PのP_i \geq P_{i+1}となるiの数が与えられる数え上げとかの問題が出たときは流石に詰まりたくないですね。
貰うdpで考えると楽そう。

提出:
Submission #5383848 - CPSCO2019 Session3


G - Grand Election
コンテスト中は見ていません
見事に嘘解法に引っかかりました。O(X\log X)解まではあってたんですけどそこからの高速化で嘘を踏んじゃいました...
pythonには有理数型があるんでそれをheapqに乗せて(乗るの知らなかった)実装した所当然TLEしたので、今度はfloatで実装すると誤差で2WA出しちゃいました。decimal使おうかなぁとか結構考えて(多分どうせ遅い)結局 lcm(lcm(1,2,3...100), \sum{A})　を分母にした所何とか通りました。疲れました。

提出:(褒めてほしい)
Submission #5385325 - CPSCO2019 Session3



反省の多いセットでした。
チーム名がI_am_yojoとかいう天才でしたね、Nキチさんの案でした。

という事で翌日自分のパフォーマンスが落ちると人に迷惑がかかるときはこどふぉにでないと心に誓いました。

解説の後２日目が終了、なんとはにーまさんが結構赤字らしいという話になります。カンパの募集があったんですけどもっと多く払うべきでした、今度会ったときに何らかの何かはしたいと思います。

懇親会は色んな話が出来て楽しかったです、けんちょんさんの腕の中で寝かけました笑
けんちょんさんと指相撲をしました、勝ちました。

電車で一人になったとき周りが引くくらい激しく船を漕いでいたようです。
家に帰って歯磨いて即爆睡しました。

つづきます。
CPSCO2019参加記(3日目) - Tallfallの日記

CPSCO2019参加記(1日目)

競プロ python cpsco

こんにちは、まつかわです。

 

はにーまさんが参加記を読みたいと仰っていたのでブログを始めることにしました。

 

5/4 ~ 5/6 の3日間、はにーまさんの主催する競プロ合宿のCPSCO2019があったので

時系列に沿ってつらつらと書いていきます

 

参加前

大阪で競技プログラミングの勉強会があるとTLで見かけたので参加登録をしましたがレート帯的に色々考えました。強い人がその後めっちゃきたので考えるのをやめました。

1日目

割と早めに会場に着いて雑談をしていました、その後会場に入りましたが居心地がとても良さそうな空間だったのでテンションが上がりました()。

Session1

作問人(さくもんちゅ)はてんぷらさんでした、まだ黄色表記ですね。

全体的に難度勾配がなだらかでかつ教育的だったなぁと思います（これは全部の回でそうだけど特に）

問題名の頭文字には気づきませんでした。

問題文:

 CPSCO2019 Session1

感想は使用言語に準拠してpythonで書きます。

A - Ajihon

N人を3人ずつのチームに分けるとき、A冊の鯵本を所有するチームを最大、最小化する問題

切り上げは-(-A//B)とかの形で書けます。mathからceil()とって来た方がバグらせないかもしれないですね

いかなごさんが解いてくれました。

提出:

https://atcoder.jp/contests/cpsco2019-s1/submissions/5291010

B - Beautiful Harmony

令和問

文字列の出現回数の種類が１かの判定問題

出現回数ならCounter使っておくのが便利で、これはdictなのでvalues()をsetに入れて長さが1かどうかを見ます、pythonが輝きそうな類の問題。

いかなごさんが解いてくれました(2回目)

提出:

https://atcoder.jp/contests/cpsco2019-s1/submissions/5291066

C - Coins

N(<=30)個のものからK個(<=6)選んでなんだかんだする{}_nC_k問題

てんぷらさんの解説の通り実装すると楽

（この記事を書いている時next_permutaionに引っ張っれてpermutaions()で書いてTLEしたのは内緒）

本番の担当は僕で、実装めんどいなぁとおもったら煎茶さんが再帰で書いてくれてpythonでTLEしたので唯一のc++ユーザのいかなごさんに書いてもらうことに

いかなごさんが解いてくれました(3回目)

提出:

https://atcoder.jp/contests/cpsco2019-s1/submissions/5291556

 

 D - Dessert Planning

mod = 10**9+7
print(8*pow(5, int(input())-1, mod)%mod)

 

おわり。

 

真面目に書くと

煎茶さん担当でした、dpはすぐに思いつきたい問題で、ケーキを食べて終わる通り数とそれ以外のを持つと遷移が

\begin{pmatrix} dp_{cake}[i+1] \\ dp_{other}[i+1] \end{pmatrix} = \begin{pmatrix} 2 &3 \\ 6 &5\end{pmatrix}\begin{pmatrix} dp_{cake}[i] \\ dp_{other}[i] \end{pmatrix}

となって結局求めたいのは\{dp_{cake}[n] + dp_{other}[n]\}なのでこれのi項目を dp_{tot}[i] とおくと dp_{tot}[i+1] = 8dp_{tot}[i]となります。

提出(いる？):

https://atcoder.jp/contests/cpsco2019-s1/submissions/5291698  

Ｅ

pythonの標準ライブラリにc++のsetをくれ(言語選択で敗北)


19/05/31追記
BIT上の二分探索すると通るようです
オフラインクエリのset実装 - Tallfallの日記



F - Fruits in Season

特徴量に対して単調に範囲が増加する部分列に対する問題。

最小値の最大化なので二分探索は筆頭候補に出て、それでなんか行けそうなので見ていくと判定パートは1~Nがそれぞれ別の部分列に含まれるようにできるかどうか？みたいな感じになります。この判定が多分本質パートで類題の解法から終点か始点ソートかなーとは考えてたんですけどheapqに終点を順次入れることに思い至るまで少し時間をかけすぎた気がします。で、思いついたら結局日経コンのＤ

https://atcoder.jp/contests/nikkei2019-final/tasks/nikkei2019_final_d

のpython解と同じじゃーんってなったので復習不足を感じました。（自分はセグ木の伝播を最後だけするようにして通してた）

なお範囲を決めるところ（算数）をバグらせて通ったのは終了3分後でした（は？？？？）

二分探索は判定を関数化した方がよさそう。

提出:

https://atcoder.jp/contests/cpsco2019-s1/submissions/me

 

G - Game with Division

部分点300その2

部分点解法が満点解法の愚直版になっている。

iゲーム目でXが始め書かれている時、それ以前はこれ以降影響しない(マルコフ過程的なイメージ）のでdpは解法候補として上の方になる。茶色とかの人がやると凄いいい感じの練習になりそう

満点は例えば貰うdpを考えたときもらうノードは O(\sqrt{a})で抑えられるので何とか貰うノードに対して定数かO(\log{n})くらいで処理を抑えたい、よく考えると同じiに配るノードは区間になっているのでSegtreeで高速化すると通ります(8TLEくらいした、前問でバグを防ぐためにceil, floorを使おうという意識が仇(?)になった、てんぷらさんはこれを予想していた....？)

本番ではFの実装詰まった時に気分転換で部分点を通しました、他の人にやってもらった方が合宿の目的には合っていたかもしれないですね、ただそれをするとレートチーム内で一番高かったのにもかかわらず何も通さない人になるのでやっちゃった(かわいい)

提出:

https://atcoder.jp/contests/cpsco2019-s1/submissions/5297662

 

H - Highest and Ends

コンテスト中は見てないです

部分点300その3

数列Aに対して l \leq m \leq r 　かつ　 A\lbrack l\rbrack + A\lbrack m\rbrack + A\lbrack r\rbrack = X 　かつ　 max_{i \in\lbrack L, R\rbrack} = A\lbrack m\rbrack を満たすl, m, rを求める問題です

部分点はよくある300っぽくて[l, r]全列挙を高速化するやつです、session4のCはこれを復習してたら解きやすそうでしたね。

lを固定した時rに対してmaxが単調になるのを使って尺取りみたいな感じしょうか。

満点解法は...少なくても今の自分からは出てこない奴でしたね、この数日前にDisjoint Sparse Tableの記事を読んだからと言って解法が生えるほど頭良くないです、地道にやるしかないですね。テーブルを毎回生やしててTLE食らいまくりました。

本番中はいかなごさんがC++パワーでO(n^{3})で通してくれました、定数倍軽いしね。

ということでいかなごさん、900点稼いでます、僕の3倍です。

提出:

https://atcoder.jp/contests/cpsco2019-s1/submissions/5300115

 

チーム戦は初めてでしたが非常に楽しかったです。自分がもう少し頑張れてれば結構いいとこ行けたかもですね、他の人には申し訳ないです笑

 

解説の後にこの日は解散しました。

 

1日目の帰りに蕎麦を食べました、美味しかったです。

AGCに出ました、Ａで2TLE吐きました。楽しかったです。

こどふぉに出ました、眠かったです。(期間中最大のミス、次の日死んでた)

 

長くなったので分けます。

 
CPSCO2019参加記(２日目) - Tallfallの日記