ではこの範囲はどのように取るべきでしょうか？できるだけ多くの花に水をあげたほうが効率が良さそうな気がします。実際にこれは「伸ばせるだけ伸ばす」、つまり既に花の高さが足りている花の直前まで範囲を長く取るのが最適となります。これについては以前似たような問題の解説を書いているので、そちらも参考にしてください。

ということで、左から1つずつ見ていって、既に高さが足りている花に当たるまで花の高さを1ずつ足していきます。これを一番左の花の高さが足りるまで繰り返します。

一番左の花の高さが足りたら、次は左から2番目の花を左端として同じように考えます。これを最後の花まで繰り返すと答えが求められます。

計算量的には $O(N \sum h_{i})$ かかる素朴なやり方ですが、制約が小さいのでこれで間に合います。もっと速く解くやり方もありますね。

ACコード

（Ruby）Submission #4059357 - AtCoder Beginner Contest 116

実装は問題の操作とは逆に、「 $h_{i}$ を受け取り、全部0になるまで値を引いていく」と書くと楽です。もちろん、問題の通り「今の花の高さ」を別途配列で用意して値を足していく実装でも解けます。

D - Various Sushi

解法

この問題は解説が難しいですね…

まず、最適な寿司の選び方というものがどのような性質を持っているか考えてみます。例えば入力として

というものを考えてみましょう。このテストケースに対する最適な選び方は以下の図の赤色のものになります。

f:id:betrue12:20190124202804p:plain

満足ポイント $9+8+6+(2\times 2) = 27$ が最適値です。単体の美味しさ優先で $9, 8, 7$ を取ると25ポイント、種類数優先で $9, 6, 2$ を取ると26ポイントで最適になりません。単体の美味しさと種類数、どちらかを無視した貪欲はうまくいかないことが分かります。

このような最適な寿司の選び方が満たす性質があります。それは、「選んだ $K$ 個の寿司は、選ばなかった種類のどの寿司よりも、美味しさが大きいか等しい」という点です。

その理由は、もし選ばなかった種類の寿司の中に選んだ寿司より大きい美味しさを持つものがあれば、寿司を交換することで種類数・美味しさポイントともに有利になり、絶対に満足ポイントが高くなるからです。最適な選び方というからには、より満足ポイントが高い選び方は他に存在しないはずです。

この性質から、もし最適な選び方における寿司の種類数が分かっているならば、次のような方法で最適な選び方を求めることができます。種類数を $k$ とします。

まず全ての種類の寿司から、それぞれの種類で一番美味しい寿司を1つずつ取り出しておき、それらの寿司から美味しい順に $k$ 個選ぶ。
上記で選ばれなかった2番手以降の寿司を集めて、それらの寿司から美味しい順に $K-k$ 個選ぶ。

さきほどの性質を満たすと何故このような選び方で最適になるのかは、以下のように説明できます。

選んだ寿司は選ばなかった種類のどの寿司より大きいという性質、そして $k$ 種類の寿司を選ぶということから、まず各種類のベスト寿司を集めて大きい方から $k$ 個取ることができます。
残りの寿司に関しては、「さっき選んだ $k$ 個と同じ種類から美味しい順に $K-k$ 個選ぶ」という選び方をします。これもまた先ほどの性質のおかげで、単に2番手以降の寿司を集めて上から取れば自然とこのような選び方になります。

こうすることで、「各種類のベスト寿司」と「2番手以降の寿司」を独立に選ぶことができる点が嬉しいです。

肝心の最適な種類数 $k$ はまだ分かっていませんが、 $k$ を全探索すればどこかで最適値が見つかるはずです。このとき上記のやり方で寿司を選んだときの満足ポイントは

（各種類のベスト寿司の、上から $k$ 個の美味しさ和）＋（2番手以降の寿司の、上から $K-k$ 個の美味しさ和）＋ $k*k$

で求められます。それぞれの「上から○○個の美味しさ和」は事前にソートして累積和を取っておくことで高速に求められるため、 $k$ を全探索しても十分に間に合います。

ACコード

この解説では、解法の正しさが比較的納得しやすいような説明を採用しました。「最適な選び方が持っている性質を考える」ということは1つの重要な視点ですね。ただ、コンテスト本番では「種類数の項が厄介だから、まずそこを固定して全通り試そう」という発想からスタートするほうが自然かな、とは思います。

2019-01-22

DDCC2019 参加記

競技プログラミング

行ってきましたDDCC！

コード部門の解説記事は別途書いたので、こちらの記事ではイベントそのものの参加記を雑多に書いていこうかと思います。

会場で全然写真を撮っていないのでDDCC公式さんのツイートをペタペタ貼らせていただきます。

開始前

集まってきましたね〜 #ddcc2019 pic.twitter.com/bFJCRDx0Nt
— ddcc2019 (@ddcc_2019) January 19, 2019

会場はこんなところでした。普段はカフェテリアになっているそうです。200人集まるだけあってかなり広い。

暑すぎてディスコTに着替えた
会場内の気温が半袖Tシャツに最適化されている
— アルメリア (@armeria_betrue) January 19, 2019

DDCC Tシャツをいただきました。着替えどうしようかなと思いましたが…会場が半袖基準なのか！？と思うくらい暑かったので着替え。

前に円盤状のウェーハが飾られているのを見て「これが例のアレ…」と思いましたが、実はそれが上位3名に贈られるDISCO特製賞状（状？）でした。

貼った pic.twitter.com/UO4jyn7xP4
— アルメリア (@armeria_betrue) July 28, 2018

PCにこのステッカーを貼っていたら横を通ったchokudaiさんに発見されました。

コード部門

AB2完（40:25）で205人中95位でした。

本番の流れとしては、

Aは普通に通す（6:30）
Bはパッと見てよく分からなかったのでEの600点を狙いに行く（～30:00くらいまでここで使ってしまった）
Bに戻って解法に気づきAC（40:25）
C, Dをチラ見しつつEを考える…も分からず（～100:00くらいまで）
Dの方針が浮かぶも、実装が間に合わず終了（～120:00）

みたいな感じでした…

素直に解いている人が多いDに早く移るべきだったのかなあとは思います。TL13秒にビビリました。

DDCC2019 D - DISCO! https://t.co/ip6dXgXGuL
通した。本番考えてたので方針は合ってたみたい…
— アルメリア (@armeria_betrue) January 19, 2019

↑本番後に通しました

昼食

もうすぐでビュッフェ❤️#ddcc2019 pic.twitter.com/H05FUhL1j4
— ddcc2019 (@ddcc_2019) January 19, 2019

ここでTwitterなどで知っている人を探す…も、ほとんどの人は名札のAtCoder IDでしか判別できないのですれ違う人々の名札を見る怪しい人に。声を掛けていただけることも多かったのでとてもありがたかったです。1stエンカウントはJoeさん＆けんしんさんでした。

既にお会いしたことのあるてんぷらさん、その繋がりでつたじぇーさん＆ほげもちさんなどなどたくさんの方々と会うことができました。ありがとうございました！

話題を振るのが下手なのでひたすら競プロの話をしていたのですが、「この前のコンテストのあの問題が…」みたいな話を振っても普通に通じるの、改めて考えると凄いことですね。

ご飯はあんまり食べてないです。ひたすら喋ってました…

装置実装部門（予選）

動いてた。#ddcc2019 pic.twitter.com/1PLRR5vHOS
— ddcc2019 (@ddcc_2019) January 19, 2019

お昼休みの時点で用意されていたこの機械。装置実装部門はこの機械を使ってのコンテストで、予選はAtCoder上のシミュレータで行われました。（URLはありますが、非ログイン状態だとNot Found表示になるので、参加者しか問題を見れないものと思われます）

いわゆるマラソン形式なのですがこれが大変厳しく、長い問題文の中に制約が散らばっていてこれらを守れないと即WA、事前情報無しで制限時間は30分…と、その結果正の得点を取れたのが205人中19人。

マラソンなのにACができない #ddcc2019
— アルメリア (@armeria_betrue) January 19, 2019

コンテストが終わった瞬間に会場には笑いが…これはこれで貴重な経験でした。初回の試みなので、次回以降より良くなるよう期待したいところですね。

DISCO社内ツアー

せっかくなので参加希望を出していました。学生でもないのにスミマセン。

ダーツ、ビリヤード台、トレーニングジム、プールなどなど色々ありました。お蕎麦屋さんを吸収合併（？）した話が面白かったです。

あと会社のビルがそのまま寮にもなっているようで…気分的に会社に住みたいかはともかく、通勤時間ほぼゼロは良いですね。

実際に円盤状のウェーハを加工するところも見ることができました。

終わった後は時間があったので適当に喋ってました。かなり自由に交流できる時間があったように思います。

装置実装部門（決勝）

装置動かしてますよー！#ddcc2019 pic.twitter.com/pks2LubuOi
— ddcc2019 (@ddcc_2019) January 19, 2019

決勝はこんな感じで装置の周りに集まり、予選上位10人がプログラムを動かしました。

写真だとわかりにくいですが、緑と赤のランプがあるところから水が出ます。ビーカー（写真だと右手前にある黄色っぽいもの）をプログラムで制御して、2箇所で水を受ける→スミの排出穴に落とすという動作をいかに速く、かつこぼさずにできるか…という競技です。

10人皆さんのプログラムの動きにかなり特徴があって、観ているだけでかなり盛り上がりました。1位のyosupoさんの動きは、無駄なく速くこぼさずに…という、流石1位という感動的な動き方でした。競プロすごい（？）

これは素晴らしいイベントだと思いました。次回も改善・強化して是非やってほしいです。

表彰式

表彰式🏆#ddcc2019 pic.twitter.com/vpB1vNXnVX
— ddcc2019 (@ddcc_2019) January 19, 2019

装置実装部門1位はさっきの決勝時点で既に分かっていましたが、なんとコード部門でもyosupoさんが優勝。まさか2部門独占優勝になるとは…本当にすごい。

懇親会

ここでもご飯を食べながら色々な人とお話。

競技プログラミングを始めたのは相対的に見ると最近のほうではありますが、結構たくさんの方に知ってもらえていて。あと「ブログの解説見てます」と言っていただけてとてもありがたいです。

あと、名札に書いていたAtCoder IDに普段名乗っているアルメリアという名前が入っていないので、次からは見つけてもらいやすいように自前の名札を持っていこうと思いました…

みなさんご参加いただき、ありがとうございました🙌
集合写真🔽 #ddcc2019 pic.twitter.com/gAvCzyQSqS
— ddcc2019 (@ddcc_2019) January 19, 2019

最後に写真撮影をして終わり。皆さんありがとうございました！

おまけ

体重実装部門です #DDCC2019 pic.twitter.com/pgYOj1CSBN
— アルメリア (@armeria_betrue) January 19, 2019

昼も夜も会場であまり食べていなかったので帰り道でご飯。「さぼてん」というお店です。オススメ。

最後に

オンサイトコンテストの参加は昨年7月のSoundHoundコンテスト以来で、そのときは社会人限定というちょっと特殊な感じでしたが、今回は幅広く205人もの人が参加していて色々な人と会うことができました。

もちろんメインはコンテストで競い合うというイベントですし、主催企業さんにとっては特に学生さん向けに自社をアピールする機会ではありますが…普段オンラインで繋がっている競プロerと実際に会って交流できるというのはやっぱり一番大きな魅力だと思います。この場を用意してくれた方々に本当に感謝です。「コンテスト楽しかったなあ」というのは会社名とともに記憶に強く残りますよね。

私自身はもう社会人なので、今回のように社会人にも多い枠が用意されているコンテストにしか参加できないとは思いますが…これからもできる限りオンサイトコンテストに参加したいですし、特に次回のDDCCにも是非行きたいですね。精進あるのみです。

f:id:betrue12:20190122000141p:plain

2019-01-20

DDCC2019 参加記録（コード部門）＆解説（A, B, D）

AtCoder プログラミング競技プログラミング

今回はオンサイト参加でした！

コード部門以外のもろもろ参加記はまた別途書こうかなと思っています。この記事ではいつものように問題の解説を。

f:id:betrue12:20190120141813p:plain

本番はAB2完でしたが…A, B, D問題について書きます。

A - レース (Race)

解法

連続した氷マスの長さに応じて所要時間が変わるので、連続した氷マスそれぞれの塊について考えます。

雪マス1つを氷マスに変えたとき、もし別々の氷マスの塊が結合してしまうようであれば厄介ですが、制約からそのようなことは起こりません。そのため、氷マスを1つ増やして一番得になる氷マスの塊に付けることを考えればよく、それは最も長い氷マスの塊になります。

あとは実際に計算です。私のコードではまず氷マスの塊の長さを全て列挙し、一番大きい要素に1加え（氷マスが1つもない場合に注意）、最後に計算しています。

ACコード

B - 大吉数列 (Array of Fortune)

解法

$a_{i} \ge a_{j}+K$ かつ $i \lt j$ を満たすペア $(i, j)$ の個数というものは、「転倒数」によく似ています。実際、 $K = 1$ とするとこれは順列の転倒数そのものになります。この記事ではこのペアの個数を $K$ 転倒数と呼ぶことにします。

転倒数が最大になるのは数列が逆順ソートされているときでした。 $K$ 転倒数が最大になるのも、同様に数列が逆順ソートされているときです。まずはその個数を求めます。

f:id:betrue12:20190120164606p:plain

図に示すように、長さ $N$ の順列を逆順ソートしたときの $K$ 転倒数は、 $1, 2, ..., N-K$ を全て足したものになり、計算すると $\frac{(N-K)(N-K+1)}{2}$ です。与えられた $R$ がこの値より大きい時は、どうやっても条件を満たせないので No Luck で終了です。以降、そうでないときに数列を構成する方法を考えます。

まず $1, 2, ..., N$ という正順ソートされた数列を考えると、この数列の $K$ 転倒数はもちろん0です。この数列の末尾要素 $N$ を先頭に移動させると、 $1, ..., N-1$ までの要素との位置関係が逆になります。このうち $1, ..., N-K$ の値に対して $K$ 転倒数が増えるため、 $K$ 転倒数は $N-K$ 増えます。

次に $N-1$ を2番目に移動させると、同じように $K$ 転倒数は $N-K-1$ 増えます。このように「末尾の要素 $N-i$ を数列の $i$ 番目に移動させてきて、 $K$ 転倒数を $N-K-i$ 個増やす」という操作を、 $K$ 転倒数が $R$ を超えないところまで繰り返します。（「 $i$ 番目」は0-indexedです）

最後は $K$ 転倒数をぴったり $R$ に合わせるために微調整をする必要があります。といっても、同じように末尾の要素 $N-i$ を数列の $i$ 番目に移動させた後、増えすぎたぶんを戻すために1つずつ後ろに戻していくと考えると楽です。後ろに戻すときは $1, 2, ...$ といった小さい値から順に位置関係が戻っていくため、ぴったり $R$ になるまでは1つ戻すごとに $K$ 転倒数が1減っていきます。

f:id:betrue12:20190120165441p:plain

あとはこれを実装します。私の実装では全要素 $-1$ （空いていることを示す）で初期化したvectorを用意し、 $K$ 転倒数が $R$ になるまでは大きいほうから値を埋めていって、最後に空いているところに小さいほうから値を入れています。

ACコード

（C++）Submission #4039728 - DISCO presents ディスカバリーチャンネルコードコンテスト2019 本戦

D - DISCO!

公式解説とは違う方法で解いたので、その方法を書きます。

解法

もしクエリの全てが $L = 1$ 、つまり常に先頭からある右端までの部分列 DISCO の個数を答えるのであれば簡単です。「 $S$ の先頭から $i$ 文字目までに含まれる、 DISCO のうち $j$ 文字目までの部分列の個数」を $dp\lbrack i \rbrack \lbrack j \rbrack$ とするDPをしておけばよいです。この場合の答えは $dp\lbrack R \rbrack \lbrack 5 \rbrack$ です。

今回の問題の場合は $L$ も様々な値を取りますが、 $L=1$ のときの応用で解けないか考えてみます。

与えられたクエリ $L, R$ に対して、まず区間 $\lbrack 1. R \rbrack$ に含まれる部分列 DISCO の個数が先ほどのDPで分かっているとします。この個数をいくつかのパターンに分解します。

f:id:betrue12:20190120170554p:plain

求めたいのはこのパターンのうち一番上のものなので、それ以外の値を全て引けば答えが求められるはずです。

これらの値の求め方を考えます。例えばD | ISCO と分断されているパターンについて、この個数は区間 $\lbrack 1, L)$ に含まれる D の個数と区間 $\lbrack L, R \rbrack$ に含まれる ISCO の個数の積です。前者は $dp\lbrack L-1 \rbrack \lbrack 1 \rbrack$ です。次に後者ですが…これは元のクエリで問われている値の、頭の文字数が1文字少ないバージョンになっています。必要なDPテーブルの値さえ分かっていれば、これは今まで書いてきた方法と全く同じように求められるはずです。

DI | SCO と分断した場合も、区間 $\lbrack 1, L)$ に含まれる DI の個数と区間 $\lbrack L, R \rbrack$ に含まれる SCO の個数として同様に求められます。 DIS | CO、DISC | O についても同様です。最後の DISCO | となっているパターンは、 $dp\lbrack L-1 \rbrack \lbrack 5 \rbrack$ そのものです。

ここまでの議論を一般化します。「区間 $\lbrack L, R \rbrack$ の間に含まれる、 DISCO の末尾 $k$ 文字と一致するような部分列の個数」を $f(L, R, k)$ と置くと、クエリの答えは $f(L, R, 5)$ です。そしてこの値は先ほどの図で示したやり方を用いて、 $f(L, R, k-1), ..., f(L, R, 1)$ の値と、前計算したDPテーブルの値を用いて計算することができます。

このときDPテーブルの値は少し拡張する必要があって、例えば $f(L, R, 4)$ の計算では ISCO の個数を求めなければいけないので、先頭からの ISCO や I IS などの個数が必要となります。そのため、「 $S$ の先頭から $i$ 文字目までに含まれる、 DISCO のうち $j$ 文字目から $k$ 文字目までの部分列の個数」を $dp\lbrack i \rbrack \lbrack j \rbrack \lbrack k \rbrack$ とするDPテーブルを全て計算しておけば必要な値が揃います。

あとは $f(L, R, 5)$ の計算をきちんと立式できれば解けます。クエリごとにメモ化することで計算時間を短縮できますが、制限時間がとても長いのでしなくても間に合うんじゃないかと思います。

計算量については、DISCO の長さは大きく影響するので $D = 5$ として表記に入れ込むことにします。メモ化した場合、DPとクエリ処理合わせて $O(D^{2}N + D^{2}Q)$ となります。

ACコード

（C++）Submission #4046101 - DISCO presents ディスカバリーチャンネルコードコンテスト2019 本戦

制限時間13秒のおかげでRubyでも通ります。

2019-01-14

KEYENCE Programming Contest 2019 参加記録＆解説

AtCoder プログラミング競技プログラミング

まあまあの速度で4完。Eは解きたかった…

f:id:betrue12:20190114020636p:plain

本番後に通したEも含めて5問解説します。→Fも書き足しました。

A - Beginning

解法

ソートして 1479 になるかどうかチェックするのが一番楽です。

ACコード

（Ruby）Submission #3998262 - KEYENCE Programming Contest 2019

B - KEYENCE String

解法

文字列 $S$ が100文字以下なので、取り除く範囲を全探索すればよいです。

部分文字列のとり方は各言語によって違いますが、ちゃんと漏れなく列挙できているかどうか不安になりますね…不安な場合は試しに abc などの短い文字列を入力にして、列挙した文字列を全部デバッグ出力して全部あるか確認してみるのが良いと思います。

ACコード

（Ruby）Submission #4000281 - KEYENCE Programming Contest 2019

C - Exam and Wizard

解法

準備度が余っているテストから、準備度が足りないテストに値を移動させます。このとき、そもそも合計値が足りていない場合は条件を満たすことが不可能です。

準備度を変更するテストの個数をなるべく少なくしたいですが、準備度が足りないテストは明らかに変更する必要があるので、準備度の余っているテストの変更数をなるべく少なくしたいです。これは余っている値が大きいものから順番に使っていくと最適になります。

まとめると、準備度が足りないテストの個数と不足値合計を計算しておきます。次に準備度が余っているテストの余剰値を大きい順にソートして、不足値を全部補えるまで大きい方から使っていきます。準備度が足りないテストの個数と、準備度が余っているテストを使った個数の合計が答えです。

ACコード

（C++）Submission #4001678 - KEYENCE Programming Contest 2019

D - Double Landscape

解法

各行と各列の最大値が指定されているので、数を大きいほうから追加していくと上手くいきます。小さい方から追加していくと「最大値のために1つマスを空けておかないといけない」など条件が難しくなりますが、大きい方から追加していくと最大値を追加した後はその行/列に自由に数を追加していけるからです。

ということで大きい方から追加していきますが、例を使ってどのようになるかを見てみます。

f:id:betrue12:20190114030452p:plain

例にあるように、

行最大値と列最大値の両方に登場するときは、その交点に置く。
行最大値だけに登場するときは、既に最大値が置かれている行に置く。逆も同様。
行と列どちらの最大値にも登場しないときは、行にも列にも既に最大値が置かれているようなマスに置く。

という操作をすることになります。この操作を $NM, NM-1, ..., 1$ と最後まで行って、各数字の置ける候補の個数を全部掛け算したものが答えになります。

1.の場合、もちろん候補の数は1つです。

2.の行最大値だけに登場するときは、既に列最大値が登場している列数がそのまま候補の数になります。

3.については、「行にも列にも既に最大値が置かれているような空きマスの個数」が必要です。これは（最大値が置かれた行の数）×（最大値が置かれた列の数）－（既に置いた数字の個数）で求めることができます。

この操作の途中で「置き場所がなくなった」、つまり置く候補の数が0になった場合は、答えは0になります。0に何を掛けても0なのでそのまま処理を続けてもよいですし、すぐに0を出力して終了しても良いです。状態がおかしくなってREになるかもしれないという不安がよぎるので、即終了のほうが安心かもしれません。

ACコード

（C++）Submission #4011139 - KEYENCE Programming Contest 2019

実装においては行最大値と列最大値をそれぞれソートしておくと楽です。これは盤面の行と行、または列と列を入れ替えるという操作に相当し、今回はこの操作によって答えが変わることはないのでソートして大丈夫です。

E - Connecting Cities

解法

コンテスト終了後に公式解説を見て通したので、公式解説ベースの解法で解説します。

作りたいのは最小全域木です。ただし辺の張り方が $O(N^{2})$ 通りあるので、辺の選び方を工夫する必要があります。

辺のコストは都市間の距離 $|i-j|$ と都市の規模 $A_{i}$ に依存していて、「近いから」「規模が小さいから」というだけでは最適な辺を選ぶことはできません。ただし、「近いし規模も小さい」という辺は、「遠いし規模も大きい」という辺よりはコストが小さいはずです。

というわけで、そのような状況を考えてみます。

f:id:betrue12:20190114122008p:plain

図の縦軸が規模 $A_{i}$ の値で、横軸が位置を表します。このとき辺 $a, c$ を比べると、 $c$ のほうが「近いし規模も小さい」という辺になっています。

ここでさらに図中の $b$ のような辺を考えると、この閉路を作る3辺のうちコストが最大の辺は最小全域木において使うことはありません（クラスカル法のアルゴリズムより）。さきほど見た $a \gt c$ という関係から、 $a, b$ のうちコストが大きいほうが3辺の中でもコスト最大になり、その辺は考える必要がありません。

この考察は規模の等しい都市があったとしても成立します。また辺 $a, b$ のコストがぴったり同じ場合は、どちらを使うと考えてもよいです。

この事実を一般化するために、3点の中で一番 $A_{i}$ が大きい頂点、図中の頂点 $i$ に注目します。そうするとさきほどの事実は

ある頂点 $i$ から見て左右のどちらかを見たときに、そちら側にある「規模が $A_{i}$ 以下である頂点」2つと結ぶ辺のうち、コストが小さいもの1本以外は不要である

と言い換えられ、さらに一般化して

ある頂点 $i$ から見て左右のどちらかを見たときに、そちら側にある「規模が $A_{i}$ 以下である頂点」と結ぶ辺すべてのうち、最もコストが小さいもの1本以外は不要である

と言うことができます。このように考えると、不要でない辺は1つの頂点につき高々2本しかないことが分かります。（これはあくまで規模が小さい都市に「繋ぎに行く」辺の本数であり、規模の自分より規模の大きい都市から「繋がれる」ことである頂点の最終的な次数が2を超えることはあります）

不要でない辺が高々頂点数の2倍であれば、クラスカル法などのアルゴリズムで十分間に合います。

f:id:betrue12:20190114122027p:plain

次は「頂点 $i$ から見て片側にある、規模が $A_{i}$ 以下である頂点のうち、コストが最も小さいものはどれか？」という問題を解く必要があります。区間内最小値ということでセグメント木が使えそうですが、距離の条件があるのでコスト値そのものをセグメント木に入れることはできません。

ただコストの特徴として、例えばある頂点から右側を見る場合、1つ座標が右にずれるごとにコストの距離要素は $+D$ だけ変動します。2つ座標がずれると $+2D$ です。この距離が遠くなることによるコスト差を、最初からセグメント木に含めてしまうという手があります。つまり「右側を見る」用のセグメント木には、

頂点1の要素としては $A_{1} + D$
頂点2の要素としては $A_{2} + 2D$
...
頂点Nの要素としては $A_{N} + ND$

を格納します。こうすれば距離によるコスト差を含んだ上での最小値がどれなのか判断できます。ただこれは「大小関係の比較」をするには正しいですが、頂点 $i$ の位置が考慮されておらず実際のコストそのものではないので、実際のコストは求め直すか頂点 $i$ のぶんを補正しましょう。

「左側を見る」用のセグメント木は別途作って、傾斜を逆にします。またこの問題の場合「最小コストはいくらか」だけでなく「最小コストを実現する頂点はどれか」という情報も必要なので、 (コスト, 頂点番号) の形のペアを格納できるセグメント木を使うとよいです。

規模が自分以下の頂点だけを繋ぎに行く対象にしたいので、「頂点を規模が小さい順にセグメント木に追加しながら、その時点で追加されている頂点の中から繋ぎ先を選ぶ」という処理の流れになります。

このようにすれば不要でない辺の選定も効率的に行うことができるので、最後にクラスカル法で最小全域木のコストを求めればOKです。

ACコード

Submission #4010825 - KEYENCE Programming Contest 2019

F - Paper Cutting

解法

最初の発想

操作列をそのまま列挙するのはもちろん無理です。少し考えると、 $k$ 回目の操作後の破片の個数はその時点での縦の切断数と横の切断数から求めることができて、（破片の数）×（場合の数）みたいなのをどんどん足していけば答え自体は求まります。ただ計算量がかかりすぎてしまいます。

ここで発想を変え、「破片と1対1に対応する何か」を数え上げることができないか考えてみます。今回の場合、「破片の四隅のどこか1つ（例えば、左上隅）」を数えるように考えてみると上手くいきます。

つまり、「 $k$ 回目の切断後に、紙の座標 $(i, j)$ が、破片の左上隅になっている」という条件を満たす場合の数を数えます。これを $i, j, k$ 全てについて合計してあげれば求めたい答えが求まるはずです。

一見変数が多くてやっぱり計算量が多くなりそうですが、この考え方にはとても嬉しい性質があり、それは「座標 $(i, j)$ が破片の左上隅になるような条件は、高々4種類だけに分類できる」ということです。具体例を見てみます。

f:id:betrue12:20190115002812p:plain

このように、左上隅のマス、上辺のマス（左上隅以外）、左辺のマス（左上隅以外）、それ以外のマスで分類できます。

これらの条件は「常に左上隅になる」「特定の1直線が切れていれば左上隅になる」「特定の2直線が切れていれば左上隅になる」の3種類に分けられて、上辺・左辺の性質もまとめることができます。それぞれのマスの個数も計算することができるので、あとは切断ステップ $k$ ごとに「 $k$ 回目の切断後に、そのマスが左上隅になる条件が満たされている」ような場合の数を求めればよいです。

左上隅

これは簡単です。全部の場合の数を数えればよいです。

$H+W$ 個の直線を順序を付けて $K$ 個並べるので、全部の場合の数は $_{H+W}P_{K}$ になります。切断回数は全部で $K$ 回、マス数は1個なので、これらを全部掛け合わせて

$S_{1} = K \times (_{H+W}P_{k})$

が左上隅についての合計破片数になります。

上辺/左辺

これらのマスが破片の左上隅になる条件は、ある特定の1直線が切断されていることでした。この直線を $a$ と表記します。

$k$ 回目の切断後に直線 $a$ が切断されているような場合の数を考えます。このとき直線 $a$ の入る場所は1回目から $k$ 回目までの $k$ 通りです。そして残りの $K-1$ 回分の切断は何でも良いので、残った直線 $H+W-1$ 本から自由に並べます。このような場合の数の総数は

$k \times _{H+W-1}P_{K-1}$

になります。これは $k$ に依存しているので1回目から $k$ 回目までの和を取って、さらに上辺と左辺のマス数（左上隅以外）のマス数 $H+W$ を掛けて、

$S_{2} = (\sum_{k=1}^{K}k) \times (_{H+W-1}P_{K-1}) \times (H+W) = \frac{1}{2}K(K+1) \times (_{H+W}P_{k})$

となります。 $\sum_{k=1}^{K}k = \frac{1}{2}K(K+1)$ の公式を使っています。

※ちなみに最後の式変形で $(_{H+W}P_{k})$ と全事象数が出ていていますが、確率の考え方を用いると $k$ 回目の切断終了後にある直線 $a$ が切れている確率は $\frac{k}{H+W}$ と求めることができて、（全事象数）×（確率）の計算をすることでも全く同じ式を導くことができます。

それ以外

それ以外の辺が破片の左隅になる条件は、ある特定の2直線が切断されていることでした。この直線を $a, b$ と表記します。

$k$ 回目の切断後に直線 $a, b$ がともに切断されているような場合の数を考えます。このとき、まず直線 $a$ の入る場所は先ほどと同じく $k$ 通り。そして直線 $b$ の入る場所は、 $a$ が入ったぶん空きが1つ少なくなるので $k-1$ 通りです。残りの $K-2$ 回分の切断は何でも良いので、残った直線 $H+W-2$ 本から自由に並べます。このような場合の数の総数は

$k(k-1) \times _{H+W-2}P_{K-2}$

になります。やはり $k$ で和を取ってマス数の合計 $HW$ を掛けると、

$S_{3} = (\sum_{k=1}^{K} k(k-1)) \times (_{H+W-2}P_{K-2}) \times (HW) = \frac{1}{3}K(K-1)(K+1) \times (_{H+W-2}P_{K-2}) \times (HW)$

となります。前2つと違ってあまりキレイな式にはなりません。 $\sum$ の計算は先ほどの公式と $\sum_{k=1}^{K}k^{2} = \frac{1}{6}K(K+1)(2K+1)$ の公式で展開して変形するとこうなりますが、 $k(k-1)$ の和を $O(K)$ で素直に求めても良いと思います。

最後に答えを計算

これらを全て計算すれば $S_{1} + S_{2} + S_{3}$ のmodを取ったものが答えになります。

必要な道具は高々 $H+W$ までの階乗なので計算量は $O(H+W)$ で、 $1 \le H, W \le 10^{7}$ といつもより大きめの制約ですが十分間に合います。

ACコード

Submission #4014003 - KEYENCE Programming Contest 2019

コードは数学をして求めた計算式をただ並べているだけという感じですが… $K^{3}$ が64bitでもオーバーフローするのでそこだけ注意です。

2019-01-13

AISing Programming Contest 2019 参加記録＆解説

AtCoder プログラミング競技プログラミング

AISing Programming Contest 2019 - AtCoder

全完！

2000未満ratedコンテストだったのでパフォーマンスは付かず、ちょっと残念。

f:id:betrue12:20190112235728p:plain

A - Bulletin Board

解法

縦の位置が $N-H+1$ 通り、横の位置が $N-W+1$ 通りあるので、これらを掛け算したものが答えです。

ACコード

（Ruby）Submission #3983074 - AISing Programming Contest 2019

B - Contests

解法

「1問目になるもの」「2問目になるもの」「3問目になるもの」がそれぞれ排他、つまり点数の範囲が被っていないことが重要です。それぞれの問題数を数えて、一番小さいものを出力すればよいです。

ACコード

（Ruby）Submission #3983935 - AISing Programming Contest 2019

C - Alternating Path

解法

黒→白→黒→白…と移動することは、「今いるマスと違う色のマスに移動する」ことと考えることができます。そう考えると、違う色で隣り合っているマスは「相互に行き来できるマス」ということになります。

この相互に行き来できるマス同士を繋いでいくと、グリッドの中で「この範囲内はどのマスからどのマスへも相互に行き来できる」という領域ができます。そうするとこの領域内の黒のマス数×白のマス数だけ、問題の条件を満たすペアを作ることができます。これを領域ごとに数えて全部足すと答えになります。

f:id:betrue12:20190113152616p:plain

あとは「領域の調べ方、数え方」ですが、これは幅優先探索/深さ優先探索などが楽だと思います。あるマスから始めて、違う色で隣り合っている未訪問のマスを探索していけばよいです。

ACコード

D - Nearest Card Game

解法

ここから難易度が上がるので、解説もしっかりしていきたいと思います…

二人が取るカードの全体像を掴む

たくさんの $x$ の値について答えを出さなくてはいけませんが、まずは一旦それを忘れて、ある1つの $x$ について考えます。

問題の操作から、高橋くんと青木くんがどのようにカードを取っていくか考えてみます。

f:id:betrue12:20190113011859p:plain

全体の形としてはこのようになります。まず高橋くんは大きいほうから、青木くんは $x$ の周りからカードを取っていきます。こうするといずれ高橋くんが青木くんの取っていた領域に当たってしまうので（図中の $y$ のあたり）、その後は2人で交互に残った下の方のカードを大きい方から取っていきます。

もちろん、このうちどこかの領域は要素数がゼロかもしれません。例えば $x$ がものすごく大きいところにある場合、2人は単に一番上から交互にカードを取っていくだけになります。

「境界」を探す

これらのゾーンの境界が知りたくなります。境界が分かってしまえば、累積和を用いて高橋くんのカードの合計が分かりそうです。

$x$ より上にあるカードについて、そのカードを高橋くんと青木くんどちらが取るのか？を考えます。これを知るには、高橋くんと青木くんそれぞれについて「その人がそのカードを取るとしたら、何枚目に取るか？」を考えればよいです。

取る順番が早いほうがそのカードを取ります。同順の場合は先攻の高橋くんが取ります。

f:id:betrue12:20210118032906p:plain

高橋くんのほうは簡単で、一番上から取っていくので「そのカード以上にあるカードの枚数」がそのまま使えます。

青木くんのほうは少しだけ厄介ですが、 $x$ に近いところから取る、距離が同じ場合は小さい方を先に取る、という条件から、カード $y$ を取る時点で青木くんは、 $d = |x-A_{y}|$ として $x - d$ 以上 $x+d$ 以下の範囲にあるカードを全て取っているはずです。なのでその範囲にあるカードの枚数を数えればよくて、ある座標範囲内にあるカードの枚数は二分探索などで求めることができます。

こうやって $x$ より上側のカードについて「どちらが取るか」を判定できるので、これが逆転するところがさきほど示したゾーンの境界になります。

大量クエリの高速処理を考える

これで答えを求めるための道筋は見えました。あとは計算量です。

答えを求めなければいけない $x$ がたくさんあるので、結局は「 $x$ が与えられたときに高速にゾーンの境界を求められるか？」という話になります。これを解決する方法は2つあります。

$x$ の値が数直線の右側に移動すると、ゾーンの境界も右側に移動していくこと（単調性）を利用する。与えられた $x$ をソートし、しゃくとり法で境界を求めていく。
さきほどの「どちらが取るか」自体に単調性があることを利用し、これを二分探索する。

これはどちらでも良いです。計算量オーダーとして優位なのはしゃくとり法ですが、各クエリを独立に処理できたほうが分かりやすいので計算時間に余裕があれば二分探索でも良いでしょう。

境界が分かった後は、各ゾーンの累積和で答えを求めます。交互に取るゾーンがあるところも考慮し、1つ飛ばしの累積和（添字の偶奇ごとに累積和を取ったもの）も求めておくと良いです。

ACコード

（C++、しゃくとり）Submission #3988902 - AISing Programming Contest 2019
（C++、二分探索）Submission #3996155 - AISing Programming Contest 2019

E - Attack to a Tree

解法

木DPの着想を得る

ある適当な点を根とする根付き木とみなし、葉から順番に値を計算していく木DPを考えてみます。

DPテーブルが持つ情報として必要そうなものは、「その頂点以下で何本の辺を切ったか」「その頂点を含む連結成分の、現時点での電力合計」です。このうち電力合計はとても大きい値になり得ますが、切った辺の本数は最大でもその頂点以下にある辺の本数なので比較的少ないです。そこで

$dp\lbrack i \rbrack\lbrack j \rbrack$ ＝頂点 $i$ 以下の部分木を考えたときに、辺を既に $j$ 本切っているときの、頂点 $i$ を含む連結成分の電力合計の最小値。ただし、辺を切ったことで既に確定している連結成分は問題の条件を満たしていなければならない。

と定義します。電力を足りなくさせることが目的、つまり電力合計をなるべく小さくしたいので最小値を取っています。

ただしこのままでは情報が不足しています。各連結成分が満たすべき条件は、「連結成分にコンピュータが存在しない」「連結成分内の電力合計が負」のどちらかなので、電力合計だけでなくコンピュータが存在するかどうかの情報が必要になってきます。そのため、

$dp\lbrack i \rbrack\lbrack j \rbrack\lbrack k \rbrack$ ＝頂点 $i$ 以下の部分木を考えたときに、辺を既に $j$ 本切っていて、部分木内にコンピュータが存在する（ $k=1$ ）/しない（ $k=0$ ）ときの、頂点 $i$ を含む連結成分の電力合計の最小値。ただし、辺を切ることで既に確定している連結成分は問題の条件を満たしていなければならない。

と各頂点が持つ値を定義します。以下はある状態において、各添字がどのようになるかを示す一例です。

f:id:betrue12:20190113160918p:plain

これなら、後に示すように遷移を構成することができます。

遷移を考える

子の情報から親の情報へ、どのようにDPの遷移を作ればよいか考えてみます。

イメージとしては、最初は親を要素数1の部分木として考え、そこに子の部分木を1つずつマージしていきます。親と子それぞれについて、さきほどの $j, k$ についてループを回します。

このとき、子からの辺を繋ぐか切るかという2通りが考えられます。

f:id:betrue12:20190113023514p:plain

添字が多いので式がややこしくなりがちですが、

辺を繋ぐ場合、今までに切った辺の数・電力合計は加算し、コンピュータがあるかどうかはOR演算する。
辺を繋がない場合、まずは子の部分木が条件を満たしているかどうかをチェック！ 満たしている場合は、切った辺の数は合計に1を足したものになり、それ以外の情報は親の情報がそのまま残る。

という風に遷移先を求めることができます。この遷移先に対して「今の値より値が小さくなるなら更新」と操作することを繰り返すと遷移ができます。

計算量について、通称「二乗の木DP」

さきほどのDP、子をマージするたびに親子それぞれの切った辺の数についてループを回すので計算量がひどくなりそうな気がします。具体的には全頂点について辺の数の2乗ループを回しているので、全体 $O(N^{3})$ になりそうです。

ですが、「その時点で持っている部分木のサイズまでしかループを回さない」という実装をすることで、全体計算量を $O(N^{2})$ とすることができます。これが通称「二乗の木DP」と呼ばれるものです。部分木の辺の数は頂点の数-1なので、切った辺の数でループする場合はこのテクニックが使えます。

ACコード（＆実装について）

（C++）Submission #3996371 - AISing Programming Contest 2019

私の実装について少し補足です。

DPテーブルに持つ値についてですが、 $INF$ という値を使っています。先ほど書いたようにこのテーブルの中には添字で定義された状態における電力合計の最小値が入っていますが、ときには「そのような添字に対応する状態が存在できない」ということがあります。一番単純な例では、部分木内にコンピュータが1つもない場合は $dp\lbrack i \rbrack\lbrack j \rbrack\lbrack 1 \rbrack$ に対応する状態はありません。このようなときには値に $INF$ を入れています。

この問題ではDPを回した後、最後に「辺の切り方が合計 $j$ 本であるような、問題文の条件を満たす分け方が存在するか」を根について調べて、一番小さい切断本数を答えることになります。このときに「 $INF$ の場合はそのような状態が存在しない」という決めごとをしておくと判定を正しく行うことができます。コードでは以下の部分です。

for(int n=0; n<N; n++){
    if(dp[0][n][0] < INF) ans = min(ans, n);
    if(dp[0][n][1] < 0) ans = min(ans, n);
}

2019-01-05

Hello 2019 (Codeforces) 参加記録＆解説（A～D, F）

Codeforces プログラミング競技プログラミング

Codeforces

2019年最初のコンテストはABCDFの5完で111位！幸先いいですね。

A. Gennady and a Card Game

Codeforces

問題概要

2文字の文字列でトランプのカードを表す。1文字目がランク、2文字目がスートに対応する。

場にあるカードが与えられ、さらに5枚の手札が与えられる。場にあるカードに対して、ランクまたはスートの少なくとも一方が一致するカードをプレイすることができる。

手札の中にプレイできるカードがあるかどうか判定せよ。

制約

省略

解法

手札を順に場のカードと比較し、1文字目または2文字目が一致するものがあるかを判定すればよいです。

ACコード

Codeforces

B. Petr and a Combination Lock

Codeforces

問題概要

$n$ 個の角度 $a_{1}, ..., a_{n}$ が度数法で与えられる。それぞれの角度に対して左回り/右回りを自由に選んで、1周あたり360度のダイヤルを回す。操作が全て終わった時にダイヤルが最初と同じ位置にあるような回し方が可能であるかどうか判定せよ。

制約

$1 \le n \le 15$
$1 \le a_{i} \le 180$

解法

左回りをプラス、右回りをマイナスとして角度を符号付きで全て合計したときに、その値が360度の倍数になっていればよいです。

制約より $O(2^{n})$ が十分間に合うので、回す方向を全探索してそれぞれ計算すればよいです。

ACコード

Codeforces

私の実装はbit全探索です。hackを狙ってコードを読んでいたら、再帰関数での実装も多く見られました。

C. Yuhao and a Parenthesis

Codeforces

問題概要

括弧だけで構成された文字列が $n$ 個与えられる。文字列2つをペアにして正しい括弧列をできるだけ多く作りたい。1つの文字列が2つ以上のペアに属することはできない。

作ることができるペアの最大数を求めよ。

制約

$1 \le n \le 10^{5}$
全ての文字数の合計は $5 \times 10^{5}$ を超えない

解法

正しい括弧列の条件は、( を+1、) を-1とする累積和を取ったときに、

文字列全体の合計がちょうど0である。
頭から見て、どの時点でも累積和が0以上である。

を満たすことです。

このことを考えると、2つの文字列をペアにして正しい括弧列とするためには、ある非負整数 $k$ に対して

前半の文字列
- 合計が $k$ である。
- 頭から見て、どの時点でも累積和が0以上である。
後半の文字列
- 合計が $-k$ である。
- 頭から見て、どの時点でも累積和が $-k$ 以上である。

をそれぞれ満たす必要があります。

あとはそれぞれの文字列に対して累積和の最小値と合計を計算して、「合計が $x$ で、最小値の条件を満たすものの個数」を整数 $x$ ごとに集計します。その値を $mp\lbrack x \rbrack$ とすると、正整数 $k \gt 0$ について正しい括弧列は $\min(mp\lbrack k \rbrack, mp\lbrack -k \rbrack)$ 個作れます。合計0の文字列は合計0の文字列とペアになるので、 $\lfloor\frac{mp\lbrack 0 \rbrack}{2}\rfloor$ 個作れます。これらを全て加算すれば答えが求められます。

ACコード

Codeforces

D. Makoto and a Blackboard

Codeforces

問題概要

整数 $v$ の初期値を $n$ とする。整数 $v$ に対して、以下の操作を $k$ 回行う。

その時点での $v$ の約数の中からランダムに1つ選ぶ。どの約数が選ばれる確率も等しいものとする。 $v$ をその約数で置き換える。

操作が終わった後の $v$ の値の期待値を求めよ。答えは有理数となるため、その値を既約分数 $\frac{P}{Q}$ としたときの $PQ^{-1} \mod 10^{9}+7$ の値を出力せよ。

制約

$1 \le n \le 10^{15}$
$1 \le k \le 10^{4}$

解法

「約数を等確率で1つ選ぶ」という操作をしたときに、 $v$ のそれぞれの素因数の個数がどうなるか考えます。 $v$ にある素因数 $p$ が $m$ 個含まれているとすると、操作後の素因数 $p$ の個数は $0, 1, ..., m$ 個の中から等確率に1つ選ばれると考えることができます。そしてこの事象は素因数ごとに独立であるとみなすことができます。

そのため、まず $n$ を素因数分解してしまい、素因数ごとに考えます。ある素因数 $p$ についてだけ注目すると、「 $i$ 回操作後に素因数 $p$ が $j$ 個含まれている確率」を $dp_{p}\lbrack i \rbrack\lbrack j \rbrack$ とするようなDPを考えることができます。

遷移は、 $dp_{p}\lbrack i \rbrack\lbrack j \rbrack$ に $(j+1)^{-1}$ を掛けたものを $dp_{p}\lbrack i+1 \rbrack\lbrack j_{2} \rbrack (j_{2} = 0, ..., m)$ に加算することで計算できます。「 $k$ 回の操作後に素因数 $p$ が $j$ 個含まれている確率」、すなわち $dp_{p}\lbrack k \rbrack\lbrack j \rbrack$ を以降 $P\lbrack p, j\rbrack$ と表記します。

これを全ての素因数について計算すると、全ての $n$ の約数について $v$ が最後にその数になっている確率を計算できます。ちょっと数式がごちゃごちゃするので、仮に $n$ の相異なる素因数が $p_{1}, p_{2}$ の2種類だとして、それぞれの個数を $m_{1}, m_{2}$ とします。

このとき $n$ の約数は $p_{1}^{j_{1}}p_{2}^{j_{2}}$ と表現できて、最後にその数が残る確率は $P\lbrack p_{1}, j_{1}\rbrack P\lbrack p_{2}, j_{2}\rbrack$ となります。求めたいのは期待値なので、 $p_{1}^{j_{1}}p_{2}^{j_{2}} P\lbrack p_{1}, j_{1}\rbrack P\lbrack p_{2}, j_{2}\rbrack$ を全て合計すればよいです。

これらを約数ごとに全て計算してもよいですが、さらに簡単にする方法があります。求めたい値は $p_{1}^{j_{1}}p_{2}^{j_{2}} P\lbrack p_{1}, j_{1}\rbrack P\lbrack p_{2}, j_{2}\rbrack$ を全ての $j_{1} = 0, ..., m_{1}$ と $j_{2} = 0, ..., m_{2}$ の組み合わせについて合計したものですが、これを分配法則を使ってまとめると

$(p_{1}^{0}P\lbrack p_{1}, 0\rbrack + p_{1}^{1}P\lbrack p_{1}, 1\rbrack + \cdots + p_{1}^{m_{1}}P\lbrack p_{1}, m_{1}\rbrack) \times (p_{2}^{0}P\lbrack p_{2}, 0\rbrack + p_{2}^{1}P\lbrack p_{2}, 1\rbrack + \cdots + p_{2}^{m_{2}}P\lbrack p_{2}, m_{2}\rbrack)$

という形になり、 $p_{1}$ と $p_{2}$ を完全に分離できます。そのためそれぞれで値を求めておいて、最後に掛け算する方法でも期待値を求めることができます。

ここまでの話は素因数の種類数が2個でない場合でも成り立ちます。それぞれの素因数ごとに値を求めて全部掛け算すればよいです。

ACコード

（分配法則不使用）Codeforces
（分配法則使用）Codeforces

分配法則使用コードのほうが圧倒的にシンプルなのでオススメです。

F. Alex and a TV Show

Codeforces

問題概要

$1, ..., n$ までの番号が付けられた多重集合がある。始めはどの集合も空である。

以下の4種類のクエリを $q$ 個処理せよ。

1 x v 番号 $x$ の集合を $v$ 1つだけの集合に置き換える。
2 x y z 番号 $x$ の集合を、番号 $y, z$ の集合の和集合に置き換える。
3 x y z 番号 $x$ の集合を、番号 $y, z$ の集合の「直積集合」に置き換える。ただしここでは要素同士の組の代わりに、それらの要素の最大公約数を直積集合の要素とする。
4 x v 番号 $x$ に含まれる要素 $v$ の個数の偶奇を出力する。

制約

$1 \le n \le 10^{5}$
$1 \le q \le 10^{6}$
クエリ1, 4について、 $1 \le v \le 7000$

解法

それぞれの集合の状態として、単純に各値の個数や偶奇を持っていてはクエリの処理が間に合いません。特に最大公約数を求める処理が厄介なので、これを処理しやすいような状態の持ち方を考える必要があります。

状態 $state\lbrack x \rbrack\lbrack v \rbrack$ を、「集合 $x$ に含まれる要素のうち、 $v$ を約数に持つ要素の個数の偶奇」とするような状態を持ちます。このときクエリ2は $v$ ごとに要素数を足せば良いので、偶奇をビットで管理している場合はXORで計算できます。

またクエリ3の結果 $v$ を約数に持つ要素の個数は、集合 $y, z$ それぞれで $v$ を約数に持つ要素の個数の積になります。そのためビットで管理している場合はANDで計算できます。

クエリ1は単純に $v$ の約数全てのビットを立てたものに置き換えれば良いので、これでクエリ1, 2, 3の処理が効率的にできることが分かりました。あとは肝心のクエリ4です。

このクエリを処理するためには、「 $k$ を約数に持つ要素の個数の偶奇 $(k=1, ..., 7000)$ 」から「 $v$ の個数の偶奇」を求める必要があります。これは包除原理を用いて求めることができて、結論を書くと

の倍数であり、と表現できるようなについて、
- $\alpha$ が同じ素因数を2つ以上含むなら（つまり、1より大きい平方数を約数に持つなら）無視
- そうでない場合、
  - $\alpha$ に含まれる素因数が偶数個なら、+1倍
  - $\alpha$ に含まれる素因数が奇数個なら、-1倍

したものをすべて足すと求めることができます。ただし今回は偶奇を表すビットなので、+1倍と-1倍を区別する必要はありません。

この証明はちょっと面倒なので書きませんが…AtCoderの「LCM Rush」の解説、またその問題などを扱っているtsutajさんの包除原理まとめPDFなどが参考になると思います。

これでクエリ4の解を求めることができます…が、計算量を確認すると $O(7000q)$ となり単純計算で70億。全てのクエリをbitsetを用いて高速に処理できるよう前計算などをしておくことで、何とか間に合います。キツいですね。

ACコード

Codeforces

2018-12-30

AGC030 B - Tree Burning

AtCoder 競技プログラミングプログラミング

B - Tree Burning

今回は私自身がAB2完で実質的にこの1問しか解説を書けないのと、この1問だけでかなり説明が長くなりそうなので、単独記事にします。

Twitter見ていると微妙に色々違う解法があるようで…？私が本番で考察した内容をベースに書きます。他の人が書いていることとズレがあるかもしれないので、そこはご注意ください。

はじめに

以降の説明で使う方向を定義しておきます。高橋くんの家を円の上側に置き、問題文の座標と同じ反時計回りの向きを「左」、その逆向きを「右」とします。

また説明を簡単にするため、与えられる木の座標値 $X_{i}$ とは別に、座標の測り方を逆にして、逆向きに回った時に $j$ 番目にある木の座標値 $Y_{j}$ を定義しておきます。これらは同じ木をどちら側から訪れるかによって2通りの座標値を付けているだけであることに注意してください。

具体的には $Y_{N+1-i} = L - X_{i}$ で計算できます。 $X_{i}$ も $Y_{j}$ も木の位置を1-indexedで扱い、 $X_{0} = Y_{0} = 0$ としておきます。

f:id:betrue12:20181230210016p:plain

部分点解法

まず部分点ですが、DPをします。「家から左に $i$ 本、右に $j$ 本の木を訪問済みで、最後に訪れたのが左側の木なら $k=0$ 、右側の木なら $k=1$ であるときの最大移動距離」を $dp \lbrack i \rbrack\lbrack j \rbrack\lbrack k \rbrack$ とします。

このようにDPの状態を定義すると、左右合計で $N$ 本の木を訪れた時点で終わりなので、 $dp\lbrack i \rbrack\lbrack N-i \rbrack\lbrack k \rbrack$ を $i=0, ..., N$ および $k = 0, 1$ の範囲で全て求めたもののの最大値が答えになります。家の座標を $X_{0} = Y_{0} = 0$ としているので、初期条件は $dp\lbrack 0 \rbrack\lbrack 0 \rbrack\lbrack k \rbrack = 0$ です。

遷移を考えます。 $dp\lbrack i \rbrack\lbrack j \rbrack\lbrack 0 \rbrack$ は左に $i$ 本、右に $j$ 本の木を訪問済みで、最後に左側 $X_{i}$ の木を訪れている状態です。ここからは2通りの移動ができて、

さらに左に進み、 $X_{i+1}$ の木を訪れる。加算される移動距離は $X_{i+1} - X_{i}$ で、 $dp\lbrack i+1 \rbrack\lbrack j \rbrack\lbrack 0 \rbrack$ に遷移する。
向きを変えて右に進み、 $Y_{j+1}$ の木を訪れる。加算される移動距離は $X_{i} + Y_{j+1}$ で、 $dp\lbrack i \rbrack\lbrack j+1 \rbrack\lbrack 1 \rbrack$ に遷移する。

という遷移になります。

f:id:betrue12:20181230211600p:plain

$dp\lbrack i \rbrack\lbrack j \rbrack\lbrack 1 \rbrack$ からの遷移も同様に考えることができます。このDPを回すと $O(N^{2})$ で計算が終わり、部分点を取ることができます。

部分点獲得コード

（配るDP）Submission #3900997 - AtCoder Grand Contest 030
（貰うDP）Submission #3893900 - AtCoder Grand Contest 030

DPの実装における違いとして、いわゆる「貰うDP/配るDP」というものがあります。本番中の実装は「貰うDP」でしたが、「配るDP」のほうが文章化しやすかったので今回の説明は「配るDP」で書いています。この問題はどちらで解いても大差ないです。

あと、 $dp\lbrack N \rbrack\lbrack N \rbrack\lbrack k \rbrack$ とか実際に要らないところまで回してしまっているのですが、まあ計算時間が約2倍になるだけで十分間に合うので…添字の演算を増やしてつまらないバグを混入させたくないので、私はコンテスト本番だとこういう実装をたまにやります。