halcの競プロ精進ブログ

はるくが競プロしたことを書き留めるなにか

【今日の精進】ARC127C - Binary Strings

競プロ 今日の精進 ARC 黄Diff

毎日格上の問題を倒すやつの84日目です。

問題リンク

atcoder.jp

問題概要

1,2,\dots,2^N-1 を二進数で書いたものを辞書順に並べたとき、X 番目に来るものを答えてね。

解法

上から決めていくと、空文字列か0になるか1になるかを判断する必要がありますが、これは引き算さえできれば容易です。

しかし、多倍長整数は普通に遅いので間に合いません。

ところで、X は二進法で与えられます。

これをうまく扱えば、必要な引き算は素早く行うことができます。

提出コード

from collections import deque
N=int(input())
X=deque(input())
if len(X)==1:
    print(1)
    exit()
cnt=0
while X[-1]=="0":
    X.pop()
    cnt+=1
X[-1]="0"
for i in range(cnt):
    X.append("1")
while len(X)<N:
    X.appendleft("0")
ans=["1"]
for i in range(N):
    if X[0]=="1":
        ans.append("1")
    else:
        cnt=0
        while len(X)>0 and X[-1]=="0":
            X.pop()
            cnt+=1
        if len(X)==0:
            break
        X[-1]="0"
        for i in range(cnt):
            X.append("1")
        ans.append("0")
    X.popleft()
print("".join(ans))

Submission #48462217 - AtCoder Regular Contest 127

感想

気づいた時感動した

【今日の精進】ARC125D - Unique Subsequence

競プロ 今日の精進 ARC 黄Diff

毎日格上の問題を倒すやつの83日目です。

問題リンク

atcoder.jp

問題概要

A から連続とは限らない部分列を取り出す方法であって、取り出し方が一意に定まるものの個数を求めてね。

解法

  • dp[i]=i 番目の要素を必ず選ぶ通り数

とします。そこで、遷移を考えましょう。

ある数が動かせてはいけないので、A_i と同じ数があるところまでの和と、その間で 2 種類以上あるものは一番後のものを考えていい感じにやれば良いです。

更新と区間和取得のできるものがほしくなりますが、まあどうとでもなります。

提出コード

class BinaryIndexedTree():
    def __init__(self,default=0):
        self.size=0
        if type(default)==int:
            self.size=default
        else:
            self.size=len(default)
        self.bit=[0 for i in range(self.size+1)]
        self.stan=[0 for i in range(self.size)]
        if type(default)!=int:
            for i,j in enumerate(default):
                self[i]=j
    
    def __setitem__(self,pos,val):
        add=val-self.stan[pos]
        self.stan[pos]=val
        pos+=1
        while pos<=self.size:
            self.bit[pos]+=add
            pos+=pos&(-pos)
    
    def __getitem__(self,pos):
        if type(pos)==int:
            return self.stan[pos]
        else:
            left=pos.start
            if left==None:
                left=0
            right=pos.stop
            if right==None:
                right=self.size
            return self._sum0(right-1)-self._sum0(left-1)
        
    def _sum0(self,right):
        pos=right+1
        ret=0
        while pos>0:
            ret+=self.bit[pos]
            pos-=pos&(-pos)
        return ret

MOD=998244353
N=int(input())
A=list(map(int,input().split()))
last=[-1]*(N+1)
dp=BinaryIndexedTree(N+1)
dp[0]=1
for i in range(N):
    dp[i+1]=dp[last[A[i]]+1:i+1]
    dp[i+1]%=MOD
    if last[A[i]]!=-1:
        dp[last[A[i]]+1]=0
    last[A[i]]=i
print(dp[1:]%MOD)

Submission #48440243 - AtCoder Regular Contest 125

感想

素直にDPできなかったなぁ

【今日の精進】ABC253G - Swap Many Times

競プロ 今日の精進 ABC 黄Diff

毎日格上の問題を倒すやつの82日目です。

問題リンク

atcoder.jp

問題概要

A=(1,2,\dots,N) があるよ。

1\leq x \lt y \leq N を満たす (x,y) の組のうち、辞書順で L,L+1,\dots,R 番目のものをこの順に見ていって、以下のようにするよ。

  • A の x,y 番目を入れ替える

最終的な A を求めてね。

解法

1 番目からキリのいいところまでを観察してみると、末尾の数列を反転させたものを先頭に写していると見れます。

そのため、この形で処理できるものは一気に処理します。

余ったものは、素直にシミュレーションすれば良いです。

提出コード

N,L,R=map(int,input().split())
lf=0
for i in range(N):
    lf+=1
    if L<=N-lf:
        lf=[lf,lf+L]
        break
    else:
        L-=N-lf
ri=0
for i in range(N):
    ri+=1
    if R<=N-ri:
        ri=[ri,ri+R]
        break
    else:
        R-=N-ri
A=list(range(1,N+1))
while lf[1]<=N:
    A[lf[0]-1],A[lf[1]-1]=A[lf[1]-1],A[lf[0]-1]
    if lf==ri:
        print(*A)
        exit()
    lf[1]+=1
if lf[0]+1!=ri[0]:
    A=A[:lf[0]]+A[-(ri[0]-lf[0]-1):][::-1]+A[lf[0]:-(ri[0]-lf[0]-1)]
for i in range(ri[0]+1,ri[1]+1):
    A[ri[0]-1],A[i-1]=A[i-1],A[ri[0]-1]
print(*A)

Submission #48415276 - NOMURA Programming Contest 2022（AtCoder Beginner Contest 253）

感想

めっちゃARCっぽいんだけど？

空いた日にやってたこと*1

80日目

x.com

*1:81日目忘れてたけど二次予選あったから許して…

【今日の精進】ABC235F - Variety of Digits

競プロ 今日の精進 ABC 黄Diff

毎日格上の問題を倒すやつの79日目です。

問題リンク

atcoder.jp

問題概要

N 以下の整数であって、すべての C_i を含むものの総和を求めてね。

解法

いわゆる桁DPです。

2^{10} 個の情報を持ち、それぞれに総和と個数を持っておきます。*1

時間が厳しそうな気持ちになりますが、祈れば案外間に合います。

提出コード

MOD=998244353
N=input()
M=int(input())
C=list(map(int,input().split()))
dp=[[(0,0)]*(1<<10),[(0,0)]*(1<<10)]
dp[0][0]=(0,1)
for i in N:
    i=int(i)
    aft=[[(0,0)]*(1<<10),[(0,0)]*(1<<10)]
    for j in range(1<<10):
        for k in range(i):
            if j==k==0:
                aft[1][j]=(aft[1][j][0]+dp[0][j][0]*10+k*dp[0][j][1],aft[1][j][1]+dp[0][j][1])
            else:
                aft[1][j|(1<<k)]=(aft[1][j|(1<<k)][0]+dp[0][j][0]*10+k*dp[0][j][1],aft[1][j|(1<<k)][1]+dp[0][j][1])
        if j==i==0:
            aft[0][j]=(aft[0][j][0]+dp[0][j][0]*10+i*dp[0][j][1],aft[0][j][1]+dp[0][j][1])
        else:
            aft[0][j|(1<<i)]=(aft[0][j|(1<<i)][0]+dp[0][j][0]*10+i*dp[0][j][1],aft[0][j|(1<<i)][1]+dp[0][j][1])
        for k in range(10):
            if j==k==0:
                aft[1][j]=(aft[1][j][0]+dp[1][j][0]*10+k*dp[1][j][1],aft[1][j][1]+dp[1][j][1])
            else:
                aft[1][j|(1<<k)]=(aft[1][j|(1<<k)][0]+dp[1][j][0]*10+k*dp[1][j][1],aft[1][j|(1<<k)][1]+dp[1][j][1])
        aft[1][j]=(aft[1][j][0]%MOD,aft[1][j][1]%MOD)
        aft[0][j]=(aft[0][j][0]%MOD,aft[0][j][1]%MOD)
    dp=aft
num=sum([1<<i for i in C])
ans=0
for i in range(1<<10):
    if i&num==num:
        ans+=dp[0][i][0]+dp[1][i][0]
print(ans%MOD)

atcoder.jp

感想

思ってたよりめっちゃ典型

*1:個数がないと総和を正しく計算できない

【開催記】yukicoder score contest 8 開催記 (番外編)

競プロ ヒューリスティック yukicoder 作問

コンテストを開催していたので開催記です。あまりしっかりしたものではありません。

注意

⚠️⚠️⚠️今回の問題設定はフィクションです！！⚠️⚠️⚠️

普通に犯罪なので唐突に破壊衝動に駆られても町の建物を爆破させてはいけません！！！

そもそも爆発物の所持・製造・使用もすべて犯罪です！！！！

死刑、無期または7年以上の禁固・懲役に処される重罪です！！！！！絶対に真似しないように！！！！！！*1

開催したいきさつ

実は、6月ごろからyukicoderでコンテストを開催したいとやんわりと思っていました。

その後、だいぶ間が空きますが9月ごろにyukicoderのスコアコンテストの開催経験があるお二方と話す機会がありまして*2、yukicoderのスコアコンテストは思ったより需要があることがわかったので開催することを決意しました。

まあ特に深い理由があってのことではないですが、楽しんでいただけたのであれば幸いです。

問題作成

爆弾ですべてを破壊するネタはなんかのゲームをやってた時に降ってきました。とりあえず大本はG - Strongest Takahashiを参考にして作りました。*3

当初は、「10*10マスを爆破」「上下左右を爆破」「×印のように爆破」のように考えていましたが、たぶんあんまりおもしろくないかなと思い、爆破の形をランダムにしました。

また、最初は「すべての建物マスをカバーする配置を見つける」だけのものを考えていたのですが、要素はある程度多い方がいいかなと思ったので、はるく君をスポーンさせました。移動のコストについてはB - Garbage Collectorの形式が良いと思いそのまま採用しました*4。爆弾をもちすぎるとコストが大きく、だからと言って小分けに買いすぎると爆弾屋が全滅する可能性もあり、けっこうちょうどいい塩梅になったと思っています。*5

実はこのネタは10月に思い付いたもので、6月には別の案があったのですが、6月に思い付いたものは競技性に欠けそうだったこと、ビジュアライザが単調になって盛り上がらなさそうだと思い没になりました。*6

問題ページを作成するにあたり、No.5017 Tool-assisted Shooting - yukicoderを大きく参考にしました。この場でplatinumさんに感謝申し上げます。

ビジュアライザの作成は、先述の問題の形式と同じようにSiv3Dでやろうともしたのですが、どうしてもPythonに慣れてしまったのもあって、Pythonで完結させたいと考えていました。

そこで、pygameというモジュールに行きつき、調べまくって何とか完成させました。実装にあたり、100ターンごとに状況を保持しているので、100000ターンもあるとさすがに重いです*7。

難易度がやや高いこと、昼に参加しにくい人も参加してもらいたいことを考えて期間は3日間としました。金曜のコンテストがつぶれるという相当なむちゃぶりなのに対応してくださったyukiさんには感謝です。

問題への言及

えっ、怖い…*8

爆弾屋を破壊すると罰金も考えましたが全部壊す方が面白そうだったので却下しました。

注...彼は特殊な訓練を積んでいます。

治安が終わっておりますね…

解法

writerの想定解

0を出力するだけのものも一応正当な解です。50点

サンプルコードはすべての建物を壊しているので、得点が跳ね上がります。9,148点 しかし、あまりにも無駄が多くこれを改造しても得点が上がる望みは薄いです。

思いつきやすいであろう貪欲は、「一番壊せるところを壊すことを、全て壊れるまで繰り返す」です。はじめに爆弾を買い込んでこれを行うと比較的良い点数が取れます。1,637,160,602点

writerの最高得点は、これを4分割した区画それぞれで行う方針です。1,739,837,672点

絶対爽快だけどコンテスト的にはあまり得点は高くなく…

ちなみにContestantの方の中では以下のが一番近いと思います。

Testerさんの想定解

tester 解は適当に貪欲しただけです

とのことです。貪欲で2G超えられるのすごい…

参加者さんの解

だいたいここから見れます。

どうやら上位の方は爆破のさせ方は貪欲で移動経路を焼きなまし等で決めているそうです。復習しないと…*9

今回の問題については、iiljjさんの以下の発言が最も的を射てると思っています。

コンテスト中

1日目

初めのうちはあまり参加者が来ないとは予想していましたが、まあそれは予想通りでした。

開始2時間でsample.cppに軽微なミスがあったのを指摘されました。反省。

あんま時間ないし順当に1.5G程度の貪欲解が出て終わるかなと思いきや、 まさかのW/Tともに1日目でbin101さんとwanuiさんに抜かされました。何事…

爆弾所持歩行コストがバカにならないとは思っていましたが、まさかここまで影響があると思っておらず…

2日目

W/Tともに複数人に抜かされました。

wanuiさんとbin101さんが首位争いをしており、見ていて楽しかったです。

また、このころから数名ビジュアライザを共有してくれました。ありがとうございます。

3日目

ここまで正直言ってあんま参加者数が伸びず心配だったのですが、この日は潜伏勢がめちゃくちゃ沸いて昨日上位だったメンツが軒並み抜かされていました…

bowwowforeachさん、rhooさん、Kiri8128さんが首位争いに参加しており、少し見れば首位が変わっていてめちゃくちゃ熱い展開でした。*10

また、当初は想定もしていなかった2.9Gが出てしまいました。私の解より1.7倍くらい効率的なの怖い…

結局rhooさんがぎりぎり勝ちました。あらためておめでとうございます。

感想

たくさんの方に参加していただけて、何より無事に終われてよかったです。Clarがほとんどなかったのもよかったです。

期間が普段より長く、ゲームバランスとかを少し心配していましたが、最終日にも多々良い解が出たので結構期間はちょうどよかったと思っています。金曜日がつぶれるのはさすがにあれなので同じ形式でまたやるとしたら土日になりそうではありますが。

改めて、コンテスト開催の場をいただいたyukiさん、Testerのjupiroさん、先駆者のplatinumさん、参加者の皆様に感謝申し上げます。本当にありがとうございました。

*1:参考:爆発物取締罰則(バクハツブツトリシマリバッソク)とは？ 意味や使い方 - コトバンク

*2:どれだけ意味があるかはわかりませんが名前は伏せておきます

*3:ただしこの問題は解けてません（え？）

*4:ただしこの問題も解けてません（はい？）

*5:はるく君が破壊する理由も最悪すぎてそこも気に入っております

*6:yukicoderの問題をいい感じに出題する設定

*7:ただ洗練されたものは割とすぐ終わると思ったので気にしないことにしました

*8:あなたが始めた物語ですが!?

*9:writerさん?

*10:なおwriterは下半分…

【今日の精進】CF17-FINALF - Distribute Numbers

競プロ 今日の精進 AGC 橙Diff 企業コンテスト

毎日格上の問題を倒すやつの78日目です。

問題リンク

atcoder.jp

問題概要

N 枚の紙があって、K 個ずつ数字を書くよ。

このとき、1,2,\dots,N が K 個ずつ出現したうえで、各紙に共通する数字はただ一つにする必要があるよ。

K は自由に、N は1000から2000の範囲で自由に決められるとき、これを実際にやって見せてね。

解法

とりあえず、N=K(K-1)+1 にする必要はあります。

そうしたら、1 を書く紙を固定し、それらにすべての数を書いたうえで、それ以外はうまくスライドしていくとうまく数字を書けます。

ただし、K は素数+1である必要があります。

提出コード

from collections import deque

#N=1057,K=33
K=38
N=K*(K-1)+1
print(N,K)
ans=[[] for i in range(N)]
ans[0]=list(range(1,K+1))
for i in range(N-1):
    ans[i+1].append(i//(K-1)+1)
cnt=K+1
for i in range(1,K):
    sw=deque(range(cnt,cnt+K-1))
    for j in range(K-1):
        ans[i].append(cnt)
        cnt+=1
    now=K
    for j in range(K-1):
        for k in sw:
            ans[now].append(k)
            now+=1
        for k in range(i-1):
            sw.append(sw.popleft())
for i in ans:
    print(*i)

感想

こういう構築いいね

【今日の精進】ABC244G - Construct Good Path

競プロ 今日の精進 ABC 黄Diff

毎日格上の問題を倒すやつの77日目です。

問題リンク

atcoder.jp

問題概要

グラフが与えられるよ。

いくつかの頂点は奇数回、それ以外は偶数回通るような長さ 4N 以下のパスをひとつ出力してね。

解法

存在が保証されている構築問題は、極端な場合を考えると良いことが多いです。今回の場合は木です。

木のことを考えると、BFSしながらその道中で偶奇があってなければ寄り道すればよいことがわかります。そうすると、各辺は高々4回しか通らないのでよさそうです。

根だけは調整できるスペースがありませんが、根から初めて根で終わる前提ですから、偶奇があってなければ最後に行ったのをなかったことにすればよいです。

一般のグラフの場合も、雑に全域木をとって同様にやればよいです。

提出コード

from sys import setrecursionlimit
setrecursionlimit(1<<19-1)

class UnionFind():
    def __init__(self,size):
        self.uf=[[-1,0,1] for i in range(size)]
        
    def unite(self,fir,sec):
        one=self.root(fir)
        two=self.root(sec)
        if one!=two:
            if self.uf[one][1]>self.uf[two][1]:
                one,two=two,one
            self.uf[one][0]=two
            self.uf[two][2]+=self.uf[one][2]
            if self.uf[one][1]==self.uf[two][1]:
                self.uf[two][1]+=1
    
    def same(self,fir,sec):
        return self.root(fir)==self.root(sec)
    
    def root(self,node):
        pos=node
        change=[]
        while self.uf[pos][0]!=-1:
            change.append(pos)
            pos=self.uf[pos][0]
        for i in change:
            self.uf[i][0]=pos
        return pos
    
    def size(self,node):
        return self.uf[self.root(node)][2]

def dp(pos,bef):
    global ans,cnt
    for i in gr[pos]:
        if i==bef:
            continue
        ans.append(pos)
        cnt[pos]+=1
        dp(i,pos)
    ans.append(pos)
    cnt[pos]+=1
    for i in gr[pos]:
        if i==bef:
            continue
        if S[i]!=cnt[i]%2:
            ans.append(i)
            cnt[pos]+=1
            cnt[i]+=1
            ans.append(pos)

N,M=map(int,input().split())
gr=[set() for i in range(N)]
union=UnionFind(N)
for i in range(M):
    u,v=map(int,input().split())
    if not union.same(u-1,v-1):
        union.unite(u-1,v-1)
        gr[u-1].add(v-1)
        gr[v-1].add(u-1)
S=list(map(int,input()))
ans=[]
cnt=[0]*N
dp(0,-1)
if cnt[0]%2!=S[0]:
    ans.pop()
print(len(ans))
print(*[i+1 for i in ans])

Submission #48234259 - AtCoder Beginner Contest 244

感想

私りーふさんの問題に惹かれる特性でもあるの？*1

*1:「良問だったなー」→「りーふさんかい」の流れ、冗談抜きで十数回経験してます