yukicoder contest 311

　AB二完で終了。Cを考えていたら睡魔に誘われてしまった。

コンテストへのリンク

No.1658 Product / Sum

　解説AC。

　1でない個数を二個にして式変形してみると、解ける。

　解法を理解してから見ると、サンプル1が良い誘導になっているのが分かる。二変数にすれば良いんだ、と。

　コンテスト中は、一変数にしなくては厳しい気がして悩んでいた。

　サンプル1で、10*10 / (2*10) = 5 という式が見えてしまったのが良くなかったか。一般にはN = 2でA1 = A2のとき上手くいくとは限らないのは分かったけど、この式から変形してどうにかするのか、と。

　詰まったら別の方針を考えないとね。

No.1659 Product of Divisors

　コンテスト後、自力で解けた。

　が、公式解説で二項係数でやっているところを思いつかず、DP＋行列累乗で解いてしまった。

・DP[i] = pに関する指数が残りi個のときの場合の数

　として、そこから各dに何個振り分けるか？　というのをK回行った。

　まあNが小さいからこの解法で問題ないけど、最初二項係数でできるのでは？　と疑ったのに、解法を思い付けなかったのは良くない。

Codeforces Round #741 (Div. 2)

　途中寝かけたせいもあり、D1まででした。 

コンテストへのリンク

コンテスト後のツイート

D2. Two Hundred Twenty One (hard version)

　D1で、さらに取り除くindexを指定するもの。

　D1で（証明しなかったけど）偶奇さえあっていれば答えが得られた。ということは、ある区間の長さが奇数ならば、一つ削除することで全体を0にすることができる。なので、区間が偶数で0でない場合は、どこでも一つ削除してから考えて良い。

　あとは、立式することが重要。区間[l : r]からxを削除するとすると、Sを累積和として、

・S[l : x-1]+S[x]+S[x+1 : r]＝S[l : r]=kとする

・S[l : x-1]-S[x+1 : r]=0

　となれば良いので、計算すると、

・A[x]=1のときS[l : x]=k/2+1

・A[x]=-1のときS[l : x]=k/2-1

　となれば良いと分かる。

　なので、Sが条件を満たすもののうち、区間[l, r]に含まれるものを探せば良い。これは二分探索を使えばOK。

　なお、コンテスト終了間際に大体この考察には至っていたのだけど、その後ずっとACできなかったのは、「区間[l, r]に含まれるものを探す」という条件を忘れていたせいでした。[l, r]に含まれないものを出力して、なんでWAなんだろう……とずっと考えていた。ひどい。

Codeforces Round #740 (Div. 1, based on VK Cup 2021 - Final (Engine))

　ACの二完でした。Bは惜しくなかった。Dの方が惜しかったのかも？（ACしていないのではっきりしたことは言えないが）

コンテストへのリンク

コンテスト後のツイート

B. Up the Strip

　DP[x]がどこから足されるかを考える。

　引き算については、DP[1]～DP[x-1]の和を足し込めば良い。これは累積和でOK。

　割り算について。まず思いつくのは、$\sqrt{x}$で分ける方法だと思う。

　DP[x/1], DP[x/2], ... , DP[x/$\sqrt{x}$]はそのまま計算、$\sqrt{x}$より大きい数で割る場合は、それぞれの商について何個ずつかを求める。

　コンテスト中はこの方法しか思いつかなかった。

　これで、Div. 2の部分点はもらえるが、Div. 1では点数にならない。

　約数に注目するのが重要。

・(x-1)/yとx/yの整数部分の値が変わるのは、x/yが割り切れるとき

　ということに注目する。これを考えると、xの約数についてだけ、変化分がどれだけ増加するかを調べていけば良い、と分かる。

　が、これでも間に合わない（MLEになるはず）。

　そこで、発想の逆転。約数を考えていたところを倍数で処理できないか考える。

　DP[x-1]だった増加量がDP[x]に増えるのは、xの倍数のところである。それを利用し、xの倍数のところに、その増加量の変化を書き込んでいく。これなら、MLEを回避できる。

AtCoder Regular Contest 125

　Cまで三完でした。レートはやや下がったけど、ABで詰まって動揺してしまってもCを通せた、というのは良かった。

コンテストへのリンク

コンテスト後のツイート

D - Unique Subsequence

　解説AC。

　制約からDPを使いそうなこと、一意な部分列を得たいので、部分列DPみたいな考え方をしそうなことも分かる。

　だがそこから考察を進められなかった。

　そこから、公式解説に書いてある必要十分条件に至る部分は、どうにかして考察してたどりつかねばいけないように思う。難しいけれど、時間かければ思いつけた気もするし、どうだろう……。

　その後の実装はDPなのだけど、各数字について「その数字がでてきたindexたち」をメモしながら進めていくことがポイントか。

　そうやって実装したものを、Binary Indexed Tree で高速化すれば良い。

TopCoder Single Round Match 811

　Easy, Medの二問解けて黄色に復帰。

　Easyはあまりにも簡単で驚いたが、他の人がすぐ提出しているのを確認して、提出。

コンテスト後のツイート

Div1 Med SmoothDivisors 

　ちょっと実験したら、各素数について、その素数を因数に持つ約数が最低三つあればOKそう、と分かった。ので、p, qを素数としてp*q, p*p*qのときのみダメだろう、と。ちゃんとした証明はできてないけど、まあそうだろう、という気持ちで実装へ。

　ただ、Pythonでは間に合いそうにないので、C++を書くのに戸惑ってしまった。

　でもまあ、遅かったとはいえ、C++でちゃんとACできたこと自体が少ないので、ACできたことを喜ぼう。

yukicoder contest 310

 　A一完で終了。Aの後Dを考えていたけど、思いつかず、途中で考える気力が……。

コンテストへのリンク

No.1653 Squarefree

　解説ACしました。

　エラトステネスの篩の応用のようことしか使っていないので、解説を理解するのは難しくない。けど、こういう力任せ（？）のような方法はコンテスト中は考えられなかった。

　シンプルな問題だけに、もっと綺麗な（数学的な）方法がある気がしてしまった。

　強引にでも解いてやろう！　という気持ちになればこの方法を思い付くのはそこまで難しくない気もする（どこまで素数を列挙するべきか？　とか計算量まで分かるのは難しいかもしれないけど、できる限り列挙しておこう、みたいな気持ちでやるなら）。根性が足りなかった。

AtCoder Beginner Contest 213

 　Eまで五完。

コンテストへのリンク

コンテスト後のツイート

FはSA-ISを書かないとACできない。SA-ISを理解していないため後回し……。

G - Connectivity 2

　解説放送を聞いてAC。

　$3^N$のDPなのだけど、そこがポイントではなく、

・DP[S]=S内の辺についてみたとき、Sが連結になる場合の数

　とおいて上手くいくと気付くのが重要。

　こうおいてDPが回るというのも意外だし、これを使って答えが求められるというのもなかなか思いつかないし理解し辛い。

　なお、解説放送ではこれを使って答えをどう表すか、ということは前半の解説部分で話しておらずコードを書くところでそれに触れている。

　私は前半を見て理解したつもりになってコードを書きだしたもののそこで詰まり、結局解説放送後半部分も見ることになってしまった。DPの遷移と大体同じ考え方なのに、ピンと来なかったんだよねぇ……。

　ただ、こんな風に重複なく数える、というのは、部分文字列を走査するDPと考え方としては似ているか。

　重複なく数えるために「1と連結なもっとも小さい集合を見る」というのは、部分文字列を走査するDPで「次に現れる文字のうち一番近い文字を見る」というのと対応しているのだと思う。

H - Stroll

　解説放送を聞いてAC。

　分割統治FFTというのはこういう処理なのですね。

　解説放送では自己ループのみがある場合で説明しているため、道がたくさんある場合でどうすれば良いかちょっと戸惑ったが、各道ごとに同じ処理を行えば良いということで納得した。

　なお、再帰で通常通り書いたらTLEしたため、他の人のコードのFFTの実装を見たら、配列の長さが小さい場合は直接計算しているようだったので、（FFTのライブラリ自体は書き換えずにDPの遷移の処理を）配列の長さで場合分けしたらACできた。

　FFTライブラリ自体を書き換えた方が後々のためには良いのだろうけど、どれくらいで分けるのが良いのだろう。AtCoderのライブラリでは、「畳み込む配列のうち小さい方が60以下かどうか」で場合分けしてそうだけど、自分の実装でもこれが良いのだろうか。

Codeforces Round #739 (Div. 3)

 　Eが解けずに終了。

コンテストへのリンク

コンテスト後のツイート

E. Polycarp and String Transformation

　正しい解法は、

・後ろから見ると消した順番が分かる

・消した順番を利用すると、最初にあった各文字の個数が分かる。それを使うと、最初の文字が復元できる

・あとは十分性のチェック

　第一ステップの「後ろから見る」を思い付けなかった。

　前からでもできそうな気がしてしまうと、なかなか後ろから見よう、と思えなくなってしまう。ただ、前からやると普通は二乗かかりそう、というところで、考え直さなくてはいけなかった。

AtCoder Beginner Contest 212

　Eまで五完。

コンテストへのリンク

コンテスト後のツイート

F - Greedy Takahashi

　解説動画を見てAC。

　コンテスト中はGの方が解かれていたため飛ばしてしまったが、発想が難しい問題ではなかった。

　ただ、実装は結構しんどいね。

　あまり綺麗な実装を思い付けず、添え字でもミスってしまった。他の方のコードを見てこういう実装も勉強すべきかなぁ。

　→　ダブリング解法だと実装がある程度大変になるのは仕方なさそう。

　

G - Power Pair

　解説AC。

　解説の論理は理解でき、ACはした。が、しっくりきてないので解説動画を見たい。

　→　結構すっきりしました。

H - Nim Counting

　すぬけさんの解説動画を見てAC。

　ただ、アダマール変換については理解できていない……。

　とりあえず、

・愚直なDPによる解法

・xor畳み込みにより高速化できる

・アダマール変換の線形性を利用すると、等比数列の積の公式などを利用して計算できる。（線形性の証明は分かってないけど、定義から成り立ちそうな気はした）

　というあたりは分かった。

　分かっていないのはアダマール変換の部分。

　一桁の場合は解説動画通りなので分かるけれど、二桁・三桁に拡張していくというところがよく分からない。拡張するとどうしてこういう式になるんだろう……。

　いまだにFFTもピンと来てないし、畳み込みを理解するためにどうにかしないといけないんだよね。私でも理解できるような資料はないものか。

yukicoder contest 308

　全完でした。 yukicoderは（難しい問題が出るとそこで寝てしまったりするため）最近ひどい成績ばかりだったのでできて嬉しい。

コンテストへのリンク

コンテスト後のツイート

　ちょっと感想を。

　EもFもそんなに簡単とは思わないのに、こんなに解かれるんだなぁ、と驚きました。

　私には、Eは類題を知らなければ厳しかった気がしますし、FはHL分解のライブラリを持っていなければ厳しかった気がします。

　ただ、Fはオイラーツアーでもいけるらしいですね。それはちょっと考えたのですが、上手くいかない気がしてやめてしまった。オイラーツアーにはやや苦手意識があり、今回も気付けなかった（まだよく分かっていない）のは反省です。

2021 TCO Algo Regional Qualification 1

 　Easyで誤読＆実装方針をミス、解けたと思ったMedはシステムテストで落ちて0完。青に落ちてしまった。

コンテストの結果

コンテスト後のツイート

OlympicShooting

　これは読解＆実装問題。

・スコアの合計が高い方が勝ち

・同じなら、後ろから順に、25回ずつのスコアが高い方が勝ち。

・それも同じなら、より後でスコア獲得した方が勝ち。

　というのを実装する。

　最初、「25回ずつ」というのを読み飛ばして戸惑った。

　その後、上手い実装がないかと考えていたのが失敗（とはいえ、短くコードをまとめている人もいた）。多少時間がかかっても愚直に書けば良かった。

TreeTokens

　解法はすぐに分かり、それであっていたが実装でミスしてしまった。

　ROOTに駒がこないためには、ROOTの隣は1個しかあってはダメ。じゃあ、その隣は、というと、3個までしかあってはダメ。その隣は7個まで。さらにその隣は15個まで。

　つまり、ある頂点の駒が高々i個になるためには、その隣の頂点での駒は高々2*i+1個であれば良い。問題が直線状で、ROOTが端にあれば、N＝（頂点数-1）として、2^N-1個が答えになる。

　では分岐があったときは？　というと、葉が深い方の枝に駒を増やしていく（2*i+1倍していく）のが最善。もう一つの分岐は、駒1個からまた増やしていく。

　そういう感じで、各頂点について「葉までの距離のmax」を前計算した後、ROOTの方がから木DPをしていく感じに解いた。

　……のだが、「葉までの距離のmax」の前計算する箇所で間違えた。

　これはよくある木DPなので、トポロジカルソートの逆順に見ていけば良いのだが、なぜかDFSみたいにしてしまっていた。

　焦っていたとはいえ良くない間違いでした。

　システムテストを通ったコードです。
 

mod=1000000007
 
class TreeTokens ():
    def placeMax(self, N, G, L, seed):
        state = seed
        E=[[] for i in range(N)]
        for i in range(1,N):
            state = (state * 1103515245 + 12345) % (1<<31)
            tmp = (state // 1000) % L
            p = max(0, i-1-tmp)
 
            E[i].append(p)
            E[p].append(i)
 
        #print(E)
 
        ROOT=G
 
        QUE=[ROOT] 
        Parent=[-1]*(N+1)
        Parent[ROOT]=N # ROOTの親を定めておく.
        TOP_SORT=[] # トポロジカルソート
 
        while QUE: # トポロジカルソートと同時に親を見つける
            x=QUE.pop()
            TOP_SORT.append(x)
            for to in E[x]:
                if Parent[to]==-1:
                    Parent[to]=x
                    QUE.append(to)
 
 
        CC=[-1]*N
 
        for x in TOP_SORT[::-1][:-1]:
            if CC[x]==-1:
                CC[x]=1
            if Parent[x]==ROOT:
                continue
            CC[Parent[x]]=max(CC[Parent[x]],CC[x]+1)
 
 
 
        AC=[0]*N
        AC[ROOT]=0
        
        ANS=0
 
        QUE=[ROOT]
        while QUE:
            x=QUE.pop()
 
            MAX=-1
            if len(E[x])==1 and x!=ROOT:
                ANS+=AC[x]
                ANS%=mod
                
            for to in E[x]:
                if to==Parent[x]:
                    continue
                MAX=max(CC[to],MAX)
 
            USE=0
            for to in E[x]:
                if to==Parent[x]:
                    continue
                
                if CC[to]==MAX and USE==0:
                    USE=1
                    AC[to]=(AC[x]*2+1)%mod
                else:
                    AC[to]=1
 
                QUE.append(to)
                
        return ANS%mod