perarduaadastra

競技プログラミングとかをしています

AtCoder Regular Contest 155 反省

あまりに久々

 

寒暖

冷え

500: 120:56(2)

 

 A - ST and TS Palindrome

ついぞわからなかった!!

S に対して、条件を満たす T は一意に決められて、その手順もわかった。だが K がでかすぎる。

絵を描いてみると、T は S の降順、昇順、降順…… になることがわかる。あとは T の後ろらへんの一致判定をやっていたが、判定すべき範囲がわかっていなかった。なんか K がでかいときのやつが小さいときのやつに帰着されないかなあと思っていたが、具体的な方法論まで進めることができなかった。

KMP 法に途中浮気しかけたけど戻ってこれた。えらい。

 

えらくない部分は、A に 90 分使ってやっと B に行ったこと。

 

B - Abs Abs Function

li-chao tree か?やめてくれよ。。。とか思ったりもしたが、絵を描いてみたらすんなりわかった。W 字の関数になるが、これを V 字 2 つと考えても最適解の都合上問題がないのだった。

BIT にぶたんでもいいんだが、面倒なので sorted set を借りてきた。

if set.ge(b): res = min(res, abs(set.ge(b) - b))

みたいなのをかいていて、set.ge(b) == None のときをケアしていたが、このコードは set.ge(b) が 0 の時も弾いてしまってペナ。

A = B の入力を入れてみて気付けたが、sorted set を使う時の注意点としておこう。

 

ムーブ

まず、30 分以上詰まるとか、泥沼に嵌り出したら他の問題も見てみよう。極端に難易度の離れたものでなければ解ける可能性がある。本当は「解ける問題から解く」が最適なんだけど、考察を始めないと解けるかどうかはわからないから難しいよね。

詰まったら腕立てするとかしてリフレッシュする、みたいのはまあ一般的に使えそうだ。

 

まとめ

良くはないが、0 完しかけたところから 1 個取れたのはよかった。B を見に行くのが残り 10 分とかだったら冷静に考察できなかったかも。

ところで、レートが 1900 を割ってしまったのですが。。。ABC バチャを走りまくって速解き力をつけようね。

AtCoder Beginner Contest 231 反省

なんか解ける問題ばかりが現れてうまくいった。

 

結果を鑑みて

2600 83:20

54位。rated内では4位。青落ち黄色だからrated内4位と言ってもそんなでもないかも。最近研究関連でごたごたばっかりだったのでメンタルがぐちゃぐちゃだったけどなんとか精神統一できた。

 

A - Water Pressure

やる。ひっかけがないかびくびくしながら提出した。

 

B - Election

なんか既視感がある。試験管difficultyの頃の問題で出てたかも。Counterでやるだけ。

 

C - Counting 2

身長の同じ生徒がサンプルにないのがちょっとこわい。bisect_leftを使う。

 

このあたりで順位は400位ちょっとくらいだった。ひとつひとつ確認しながら解いていたが、なんとなく今回は速解き回だったりしないだろうか?と思ったりした。そうなるとちんたら解いてたら危ない。

 

D - Neighbors

閉路があるとまずいと思った。一瞬、二部グラフかな?とか考えたけど閉路だけが問題らしかった。

サンプル2を見ると、次数の制約に気付く。これでたぶん必要十分だろうと思ったが、順位表でペナっている人を見つけてちょっと念入りに確認してから出した。

 

この時点で100位ちょっとだった気がする。

 

E - Minimal payments

わっかんね〜こんな問題があったかもしれないなと一瞬思ったけど思いはどこかへ飛んで行った。

上から貪欲にやっていくタイプか?とか考えたけどお釣りがどうにも扱いづらい。

 

結局F→G→Eで最後に解いた。

 

ある硬貨で支払った時に残り支払う金額がマイナスになったら、マイナスになった分はおつりになる、ということに気付いた。「おつり 桁dp」とかでぐぐってABC155-Paymentにたどり着いた。

Paymentは上の桁から見ていってギリギリの金額で支払うか、ちょっとだけ多めに支払うのが最適という戦略らしかった。

今回の問題で、硬貨の金額をxとして、X-xが負になるなら、-(X-x)<Xの時に限りお釣りをとったとして(すでにお釣りで考えているなら本来支払うべき金額として)遷移することにした。

計算量に自信はなかったが、剰余を取りながらXを小さくしていっているのでお釣りはよくわからないが計算回数は60回くらいで済みそうだった。

 

出してなんとか通った。ふう〜

 

F - Jealous Two

EがわからずFにきた。

問題文がちょっと読み取りづらいが、(a, -b)について二次元ソートしてあげると、i≦jなるindex i, jを使って、a[i]≦a[j]が成り立つからその中でb[i]≧b[j]が成り立てば良いことに気付いた。これは転倒数そのもの。

 

しかし、サンプル2でa,bペアの値がそれぞれ等しいやつがあると数え漏れが出ることに気付いた。後からこれを補填してAC

 

この時点で2桁順位だったはず。

 

G - Balls in Boxes

積の和典型。しかもNの値から、DPでやるタイプだとわかった。

白いボール、黒いボールがあって、箱1個につき黒いボールが1個割り当てられると考える。

O(N^2)が許されているが、dpに何を持たせるか?と考えた時、既に i 個の箱には黒いボールが割り当てられていると考えるのが妥当そうだった。

そこまでいくと、dpである必要はなくて、既に i 個の箱に黒いボールがあるなら N - i 個の箱にそれぞれ黒ボールを割り当てるため、K個のボールのうち N - i 個を黒ボールにして箱にあてることにする。順列の計算は前計算できそうだけどしなくても間に合う。

 

通すと30位くらいだった どひゃ〜

 

H - Minimum Coloring

MCFっぽいけどフローが分かれちゃったりしてうまくいかなかった。

分流してしまってまずいときは双対とって分圧にする みたいのがあった気がするけど思い出せなかったしそもそも正しいのかわからず。

 

 

総括

Fがすぐわかって、Gも積の和だったからよかった。Eで詰まってもじっくり考えれば解ける問題だったし、ABCでは解ける問題を探しに行くのが本質な気がしてきた。

積の和はいままで「積の和だ!」とわかっても解けなかったからうまくいってよかった。フロー も「フローだ!」とわかったら解けるようになりたいね。

AtCoder Regular Contest 131 反省

なんかあたたまった

 

結果を鑑みて

1200 29:46

298位。解かなきゃいけないのを解いてあったまった。Dさっさと捨ててもよかったかも。

 

A - Two Lucky Numbers

まあふたつ繋げればいいんじゃないか?とまず直観する。

A + B / 2 * 10^k

という形にした。2倍したときにAの部分が繰り上がるとまずいので間に0が挟まるように10の冪乗倍する。

 

通る。

 

B - Grid Repainting 4

4色定理?とか思ってた。

まあふつうにやって塗れそうなので塗る。通る。

 

この時点で100位くらい。

C - Zero XOR

xor battle に似てるなあと思った。

まず、初手で勝てる場合を先に処理した。

 

制約がでかいから基底とって何か考えるのかと思ったけど、基底の個数回はゲームが続きそう?とか思った。結局、基底の個数関係なくてN回続くかも、と思った。(ただのエスパー)

 

みんなすいすい通してるから、証明できていなかったが誘惑にあらがえず出すと通った。う〜ん。

 

D - AtArcher

明らかに、射った場所で一番中央に近いものを決定するとその後の射るべき場所は一意っぽかった。つまり、交差Dの等差数列になる。

どうせ単峰性あるだろ!→ない

 

これで1時間つかって、どうしようもなくなってE行った。

 

E - Christmas Wreath 

3で割って2余るやつはどう考えても無理。

5以下はだめそうで、6も手で解こうとしたけど無理になったからprint("No")してみた。

WAの数から、6以上の場合は3で割ってあまりが2以外なら全部構築可能なことがわかった。

 

6のときは無理やり全探索で構築できたので、そこに貪欲に頂点を足してみた。だめだった。

 

この時点でタイムアップ。

もう少し考えたいね。

 

 

 

総括

Cまではまあよかった。Dにさっさと見切りをつけてEに行くべきだったかもしれない。ムーブにケチつける部分があるとしたらそのくらいか。600点で未証明エスパーを投げるのは本来は良くないが、今回は順位表のこともあるからいいか。

 

 

累積和のダブリングと二分探索並行ダブリングと。












冷えたご飯と昨晩の残り物の野菜炒め、それから卵焼きの入った弁当。
一晩冷蔵庫に入れておいたからか、冷蔵庫の食材の香りが混ざっているようだ。




机においたスマートフォンに目をやりながら黙々と食べる。

右手の箸で食物を口に運び、左手でスマートフォンをスワイプ。

他人と歓談することなく食事をしていれば、自然とペースは早まるものだ。昼休みが始まってまだ10分と経っていないが僕は食事を終えて教室を出た。




高校2年生になって半年経った冬。タイミングを逃したというか何というか、僕はクラスに馴染めずにいた。
昼休みに教室にいても、スマートフォンをいじっているか寝たフリをしているくらいしかすることがない。
そんなことだから、最近は学校の敷地内にある人気のない中庭で時間を潰すことにしていたのだが……。


「予報では曇りだったんだけどな……」


廊下の窓を伝う雨粒。
僕はそれを見て溜息をついていた。


1時間ほど前から降り始めた雨のせいで、今日は中庭には出られないのだ。
中庭には出られない。かといって今から教室に戻るのも何だか気が重い。


静かで、知り合いに会わなくて済むような場所。校内に他にあるだろうか?



     ◇ ◇ ◇ ◇ ◇



静寂。昼休みが始まって間もないからか、他に図書室に来ている生徒はいないようだった。


図書室に入ると、僕は入り口から一番遠い席を目指した。
ここなら廊下から漏れてくる雑音はほとんど聞こえない。その上、暖房の効きも良くて快適だ。





僕はスマートフォンを静かに取り出してブラウザを開いた。
昼休みの暇つぶしとして、最近は「競技プログラミング」というものに取り組んでいる。
競技プログラミング」はプログラミングで数学の問題を解く競技で、巷では「競プロ」などと呼ばれたりしている。


僕がブラウザで見ているのは競プロの問題が書かれているページだ。
この問題ページにはソースコードを書くスペースが用意されており、ここに解答のコードを書き込んで提出することができる。



「う〜ん……。動的計画法っぽいんだけどなあ」


ぶつぶつと呟きながらあれこれとコードを書き換える。
コードテストを繰り返してバグを見つけてはコードを直す作業。


何かに熱中していると、気まずい人間関係のことを考えなくて済む。
ここは僕の聖域だ。少なくとも、飽きるまでは。





――図書室でコーディングを始めてから10分以上が経過した。
デバッグを進めてはいるが、プログラムがなかなか思うように動作しない。
今回の問題はかなり手強いらしい。


 10^6 って事は、多分 線形時間で解けるんだよな」


そんなことをぼそっと呟いた時だった。


「――あのっ!」


不意に後ろから声をかけられた。


「それって競プロ、ですよね?」


振り向くとそこには女子生徒が立っていた。上履きの色を見るとどうやら1年生らしい。
長く艶やかな銀髪と、白磁のような肌が窓から差し込む光を受けて輝いている。
彼女は、誰が見てもわかる美少女だった。


「え、あ、はい。そう、ですけど」


変な反応をしてしまった。


「私も競プロやってて、この学校で他に競プロしてる人見たの初めてだったからつい。……すみません、問題を解いているときに」

「あ、いや、大丈夫ですよ」


確かに僕も自分以外で競プロをやっている人間を見るのは初めてだ。見かけたら声をかけたくなる気持ちもわからないでもない。
競プロなどというマイナーな趣味を持っている人など校内にそうはいないはずだから。



――だから、僕はこのとき柄にもない提案をした。


「あ、えーと、今やってる、問題、見ます?」

「いいんですか?」


彼女の翡翠色の目がきらりと輝く。
どうぞ、と隣の席を指すと、彼女はぺこりと頭を下げて席についた。


「私、1年の青木翠って言います」

「あ、うん。よろしく」


僕も自己紹介を済ませると、スマートフォンを僕と翠の中間の位置に移動させた。



ふたりで小さな画面を覗き込む。

仄かに鼻腔をくすぐる石鹸のような爽やかな香りにドキッとする。

……ドキッじゃない。問題を見るだけなんだから。

深呼吸をして雑念を取り払うと、画面に目を落とした。




問題文は以下のようになっていた。

 1 ~  N の番号が付いたお菓子が入ったお菓子セットがある。お菓子にはそれぞれに体積が設定されている。
食べたお菓子の体積の合計がちょうど  V になるようにお菓子をいくつか選んで食べる。
お菓子セットの数が  k のときにちょうど食べたお菓子の体積の合計が Vになるように食べる方法の数を  f(k) として、 f(1)+f(2)+…+f(K) 998244353で割ったあまりを出力するようなプログラムを作成せよ。

ただし、セットが違えばたとえ同じ種類のお菓子であっても区別される。

制約:
 
1 \leq N, V\leq 2000, 1\leq K\leq 10^6


「あの、これ、動的計画法だと思うんだけど、なんか、計算量が合わなくて……。 K=1 だったら、ふつうに動的計画法で解けると思うんだけど……。あ、下の方に僕のソースコード書いてあるので」


翠が問題文を読んでいる間に僕は自分の考察について喋る。
彼女はうんうんと相槌を打ちながら問題文を読んでいる。


……本当に考察が伝わっているんだろうか?

そういえば、僕はこの子の実力について何も知らなかった。
1年生みたいだし、まだ初心者かもしれない。
どのくらい競技プログラミングをやっているか、とか予め訊いておくべきだったか。




「私も、DPでいいと思います。多分解けたんですけど、解法についてはまだ話さない方がいいですよね」



その言葉を聞いて僕は耳を疑った。

解けた? もう?

僕が初めてこの問題を読んだのは今朝のこと。今まで授業の合間にも考えていたから、合計で1時間以上は考えていることになる。それを、彼女は問題文を読んで1、2分の内に解いたというのか。


「え、本当に? これ結構難しいと思うんだけど。計算量とかどうなった?」

「んーと、 \mathcal{O}(NV+V^2\log{K}) とかですかね?」

 \log{K} って、二分探索するってこと?」

「二分探索とはちょっと違うんですけど……。話してもいいんですか?」


 \log{} がつくアルゴリズムと言えば、ソートや二分探索、セグメントツリーというデータ構造の操作以外に思いつくものはない。自分で考えたいとは思ったが、昼休みも残り15分程度だし一回話を聞いてみることにした。


「じゃあまず、ダブリングってご存知ですか?」

「聞いたことないかも」

「繰り返し二乗法とか二分累乗法ってあるじゃないですか。 2^{8} 2^{4}\times 2^{4} として計算する、みたいなやつ。それと同じで、現在の自分の値を利用してぎゅーんっと先の値を計算できるようになるんですよ」

 x^{n} \mathcal{O}(\log{n}) とかで計算できるってやつだよね」

「そう、それです !!」


急に大きな声を出すのでびっくりした。
僕の表情を見て察したのか、はっとした表情をすると彼女は言った。――今度は適正な音量で。


「すみません、ここ図書室なんでした……。こしょこしょ喋りますね……」

「びっくりした……」

「うう……すみません。昔から熱中すると我を忘れてしまって……。気を付けてはいるんですけど」

「まあ、他に図書室きてる人あんまり居ないみたいだし、大丈夫だろ」


雑なフォローをする。

翠は周りに少し頭を下げてから、説明を続けた。


「えと、その、繰り返し二乗法っていうのがダブリングの一種なんです」

「ほう」

「同じ操作を何度もしなくてはいけないとき、『2回操作をする』とか、『4回操作をする』っていう操作を用意してあげることで高速化ができるんです」

「ああ、つまり『 2^k 回操作する』っていう操作が考えられれば、それを組み合わせて任意の操作回数のときの結果が計算できるんだ」

「理解が速いですね。『 2^k 回操作する』という操作は『 2^{k-1} 回操作する』の操作から作っていける、ということを意識すると楽に実装できますよ」


なるほど、使い所の多そうなアルゴリズムだ。覚えておこう。


「ん?待てよ。今回の問題だとお菓子のセットが増えるとその分遷移が増えるから、結局計算量が大きくなりそうな気がするんだけど」

 K = 1 の時のDP配列をそのまま遷移として利用するといいですよ」

「どういうこと?」


翠は机に人差し指を置くと、指先でいくつか仕切りの入った横長の長方形を描き始めた。
「目」という字を横に倒したような図だ。


「区切られたひとつひとつのセルがDP配列の要素です。左側がゼロ番目で、右側が  V 番目ですね」


一番左のセルから、右のセルに向かってすーっと人差し指を滑らす。


「最終的にできたDP配列は、1つのお菓子セットをつかってゼロからある体積になるまでお菓子を食べる方法の数を表していますよね」


そして今度は真ん中のセルから右のセルに向かって指を動かした。


「これは、例えば合計体積  x から初めて  x + V までDPしたとしても、得られる配列は同じのはずです」

「あ、っていうことはいちいち  N 個のお菓子についての遷移を考えなくても、DP配列自体がお菓子セット1個分の遷移になるのか」

「うんうん」

「お菓子は全て区別されるから独立事象の積事象になるわけだね」

「たぶんそんな感じです!」

「そして、この遷移の  2^k 回分を計算しておけばダブリングで  f(K) \mathcal{O}(NV+V^2\log{K}) で計算できるってわけか」


眼から鱗だ。DP配列自体を遷移にするという、一見すると計算量を改善しない操作がダブリングのための伏線になっているとは。

最初は初心者かもしれないと思ったが、この子は自分よりも競技プログラミングをやり込んでいるらしい。




 f(K) がダブリングできると、あとはちょっとした工夫で  f(k) の総和とか累積和も計算できちゃうんですよ」


そういえば計算しなければいけないのは総和だった。これもダブリングで計算できるのだろうか?

彼女は机に指でさらさらと数式を書いて行く。
g(m)=\sum_{k=1}^{m}{f(k)}


「紙とか持ってきてればよかったんですけど……わかりますか?  f(k) 1 から  m までの総和を  g(m) と定義しています」


読めはしそうだ。大丈夫だ、と伝えて話の続きを促す。

彼女は先程書いた式の下に新たに式を書いていった。
g(2m)=g(m)+\sum_{i=1}^{m}{f(m+i)}


 g(2m) ですね。ダブリングのためにはこれが効率よく計算できなくてはいけないです」

「うん」

 g(2m) は和に  g(m) を内包していますから  g(m) と残りの部分の和に分解できます」

「なるほど、  g(m) は既に計算されているとすると残りの和の部分の計算だけが問題だね」

「今回は演算が分配法則を満たしますから、 f(m) の部分だけシグマの外に出せるんです。今回の問題で言う演算  \cdot っていうのはDP配列を遷移にして計算する  \mathcal{O}(V^2) のパートの事ですよ」


そう言いながら更に式変形を行う。
g(2m)=g(m)+f(m)\cdot \sum_{i=1}^{m}{f(i)}


「更に、右側のシグマの中身は g(m) そのものですから」


g(2m)=g(m)+f(m)\cdot g(m)


「後はこの式に従って実装すればダブリングの前計算は終了です」

「すごいな……」

「前計算の結果を利用して実際にダブリングするときはちょっと式が違うんですが……」


――翠が続きを言おうとした時、授業開始5分前の予鈴が鳴った。


「……まあ、 g(m+d) に同様の式変形を行えば導けますから、やってみてくださいね」

「ありがとう。参考になったよ」

「ふふ、嬉しいです」


彼女は微笑んで言う。


「それじゃあ、ええと、もう行きますね。また面白い問題あったら教えてくださいね〜」


席を立って会釈をすると、彼女は銀色の長髪をなびかせて図書室を出て行った。



     ◇ ◇ ◇ ◇ ◇



――次の日の昼休み。

昨日に引き続いての雨天のため、僕はまた図書室で時間を潰すことにした。
昨日と同じで入り口から一番遠い席。


前の日と違ったのは、そこに先客が居たことだった。

澄んだ翡翠の瞳。
流れるような銀色が窓から差し込む青白い光に照らされて輝いている。

彼女は間違いなく昨日出会ったばかりの後輩――青木翠だった。


「先輩、こんにちは」

「あ、うん。こんにちは」


座るように促されて、彼女の向かい側の席に座った。


「あ、何読んでたの?」

「これですか? ――古文の教科書です。次の時間テストなんで」


もう大体覚えましたけどね、と 翠は自信満々の表情を見せた。
教科書を閉じると、彼女は昨日の問題について尋ねてきた。


「昨日のやつ実装できました?」

「結構時間かかったけどなんとかできたよ」

「よかったです」


そう言って微笑むと、彼女はスマートフォンを取り出して言った。


「昨日のやつとは別のダブリングの問題があるんですけど、やってみませんか?」

「どんなやつ?」


これです、と端末をよこして見せてくれた。

 1 ~  N の番号が付いたお菓子が  1 個ずつ入ったお菓子セットがある。お菓子にはそれぞれに体積と美味しさが設定されている。お菓子  i の体積は  v_i で、美味しさは  a_i である。
あなたはお菓子セットを好きな数だけ用意して、セット内のお菓子を食べることができる。ただし、食べたお菓子の体積の合計が  V 以下になるように食べなければならないとして、食べたお菓子の美味しさの合計の最大値と、それを達成するために必要なお菓子セットの最小個数を出力するようなプログラムを作成せよ。


制約:
 
1\leq N, V\leq 2000, 1\leq a_i, v_i\leq 10^9


「ナップザック問題かな。題材とかこの前のと似てるね」

「そうですね。この前のダブリングを思い出してもらうと、結構やりやすいと思います」


昨日の問題では、お菓子1セット分の遷移を使って、ダブリングで2セット分の遷移、4セット分の遷移……と計算していくことができた。そして、その累積和もダブリングで計算できるということだった。


「あれ、これは累積和必要?」

「今回は敢えて累積和を計算しに行かなくても大丈夫です。――この問題は前回の問題の遷移で  + \max{} に、  \times + に読み替えたような問題になっているので、普通にダブリングして大丈夫ですよ」

「ふーん、なるほど」


よくわからないが、普通にダブリングしていいらしい。

まず、セット数が1のときのナップザック問題を解いて、お菓子の合計体積が  v 以下のときの美味しさの合計の最大値を計算する。これを遷移と見てダブリングしていけば、セット数が  k のときの答えが高速に計算できる。

しかし……必要なお菓子セットの最小個数というのはどう計算されるのだろう?


「目一杯セット数を多くすれば美味しさの合計の最大値は得られそうだけど、セット数はどうすればいいんだろう……」


「……先輩は」

「本当に飲み込みが早いですね」


顔を上げて見ると、翠はにっこりと微笑んでいた。

僕は心臓が一瞬止まったような気がした。


雨空の色を拾って儚げに輝く白銀。吸い込まれそうな翡翠色の瞳。それとは対照的にやや赤みを帯びた頬。
彼女のその柔らかな表情は僕に向けられている――




「……先輩? どうかしました?」

「え? あ、ああ」


彼女に言われて、僕は自分がぼーっと彼女の方を見つめていたことに気付いた。
何でもない、と答えてスマートフォンの方に目線を落とす。

何か悪い事でもしたみたいに心臓が大きく鳴るのを感じた。



「……そういえば、セット数で困っているんでしたよね」


向こうはそこまで気にしていないらしい。安心。
――何に安心したのかは僕自身よくわからなかったが。


「あ、うん。今のままだと結局セット数を全探索しちゃいそうだから……」

「美味しさの合計の最大値は計算できるんでしたよね。セット  k 個の時とセット  k+1 個の時を比べて見ると何かわかる事があるかもしれないですね」


天井を見つめて少し考える。
セットが  k 個の時よりも、セットが  k+1 個の時の方が選択の幅が広いから良い答えを得られるはずだ。


「セットが  k+1 個の時の方が最大値は大きくなる。それか同じ値になるか」

「その通りですね。ということは……」


――二分探索だ。

我ながら冴えている。計算量的にもこれで  \mathcal{O}(NV+V^2(\log{V})^2) くらいになるだろう。


「計算量はどうなりますか?」

 V^2 が最大で  4\times 10^6 くらい、  (\log{V})^2 10^2 くらいになるから合計で  4\times 10^8 くらいの演算回数だね」

「このままでも通らなくはなさそうですが、ちょっと重たいですね」


今日のコンピュータはだいたい  10^9 までの演算回数であれば十分高速に処理できる。
この  4\times 10^8 という演算回数は目安で、複雑な実装になるほど実際の演算回数は多くなるので、結構ギリギリ、というか半分アウトくらいの計算量だろう。


 (\log{V})^2 \log{V} くらいになってくれたらうまくいきそうだけどなあ……」

「つまり?」

「えーと、二分探索とダブリングが並行できたらいい、みたいな?」


――そこまで言って思考が至った。
まず、美味しさの合計の最大値をダブリングで前もって計算しておく。ここからさらにもう1回ダブリングするのだ。

ダブリングする際にセット数  2^k の遷移を使うことになる。このとき、  k の大きい方から遷移の使用を検討していくことにする。
その遷移を使うかどうかは、前もって計算した値との比較で判定できるのだ。

セット数  2^k の遷移を使った場合に、お菓子の美味しさの合計の最大値が、前もって計算した最大値未満ならその遷移を使う。前もって計算した値以上なら使わない。

そのように遷移させると、美味しさの合計の最大値が前もって計算した最大値未満になる最大のセット数がわかる。これに1を足したものがセット数の答えだ。


「……ダブリングと二分探索を同時にできるのか。最大値を先に計算しておいて、ダブリングするときに大きいセット数の遷移から使っていけば」

「そうですね。お見事です。これでたぶん解けましたね」

「ふう、後で実装してみるよ」



ひと息ついて、スマートフォンを彼女の方に返した。


「さっきの問題のリンクとか送りましょうか?」

「うん」

「じゃあ、えーと連絡先とか交換してもいいですか」


僕はスマートフォンを取り出して、メッセンジャーアプリを開いた。


「あれ、なんか振ると友達に追加できるやつなかったっけ」

「それ廃止されましたよ」


そうなのか。聞けば廃止されたのは去年のことらしい。
彼女の端末に表示されたQRコードを読み込んで、連絡先を追加した。


「最初から連絡先交換してリンク送っておけばよかったですね」

「確かに……」





――時計を見ると、昼休みはあと10分。
翠がちらりとスマートフォンを見て言う。


「明日は晴れらしいですね」

「そうなんだ」

「先輩って普段から図書室にいるんですか?」

「いや、今日と昨日はたまたま雨だったから図書室に居ただけ」

「じゃあ、いつもお昼は外で遊んだりするんですか?」

「いや、中庭で……問題考えたりして過ごしてる」

「へ〜……外で考えるの気持ちよさそう」

「そっちは? 昼休みいつも何してるの?」


こうやって誰かと雑談するのは久しぶりな気がした。


「友達とだべったり……。先輩と同じでお昼に問題考えたりすることもありますよ」


雨が止んだら、ここへ来る理由もなくなって、きっとこうして話したり、一緒に問題を解くこともなくなるだろう。


「まあ、私はまわりに競プロやってる人がいないので、ひとりでぶつぶつ言いながら問題考えてるから、周りから変な人だと思われてそうなんですよね」

「そ、それならさ」



「雨じゃなくても、晴れの日でも、たまにでいいから、一緒に問題解かない?」


勢いで言ってしまったが、この言い方だと、何だか自分だけ必死すぎないか。
気持ち悪いと思われていないだろうか。




「はい、私でよければ!」


彼女は微笑んでいる。肩に入っていた力が溶かされていくように感じた。


「というか、晴れとか雨とか関係あるんですか?」

「そ、それは図書室に居るのは雨の日だけだから」

「じゃあ晴れの日は一緒に外で問題解きますか」

「いいの?」

「毎回一緒に、というわけにはいかないかもしれませんが、そういう時はこれで連絡しますね」


彼女はスマートフォンを振って見せた。


「あ、いや、別に毎日一緒にじゃなくてもいいんだけど」

「わかってますよ。……あ、そろそろ時間ですね」


端末をポケットにしまうと、席を立った。


「それじゃ先輩、また明日ね」

「あ、うん」


そう言うと、彼女は扉の方まで歩いて行った。
僕の横を通り過ぎる、石鹸のような、甘いような香り。


「明日、か」


降り続いた雨はいつの間にか上がっていた。












     ◇ ◇ ◇ ◇ ◇




この記事は 競プロ Advent Calendar 2021 1日目 のために作成されました。



ダブリングで累積和を計算すること、ダブリングしながら二分探索もすること、が技術的なテーマです。
個人的には汎用的だなあと思っているのですが、あまり使う機会がないですね。


紹介するテクニックの簡単な説明と実装、このテクニックで解ける例題を紹介します。

累積和のダブリング

半環 (\mathbb{R}, +, \times) において乗法のダブリングで  f(n) が計算できるとき、加法で  f(n) を累積した g(n)=\sum_{k=1}^{n}{f(k)} なる g(n) をダブリングで計算できます。


g(n+k)=g(n)+f(n)\times g(k)
g(2n)=g(n)+f(n)\times g(n)


加法と乗法の間に成り立つ分配則から、上の2式が成り立ちます。(通常のダブリングは分配則を必要としないことに注意して下さい。)


加法の単位元が不要だったりして本当は半環よりももう少し制約を緩めても成り立ちますが、競技プログラミングではあまり気にしなくていいかもです。

二分探索並行ダブリング

ダブリングができる構造で、単調性があるならダブリングと二分探索は同時に行えます。セグメント木の二分探索みたいな感じです。

項数  k の大きい  f(k) の方から順に使うかどうかを決定していけばよいです。


ある値  s の位置を二分探索していくとします。
lower bound の場合は、  f(k) を使うと得られる値が  s 未満になるならば  f(k) を使います。これを繰り返すと、最終的に  s 未満の最大の index が得られます。これに +1 したものが下界です。

upper bound の場合は、  f(k) を使うと得られる値が  s 以下になるならば  f(k) を使います。これを繰り返すと、最終的に  s 以下の最大の index が得られます。これに +1 したものが上界です。


次節の実装では lower_bound しか実装されていませんが、check関数を自分でよしなに定義すると upper_bound になります。



実装(python3)

ダブリングをクラス化しました。
(\mathbb{R}, op, prod) です。前計算するステップ数  k = \log_2{n} と、加法の二項演算  op 、乗法の二項演算  prod f(1) を生成する関数  prod1 を渡して下さい。

lower_bound には乗法単位元を生成する関数  e 、二分探索の判定関数  check を渡して下さい。

後述する例題は全てこのライブラリで解けます。

class Doubling:
  def __init__(self, k, op, prod, prod1):
    self.k = k
    self.op = op
    self.prod = prod
    self.prod1 = prod1

    self.f = [prod1()]
    self.g = [prod1()]

    for i in range(k):
      self.g.append(op(self.g[-1], prod(self.f[-1], self.g[-1])))
      self.f.append(prod(self.f[-1], self.f[-1]))
  def double(self, n):
    n -= 1
    res = self.prod1()
    i = 0
    while n:
      if n & 1: res = self.prod(res, self.f[i])
      n >>= 1
      i += 1
    return res
  def double_sum(self, n):
    n -= 1
    resg = self.prod1()
    resf = self.prod1()
    i = 0
    while n:
      if n & 1:
        resg = self.op(resg, self.prod(resf, self.g[i]))
        resf = self.prod(resf, self.f[i])
      n >>= 1
      i += 1
    return resg
  def lower_bound(self, e, check):
    n = 0
    t = e()
    for i in range(self.k, -1, -1):
      tt = self.prod(t, self.f[i])
      if check(tt): continue
      else:
        n |= 1 << i
        t = tt
    return n + 1
例題

ストーリーパートで登場した2題です。mojacoderに投稿されています。

t.co

t.co


おわり

ここまで読んでくださり、ありがとうございました。少し早いですが、良いお年を。

来年は10万字書きます。

AtCoder Regular Contest 130 反省

かなしい

 

結果を鑑みて

700 8:27

471位。Cで1ケースWA、WAを取りに行くとTLEでぼろぼろにされた。きちんと考察してから書くこと。

 

A - Remove One Character

ランレングス圧縮して二項係数をとってみると解ける。サンプルも優しいし、今回は300点っぽい300点だった。

 

B - Colorful Lines

ふつうにやろうとするとHやWがでかすぎて嫌な気持ちになりながらやることになりそうだが、後ろから見ると行や列の上書きは行や列の削除に対応づけられて、解けた。

 

ここまでは勘が冴えてた。

C - Digit Sum Minimization

本当に辛い。

こんなもの貪欲するしかないから貪欲を考える。和が9になるペアをマッチしてあげると、和が10以上になるペアを使った後に和が9になるやつを使い続けてあとは適当にやれば良いことがわかる。これで1WAまで進められたが、マッチの結果ぜんぶ9になるペアにしてしまうと良くない。

どれか一個のマッチを破壊しなくてはならないが、55通りくらいあってヤバい。しかもその都度digitsumをとっていてこれが一番ヤバい。TLEラッシュになり敗北。

 

digitsumの部分を最適化するか、もうちょっと問題を整理するしかない。

 

 

総括

Bまで良かったんだけど、Cで破滅。青パフォで済んだからまだよかったけど、泥沼実装に突っ込む前に落ち着いて考えられるようになりたいな。落ち着くのが一番難しい。

AtCoder Beginner Contest 229 反省

メンタルが壊れる!

 

結果を鑑みて

1500 19:12

542位。Fで詰まって、Gに行くのが遅すぎた。今回のFが解けないのは本当にヤバい。

 

A - First Grid

よく考えるとNoのパターンが斜めに2個配置の2パターンしかない。

 

B - Hard Calculation

がんばって実装する。10で割っていけば良いのだが、0埋めしたlistでやってしまった。筋悪。

 

 

C - Cheese

貪欲。

 

 

D - Longest X

にぶたんで解いた。

このあたりまでは100位ちょっとくらいで通過していたので余裕をもってEへ進めた。

 

 

E - Graph Destruction

UFくさいし、カットしてから辺を追加しないのでクエリ逆読みだと気付いた。

あとはよしなにやる。

 

トイレ行っている間に抜かれて200位くらいになってた。

 

F- Make Bipartite

一般グラフだとNPらしいし、dpくらいしかないんだよな。

嘘解法としてMST→くっつけられるだけ辺をくっつけるとかがあって、これだと一般グラフでも解けることになっちゃわないか?と思いながら提出してしまった。バカすぎる。

 

素直にdpすればいいのに長さ3の奇閉路をとらないグラフを構築するようにdpした。ふつうに落ちて、悲しいしもうわけわかんなくなってGへ行った。のこり40分弱くらい。

 

今考えても時間使いすぎだと思う。

F通さないとヤバいのはそうだが、詰まってるときは別の問題通してから帰ってくるっていうのは定石ムーブのはず。

 

G - Longest Y

まず、ある地点より右にあるYを寄せていく解法を作った。これ15分はかかったはずだけどサンプル1見れば嘘だと言うことがわかる。視野が狭くなっていた。

 

同時にサンプル1が解法を端的に表していることに気付き、結局あと10分くらいしかなかったから通せなかった。考察は合っていて、終了後10分あたりで通せた。

 

 

総括

ABCにだらだら参加して、ARCはnosubばっかりしてたから詰まった時のムーブを忘れていた。8問制だから6問のときよりも問題を保留するかどうかの見極めが重要かもしれない。

これでARC出て大丈夫なのかなあ

AtCoder Regular Contest 129 反省

nosubしてないだと

 

結果を鑑みて

1200(1) 91:59

330位。微冷えして青に叩き落とされた。

あと20分あればD通せたかも、と思うが他の問題に割いた時間や明らかな嘘解法に費やした時間が自分を苦しめただけなんだよね......。

 

A - Smaller XOR

パッと見桁dpに見える300点。1≦x≦Kとして、K=L, K=Rのときの結果があればOKだと思った。

桁dpは嫌だなあ、ここでつまづくとそこから先もえらい目にあいそう......

などと思っていたが、順位表を見て4, 5分で通している人がいたので、桁dpの線を捨てた。

そういえばARCの300か400くらいの問題で桁dpっぽいけど実はふつうに数え上げられるというようなのがあった気がしたのでぐっと睨むとxの1番上のbitが固定してみたときに良い感じにできる計算式を思いつく。

 

もともとBまで潜伏のつもりだったので出さずにBへ。

 

B - Range Point Distance

あんまり記憶がない。こういうのは区間の端点だけ見れば良いと直観した。

maxをとるような直線は端っこのほうから生えているはずだから、よく考えると直線は2本あればいい。

あとは数合わせをして提出。

 

このときはそんなに順位悪くなかった気がする。(300くらい?)パフォはカスだった。

 

C - Multiple of 7

142142...みたいにできるのかと思った。違った。

三角数で貪欲に構築していって、77777177717みたいに1で仕切ったら良い感じになったので出して1ペナ。

そこから迷走しまくって悩みに悩んだ末、順位表みて爆速で通している人を見て、ad-hocな方法でなくても構築できるのでは、と思った。

区間を値の7で割った余りごとに仕分けて貪欲にNを減らしていく形で構築していった。Nがでかすぎるとどの数字を置いてもうまくいかなくなる場合がありそうで不安だったが、1000くらいまで試してもうまくいっているので出したら通った。

 

後で知ったが、三角数定理を覚えていれば楽勝の問題なのだった。(あるいは、三角数定理があればこのアルゴリズムに正当性を与えられた。)

この時点で青落ちのパフォーマンスだった。ひえ〜

 

D - -1+2-1 

どこぞで見かけた、累積和で持つと良い感じのやつだと直観したが、円環なのでどうなるんだ?と思ってheapを使った貪欲に走ってしまった。

残り10分くらいになって冷静になり、見れば見るほど累積和でうまくいきそうなことに気付いた。index 0やN-1への操作が特殊で、ここの理解が中途半端なままコンテストが終わってしまった。

あとでちゃんとそのままの解法でがんばったら解けた。勘を信じよう。

 

総括

Eで燃やす埋めるみを感じたがAC数を見て諦めたのはやや偉いムーブだった。A、C、Dでの解法ガチャの失敗が良くなかった(Dについてはガチャは当たってたのに捨ててしまった)

Cはなんとなく1+2+3+...+nの組み合わせで整数を表す方法というのが一般的な話題のような気がしたのにググらなかったのは悪手だった。

 

なんとか微冷えで済んだが、ARCでまともに戦えるようになるにはもう少し冷静な立ち回りが必要だなと思った。あとは天才的な頭脳とかがあればもっといい。