CodeForces #266_Div2 : B. Wonder Room

「† 注意力 † コンテスト」バチャの問題

Problem - B - Codeforces

n, a, bが与えられるa'>=a, b'>=b, a'b' >= 6nを満たす最小のa'b'とそのときにa', b'を求める問題

まず、a<bとすると、明らかにa'<b'とできる。(aで小さい方、bで大きい方を作ってそれぞれa', b'とする)

この後、a<b、a'<b'とする。

ai²< 6nとなる範囲でaiを探索する。aiに対して、bi=Max(b, ceil(6n/ai))としてあげればaiを固定したときに6n以上のaibiの最小値になる。

ai²>=6nのとき、明らかにaibi>=6nなのでこの範囲の最小のaiについてだけ試す。

上記で試した全ての中で最小のaibiが答え。

Educational Codeforces Round #83 参加記録

Dまで4完でした。Eは解法もあっていたのですがつまらないバグを残してしまいダメでした（泣）。

A Two Regular Polygons

N%Mが0かどうか。

B Bogosort

リストを並び替えてi-aiがすべて異なるようにすればいいです。 aiを降順に並べればi-aiは狭義単調増加になります。

C Adding Powers

A=a1...an はゼロ埋めされたリストでB=b1...bnが与えられます。 k^I をajに足す操作を各iに対して高々1回行って A=Bとできるかという問題

b1...bnをk進数で表したときに各桁の値が1 or 0にならないといけないです。 また、同じ桁が1のbjが2つ以上あってもダメです。 それ以外の時はYESです。

結構迷った印象ですが時間を見ると10分で解けていて成長を感じます。

D Count the Arrays

問題 : M以下の数字を使って長さNのリストを作る。重複する数はちょうど1つになるようにする。 また、あるjが存在してi<jならai<aj、j>iならai>ajとなる。 このようなリストの数を数える。

ちょっと迷いましたが出来ました。使う数字を決めます。重複1なので数字の種類数はN-1なのでcombination(M, N-1)。 重複させる数を決めます。それがN-1個の数の中で最大の数なら構成できないので決め方はN-2通り。残りの数(最大の数と重複させた数以外のN-3個)が最大の数の左右どちらにあるか決めます。2^N-3

これらをかけたら終わりです。

N=2の時がコーナーケースです。1WA またcmbinationを事前計算しておくとMLEしてしまいました。pypyでなくpythonで出すことで通りましたが、何か改善策を考えておかないといけなさそうです。 この問題に合計25分くらいかかったようです。

E Array Shrinking

「隣り合う同じ数字をくっつけて1増やす」を繰り返してどれだけ列を小さくできるかという問題です。 通せなかったのが本当に悔しい。

a1, a2, a3, a4, ... an とあるときに連結できる範囲をあらかじめ計算してしまいます。

a1, |a2, a3, a4, a5|, ... an

とあってa2からa5をくっつけて1つの値にできるかを調べましょう。 なお、できる場合はその値はどのような順序で連結しても同じ値になります。（適当に試せば証明可能と思います）

|a2], |a3, a4, a5|

がそれぞれ１つの値になって、さらにそれぞれが同じ値なら良さそうです。 なので|a2 .. ai| と|ai+1...a5|につて予め計算しておいて全部試せば全体が１つの値になるか、またどのような値になるかがわかります。

長さ１の区間 n個について初期化しておいて、次に長さ2の区間n-1個について、...という風にdpすればいいです。

具体的な配列は次のようにします。 dp1[i, j] = 範囲 i, j を１つにすると値は何になるか。1つにできないなら-1

これがあればdp2[x] = 1...axをみたときの列のサイズの最小値 が計算できます。

dp1の計算量は雑に見積もればN³で、500³なのでTLEしますが、実際のループ関数はそれよりも大分少なめです。（オーダーはN³のままです）

しかし、本番ではTLEしてしまいました。 理由はdpをタプルからintへの辞書を使ったからです。 なのでタプルをencodeしてintにしてから計算！

これでTLEは解消できましたが、dp2の初期化にバグがありWAが取れませんでした。 本当に単純なバグだったので悔しいですが反省点は次のようなものです。1. pythonを使っているのならTL厳しいのは当たり前。タプルをencodeするなどの書き方を固定してストレスなく高速化できるようにする。2. シンプルでバグりにくいコードを書きましょう！　

最終コードは以下です。

N = int(input())
X = list(map(int, input().split()))
from collections import defaultdict
dp1 = defaultdict(lambda :-1)
M=1001
def ec(i,j):
    return i*M+j

for i in range(N):
    dp1[ec(i,i+1)] = X[i]
for i in range(2, N+1):
    for j in range(N-i+1):
        for k in range(1, i):
            u, v = dp1[ec(j,j+k)], dp1[ec(j+k,j+i)]
            if u != -1 and v != -1 and u == v:
                dp1[ec(j,j+i)] = u+1
                break

dp2 = [N]*(N+1)
dp2[0] = 0
for i in range(N):
    for j in range(i+1):
        if dp1[ec(j,i+1)] == -1:
            continue
        dp2[i+1] = min(dp2[i+1], dp2[j]+1)
print(dp2[-1])

AtCoder ABC158 メモ

ABCDを解きました。水色パフォでした。今週はコドフォも含めて全体的にいつもより順位が低めでした。練習の仕方に問題があるのかも。

D String Formation

後ろから解きました。Dequeと使うのが簡単なようですが私は最終的な文字列の長さ分リストを用意しておいて、前に置くときはX[i] = x;i+=1;後ろに置くときはX[j] = x;j-=1のようにしました。 Dequeは最終的な長さがわからないときにこそ有効と思っているのですが、バグの元なので多少オーバーキルでもDequeを使ったほうがいいかもしれないです。

E Divisible Substring

わかりませんでした。かなり難しく感じます。modがなお苦手なんだなあという感想です。終了後、解説通りにACしました。 mod系の問題をたくさんといて克服したいです。

F Removing Robots

Fにしては簡単だった気がします。Eを早めに見切りつけてれば解けた気もします。 終了後、自力ACしました。 各ロボットの位置をソートして添字を振り直します。各ロボットiの位置はX1, X2,...Xnになります。

1. 各ロボットiが直接影響するロボットの区間はi+1..Ciとなるはずです。Ciを求めます。

2. 後ろからdpします。dp[i] = ロボットi...Nだけについて考えて最終的に残るロボットの数です。 これはdp[i] = dp[i+1] + dp[max(dp[i+1:Ci + 1])]で更新できます。（１つ目の項はiのスイッチを入れなかったときで、2つめはスイッチを入れたときです。それぞれiがいないかいるかなので独立で足せます。）

1でCiを求めるために苦戦してしまい間に合いませんでした。 xi, xi+diを混ぜてリストに入れて、ソートして順に見ていってxj+djが来たら直前のxに相当するiをC[j]=iとして計算。という風にしていました。 以下コードです。

class SegTree:
    def __init__(self, init_val, ide_ele, seg_func):
        self.segfunc = seg_func
        n = len(init_val)
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        # k+1ではなくkでは？
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
import sys;input=sys.stdin.readline
mod = 998244353
N=int(input())
X = []
Y = []
for _ in range(N):
    x, d = map(int, input().split())
    X.append((x,d))
X.sort(key=lambda x:x[0])
for i, (x, d) in enumerate(X):
    Y.append((2*x,i,0))
    Y.append((2*x+2*d-1,i,1))
Y.sort(key=lambda x:x[0])
C = [0]*N
for x, i, t in Y:
    if t==0:
        j = i
    elif t==1:
        C[i] = j
st = SegTree(C, -1, max)
dp = [1]*(N+1)
for i in range(N-1, -1, -1):
    y=st.query(i, C[i]+1)
    st.update(i, y)
    dp[i] = (dp[i+1]+dp[y+1]) % mod
print(dp[0])

Ciを求めるパートは単に二分探索の方が良かったかもしれないです。 二分探索でバグったことが多すぎて使うのを躊躇っている節があります。 二分探索使って書き直しました。

class SegTree:
    def __init__(self, init_val, ide_ele, seg_func):
        self.segfunc = seg_func
        n = len(init_val)
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        # k+1ではなくkでは？
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

def bsearch(mn, mx, func):
    #func(i)=False を満たす最大のi
    idx = (mx + mn)//2
    while mx-mn>1:
        if func(idx):
            idx, mx = (idx + mn)//2, idx
            continue
        idx, mn = (idx + mx)//2, idx
    return idx

import sys;input=sys.stdin.readline
mod = 998244353
N=int(input())
X = []
for _ in range(N):
    x, d = map(int, input().split())
    X.append((x,d))
X.sort()
C = [0] * N
for i in range(N):
    x, d = X[i]
    k = bsearch(-1, N, lambda j: X[j][0] >= x+d)
    C[i] = k

st = SegTree(C, -1, max)
dp = [1]*(N+1)
for i in range(N-1, -1, -1):
    y=st.query(i, C[i]+1)
    st.update(i, y)
    dp[i] = (dp[i+1]+dp[y+1]) % mod
print(dp[0])

Educational Codeforces Round 82 - E Erase Subsequences

解説ACした

絶対思いつかない天才解法だったのでメモ

ngtkana.hatenablog.com

これ通りに書いただけ。丁寧な説明なのに結構実装にも手間取った。 以下は実装。O(N³)の計算量。6.4*10⁷でpypyでは厳しいのでは？と思ったが余裕で通った。 こういうの本番では不安で出したくない。

T = int(input())
for ti in range(T):
    s, t = input().strip(), input().strip()
    N = len(t)
    for i in range(1, N+1):
        # t1 : [0,i), t2 : [i,N)に分割
        dp = [0]+[-1]*i
        for l, c in enumerate(s):
            for j in range(i, -1, -1):
                # dp[j] : cまで見てt1[:j]、t2[:k]を作るとしてkの最大値
                tmp = dp[j]
                # cをt2に使う
                if dp[j] != -1 and i+dp[j] < N and t[i+dp[j]] == c:
                    tmp = dp[j]+1
                # cをt1に使う
                if j != 0 and t[j-1] == c:
                    tmp = max(tmp, dp[j-1])
                dp[j] = tmp
        if dp[i] == N-i:
            print("YES")
            break
    else:
        print("NO")

Codeforces Round #621 + 622 参加記録

1日に２つあると大変ですね。疲れました。

# 621 (div2)はA, B, C1の３つ解けたつもりがC1がシステムテストで落ちました。 一行間違えて消していて直すと通りました（泣） ちゃんと確認しましょう！

#622 (div2)はA, B, C, Dまで解けたつもりですが現在システムテストの途中なのでわかりません。 DなどはTLEが怖いですね。

621-A Fast Food Restaurant

いきなり難しくてNo Subを考えましたが15分かけてACです。 a, b, cそれぞれ４以上なら同じなのでsortしてから手で全探索しました。もっと効率的な解き方がありそうです。。

621-B Different Rules

難しかったです。順位をよくする方は順位の和がa+b+1となる人をたくさん作る感じにしました。 悪くする方は順位の和がa+bちょうどになる人を増やします。下みたいな感じになりましたが自信ありません。（通ったけど）

print(max(a+b-n+1, 1), min(a-1, n-b)+min(b-1, n-a)+1+(a-1-(n-b) if n-b < a-1 else 0))

621-C1 Skyscrapers (easy version)

A, Bよりも簡単でした。（でも落ちた...）最も高くなる点を全探索します。１つ点を最も高い点として固定してそこから貪欲に左右に低くしていけばいいです。

621-C2 Skyscrapers (hard version)

ずっと考えてたけど解けませんでした。 最長増加列の話などと似ているのでsegtreeを使うのかなあとか、全てのビルをX以下にするとしてXを2分探索かなあとか考えていました。

終了後、以下のtweetをもとにACしました。

左右から累積和でみていって、例えば左から見るときは、1個前よりちいさければそれ以前を更新していく形で解けます。(愚直にやるとO(N^2)かかるのですが、stackを使うことでO(N)でできます)https://t.co/jnHNcXTL9d

— じゅぴろ (@jupijupi111) 2020年2月23日

すごいですね。O(N)だし。

beatとかいうデータ構造を使ってもACできるし、セグ木+2分探索でも解けるようです。（方法はわからない）

622-A Dead Pixel

簡単ですね。ただ英単語力的に苦戦しました。

622-B Home Coming

これも簡単でした。後ろからシミュレーションするだけです。621のABとはえらい違いです。

623-C Restoring Permutation

一応、証明っぽいものができたと思っていますが自信ないです。 １〜２Nの大きい方から見ていって、biに含まれる数 <= 含まれない数と常になっていれば構成可能で、ないなら-1です。 あとは貪欲に詰めていけばいいです。

624-D Recommendations

解法はすぐ思いついたのですがセグ木使うだけでも苦手なので時間がかかりました。 セグ木の用途はmaxを常にpopできるような集合を使いたいからです。 今回は重複ありだったので時間がかかりました。少し前のABCでも同じ苦戦をしているので早めに纏めておきたいです。 確かC++だとライブラリがあるのでこんなところで30分以上かけているのはとても不利になってしまいます。 その上、セグ木でこれを代用するのは遅いのでTLEが怖いですね。

具体的な解法は後で追記します。（眠いので）

624-E Double Elimination

泥臭くやればできる可能性もありそうだと思いながら、途中で心折れました。 見るからに実装が大変です。セグ木の実装とかで2分木の扱いになれればできるかな...

AtCoder ABC156 メモ

ABCDEを解きました。青パフォ上位なのは嬉しいですがF解けなかったのが悔しい。

D Bouquet

combination(n, a)のnが大きくaは小さいのでn(n-1)...(n-a+1)とa!を求めないと計算できないです。

E Payment

はじめ各部屋の人数がk以下の個数を数えようとして時間を溶かしました。 0人の部屋の個数iを固定して、どの部屋を0にするかnCi と 残りの部屋に1人以上割り振る方法で nCn-iをかけます。 iごとに足せば計算できます。(0<=i<=Min(N-1, K))

K=1だとi=0とできないですが制約的に関係ありません。

F Modularness

次のような方針を考え続けて時間を終えました。

各diごとに考える。aj (j=i mod k)がaj-1より大きくなる条件は？a0にsum(di) を何度か足してd0...di-1を足したものがaj-1。diを足すとaj。なので頑張ってmod m が1変わるjの個数を探す。 di + x*y < n mod m みたいになるX以下のxの個数を数えることができればこの問題は解ける。

twitterを見ると同じ方針で解こうとした人は結構いたっぽいです。 しかも解き方自体は存在するらしい！ ( https://twitter.com/maspy_stars/status/1231219562076459010 )

しかし、とても難しそうですね。解説pdf通りだと簡単です。丁寧な解説なのでここでは書きませんが上の方針を早めに捨てられていれば解けていたかもしれません。 modの式変形はどのような時に大変でどのような時は簡単なのか判別できる能力が必要と感じました。まずはmod式変形の勉強を進めていきたいです。

Codeforces Round #620 (Div1 + Div2) 参加記録

A, B, Dの３つ解けました。遅かったのでレートは下がりました。(1752 -> 1716)

A Cow and Haybales

苦手系です。割算を頑張りましょう。 こういう割算の算数系はそれほど難しくない割に時間がかかって本当に苦手です。

B Cow and Friend

ちょうどのものがあれば1です。目的地より遠くに飛べれば2です。 目的地より近くにしか跳べないなら、跳べる最長の距離で切り上げ除算です。

C Cow and Message

今見ると簡単ですが頭が混乱していて解けませんでした。 長さ2以下の文字が答えになるので長さ2以下の部分列をそれぞれ数えます。

D Cow and Fields

難しかったです。各special field Pi について始点からの距離と終点からの距離を計算しておきます。これはbfsでできます。 すると、Pi とPjを繋いだときの1-Nの最短パスはd(1, Pi) + d(Pj, N) + 1, d(1, Pj) + d(Pi, N) +1, d(1, N)のいずれかになります。（d(x, y)はつなぐ前のx-yの距離） あとはMin(d(1, Pi)+d(Pj, N), d(1, Pj) + d(Pi, N))が最大となるように(i, j)を見つければいいです。 全探索だとN**2かかるので工夫が必要です。私は以下のようにやりました。

d(1, Pi) をai, d(Pi, N) をbiとする。 ai<aj, bi<bjがあればai, biはいらないので消す。あとは(ai, bi) についてai < aj となるjを調べると最小のajの(aj, bj)を選べばいいことがわかる。aiでソートしてから隣り合うものについてMinを計算してMaxをとる。

以下はtwitterで見つけた賢い解法です。（こういうのって転載いいのかな）

にしても任意の(i,j)(i≠j)の組についてmin(A_i+B_j,A_j+B_i)の最大値を出したいみたいな時に

A_i+B_j <= A_j+B_i
を移項して
A_i-B_i <= A_j-B_j

なのでA_k-B_kの昇順にソートすると(i<j)についてminは絶対A_i+B_jになってこれは累積min使えば出来るってテク、頭から抜けてたな

— 物理好き@1点は大事!(素振り)文章力も大事!(素振り) (@butsurizuki) 2020年2月17日

D,d(1,A)<=d(1,B)が満たされているなら、d(A,N)+d(1,B)のパターンは見なくていい(d(A,N)+d(1,B)>=d(A,N)+d(1,A)>=元々の最短距離)ので、{d(1,A),d(A,N)}でsort

— heno (@heno_code) 2020年2月17日