2019-06-22

yukicoder No.778 クリスマスツリー

お題箱より。

解法

飾りを頂点0を根とする根付き木とみなします。言葉を言い換えると、求めるものは以下の2条件を満たすペア $(i, j)$ の個数です。

頂点 $i$ が頂点 $j$ の先祖である。
頂点番号について、 $i \lt j$ である。

ここでの「先祖」は、ある頂点の親、その親、その親…を根まで辿った頂点全てを指します。また、先祖と逆の関係にあるものを「子孫」と表現することにします。

つまり「位置関係（親子関係）」と「頂点番号の大小関係」の2つが条件になっています。このような問題では、片方の条件が扱いやすいような探索順番で頂点を見ていきながら、データ構造などを用いてもう片方の条件を満たすものを効率的に数える、という方法が有効であることが多いです。

そのような解法を2つ紹介します。

解法1

解法1では、親子関係を扱いやすい探索順で探索していくことを考えましょう。深さ優先探索で頂点を1つずつ見ていくことを考えます。

木の深さ優先探索では「今見ている頂点の先祖にある頂点たち」の集合を管理しながら探索することができます。具体的には頂点 $i$ を訪れたとき、以下のような手順で処理します。

まずは、頂点 $i$ とその先祖たちについて求めたい何かを計算する。（今回の場合は、 $i$ より番号の小さい先祖の個数を答えに足す）
先祖たち集合の中に頂点 $i$ を加える。
頂点 $i$ の子それぞれについて、再帰的に同じ処理を行う。
子を全て処理し終わって頂点 $i$ を出る時、先祖たち集合から $i$ を除く。

先祖たち集合として set を利用したC++の実装イメージは以下です。処理全体で同じものを使うので、グローバル変数にするか参照渡しで渡してあげてください。

set<int> ancestors;
void dfs(int i){
    ans += <iより番号の小さい先祖の個数>;
    ancestors.insert(i);
    for(int j : child[i]) dfs(j);
    ancestors.erase(i);
    return;
}

あとは、各頂点 $i$ を訪れた時に「 $i$ より番号の小さい先祖の個数」を効率的に求めることが必要です。これはデータ構造を用いましょう。上記のコード中でsetを使っている代わりに、頂点番号をインデックスとしたBITやセグメント木を用いればよいです。

解法1 ACコード

#353465 No.778 クリスマスツリー - yukicoder

これは

親子関係を扱いやすい探索順にして、
頂点番号の大小関係をデータ構造で処理する

という解法でした。個人的にはこちらの解法が解きやすくてオススメです。

解法2

次に公式解法のほうです。こちらは解法1とは逆で、

頂点番号の大小関係を扱いやすい探索順にして、
親子関係をデータ構造で処理する

というものになっています。

頂点番号を大きい方から見ていくことを考えます。そうすると、ある頂点 $i$ を見ているときに数えるべきものは、

既に見た頂点であって、頂点 $i$ の子孫であるものの個数

となります。解法1では数える条件が「頂点番号が $i$ より小さい」だったので区間和が使えましたが、「子孫である」という条件はどう扱いましょう？

ここで使えるのがオイラーツアーというテクニックです。これは根付き木に対して「DFSで訪れた頂点の順番を、行き帰り含めて全て並べた数列」を求めたものです。

英語ページですが、図があったほうが良いと思ったので参考としてこちらを紹介します。

Euler Tour of Tree - GeeksforGeeks

このオイラーツアーの数列において、部分木（ある頂点自身とその子孫からなる木）は連続した1つの区間を構成しています。つまりオイラーツアーの数列に対応したBITを作ると、「頂点 $i$ の子孫であるものの個数」は区間和として効率的に計算することができます。

つまり頂点番号を大きい方から見ていきながら、それぞれの頂点 $i$ を見る時に

頂点 $i$ 以下の部分木に対応するオイラーツアー上の区間について、BIT上で区間和を取り答えに加算する。
頂点 $i$ に対応するオイラーツアー上の点1箇所について、BIT上で1を加算する。

のように処理することで解けます。一般にオイラーツアーでは1つの頂点のインデックスが複数個入るので、値を足す際には注意してください。この問題の場合はどこでもいいので1箇所に足せば大丈夫です。

解法2 ACコード

#353478 No.778 クリスマスツリー - yukicoder

2019-06-20

スクリプト言語などで競プロをすることについて

「スクリプト言語」と呼ばれるRuby、Pythonなどの言語に代表される、比較的実行速度の遅い言語で競技プログラミング（特にAtCoder）をすることについて。

最近色々ともやもやすることが多いので、思っていることを書きます。まさにこれらの言語を使っている方々、これらの言語を使うことについて何か物申したがる方々、そしてコンテストを運営されている方々それぞれに向けて。

長いです。興味があれば読んでください。

2023/03/06追記

この記事の内容は、公開当時である2019年頃のTwitter 競技プログラミングコミュニティに関するものです。いくつかの要因で現在このような風潮は弱くなっていると感じます。記事を読まれる際はその点にご注意ください。当時のような風潮が再び蔓延しないことを願います。

私の立場

私は競技プログラミングを始めた当初はRubyを使っていました。AtCoder青まではRubyのみで問題を解いていました。

その後、徐々に速度面での限界を感じてC++への移行をしました。現在はratedコンテストでは（多倍長整数を使いたいなどの）特別な理由がない限りはC++を使っています。

現在AtCoder橙ですが、もし仮にRubyだけを使い続けていたとしたら橙にはなれていない（もしくは、もう数年かかっている）と思っています。

スクリプト言語での競技プログラミングについて

実際に使っている方は十分身に沁みていると思いますが、問題によっては想定解法を実装してもTLEが出てしまい通せないことがあります。これは確かな事実です。

もちろんスクリプト言語の中でもその速度差はあり、私の体感ではPython（いわゆる普通のPython）よりはRubyのほうが多少速いように思います。一方でPythonにはPyPyという高速な実装があり、これはRubyより遥かに高速です。競技プログラミングでもよく活用されています。

なので一概には言えませんが、私がRubyで問題を解いていた頃は、AtCoderのratedコンテストの点数で

400点以下の問題は素直な実装でほぼ通る
500～600点には、定数倍高速化を考慮しない実装では通りにくいものが存在する
700点以上では、体感でおよそ半分ほどの問題は通すために（可読性を損なうレベルの）定数倍高速化が必要か、またはそれでも通らない

という印象です。ただこれはあくまで体感であり、コンテスト開催側が「○○点問題は○○言語でACできることを保証します」と宣言しているわけではありません。

ただしこれは私がRubyで問題を解いていたおよそ1年前の頃の話で、直近のコンテストでは300～400点でもスクリプト言語に厳しい問題が出題される頻度が上がっているように思います。AC者がいることから分かるように、定数倍高速化をすれば通るレベルのものではあります。

A - Darker and Darker

D - Lamp

そのため以前私は「青までならスクリプト言語で問題なく到達できる」と主張していましたが、この傾向が今後も続くようであればRubyで到達できるかは少し怪しいかもしれません。

やはり現在のAtCoderではC++に次いでPythonの利用者が多く、PythonユーザであればPyPyという強力な武器を使うことができます。AtCoderのコンテスト運営に携わっているとある方が「PyPyなら通ります」ということをよく言われていますし、やはり「PyPyで通る」が1つの基準になっているのかなと想像します。そのぶん他のスクリプト言語利用者には厳しい状況になっていくかもしれません。

また実際に問題をACできないこと以外に、「遅い言語で競プロをすることについてTwitter等で人々が物申す現象が定期的に発生する」というのも、実情としてはつらい点です。「物申す」という表現は失礼かもしれませんが、すみません、あえて書きました。私の受けている印象をそのまま書くとこういう表現になってしまいます。

問題をACしたいなら速い言語を使うべきという主張は「正論」です。ド正論です。正論だからこそ言いたくなってしまうのかもしれませんね。ただし、少なくとも私は「そんなことは百も承知でRubyを使っていた」わけで、分かりきった「べき」論を言及されることに正直良い気はしません。同じような思いのスクリプト言語使いも多いのではないでしょうか。特に最近はユーザが多く目立つからなのかもしれませんが、やたらPythonユーザに対する言及が多いように思います。

スクリプト言語利用者の方へ

先述した通り、問題面でも環境面でも今後より厳しい状況になっていく可能性があります。私は自身の経験もありこれらの言語で競技プログラミングをする人を応援したいと思っていますが、この状況を変えることはとても難しいと思っています。

まずお願いしたいのは、「通せない問題があることを受け入れる」ということです。もっと言うと「特定の言語で通せない問題を出題するコンテストに非がある」ということは無いし、「全ての言語でACを取れるようにコンテストを構成すべき」という主張は良くないものだと理解してほしいです。いえ、そう思うこと自体は構わないのですが、今の競プロコミュニティではそれをSNS等で主張することのデメリットが予想以上に大きく、またこの問題が完全に解消される望みが薄いことからあえて「良くない」という言葉を使っています。

コンテスト運営側としても、想定解法が通らないことはなるべく避けたいと思っているでしょう。しかし実際問題としてこれを本質的に改善することは非常に困難です。

その上で、「可能な限りハンデを緩和するテクニックを身に付ける」ようにしましょう。同じような処理に見えても、書き方1つで大きく実行時間は変わるものです。これは同じ言語を使っていて、競プロ歴が長い人やレートの高い人を頼るのが一番です。

Pythonであればこちらの記事が非常に有用です。

https://juppy.hatenablog.com/entry/2019/06/14/Python%5F%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E9%AB%98%E9%80%9F%E5%8C%96tips%5F%28Python%E3%81%A7Atcoder%E3%82%92%E3%82%84%E3%82%8B%E9%9A%9B%E3%81%AB%E5%80%8B

Rubyについては私が記事を書いていますが、あまり高速化技法に触れられていない点は申し訳ないです…

Rubyで競プロするときのTips - ARMERIA

そして、より高いレートを目指すのであれば「いずれは他の言語に移行する必要がある」ことを頭の片隅に入れておいてください。これも言語ごとの事情や今後の出題傾向に大きく依存しますが、目安としては「青になったらそろそろ」という感じです。言語の移行は簡単に出来ることではないですが、出来る限り道を用意していけたらと思っています。

そうではない方々へ

スクリプト言語を使っているのはあなたと同じ競プロerであり人間です。そのことを忘れないでください。

…と言うのも変な話ですが、こう言いたくなるくらい現状はつらいと思っています。意図的に攻撃的なことを言いたがるような一部の人は別としても、それに限らずこの話題は「正論の言及」をしたがる人が多いようです。

私の知る限り、スクリプト言語である程度の期間競プロをやっている人のほとんどは言語のデメリットを受け入れた上で競プロをしています。自分でも理解している正論をことあるごとに投げつけられるとつらい…ということは、この話題に限らず多くの人は経験があるのではないでしょうか。

そうではない人への言及、特に「通せない問題があることについてコンテスト運営に文句を言う人」への批判も見られます。確かにそのような人も中にはいるでしょうし、それは違うと私も思います。ただ得てしてこのような言及は攻撃的になりやすく、連鎖的に言及範囲が広くなり先述の「正論の言及」が発生しがちです。つらいです。

たかがTwitter、それなりの節度を持って好きなことを書けば良いと思います。ここで書いたことを辞めてくれと強制することもしないしできません。ただ、その言語を使っている当事者たちはそれを見てどう感じているのか、よかったら一度考えてみてください。私はつらいです。

コンテストを運営されている方々へ

言語間の速度差に関する問題は運営の方も頭を悩ませていると思います。よく言われるような、言語ごとの実行時間制限や制約の大幅な緩和をしてしまってはコンテスト全体の公平性を維持できない、という論は私も全く正しいと思います。

本音を言えば、先程書いた「400点以下の問題はRuby・Pythonの素直な実装でほぼ通る」状態はなるべく維持するように問題選択をしてくれたら嬉しい、とは思っています。AtCoder（特にBeginner Contest）の運営思想として、いわゆる「アスリート」指向の競技者に限らず広く参加者を集めたい、という思いがあるのであれば尚更です。ただ通ることを「保証する」ことはとても手間がかかると思うので、あくまで問題選択の指針として、です。

また、運営の方も我々参加者もTwitterがかなりの情報共有場になっているので、Twitterで頻繁に話題になっていると十分周知されていると勘違いしがちですが、実際にはそうでない参加者の方が多くいると思います。「全言語でACできることは保証していない」などの記述がAtCoderのサイトでちゃんと分かるようになっていると良いと思います。例えば非公式コンテストのs8pcではトップページにそのような記載がありますが、これと似たような記載が公式ratedにあってもいいのかなと。

あと例えばCodeforcesのDiv.3コンテストだと、時間制限が厳しい問題の問題文には「この問題では、Python利用者はPyPyを使うことを推奨します」という注意書きがあったりします。AtCoderもBeginner Contestであればそのような注意書きを入れるのも一案なのかな、と思っています。

文句を言われることは運営の方にとっても本意でないと思いますが、それらの文句は「悪意」ではなく「無知」によるものではないかと考えています。これらがより広く・公式に周知されるよう、今後改善されていくことを期待します。

おわり

同じ趣味を持つ人同士で、同じように問題を解いて、知識を共有して、レートを競い合って、なのに何故「遅い言語」の話題になるとこうなってしまうんだろう。この状況が少しでも変わるきっかけになればいいなと思い、この記事を書きました。

読んでくださってありがとうございました。

2019-06-17

AtCoder Beginner Contest 130 E - Common Subsequence

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

E - Common Subsequence

公式解説とほとんど同じだけど、二次元累積和が出てこないようなDPで解いたので記録しておきます。

解法

記法について

数列 $S_{1}, ..., S_{N}$ を単に $S$ 、数列 $T_{1}, ..., T_{M}$ を単に $T$ と書くことにします。

与えられた数列は1-indexedで扱い、「0要素目」として空の要素を考えることにします。空部分列" $()$ "は0要素目が入っているものとみなします。

基本の考え方

いくつか微妙に違う解き方を紹介しますが、基本の考え方は同じです。それは

$S$ のほうは $S_{i}$ より前で終わっていて、 $T$ のほうも $T_{j}$ より前で終わっているような等しい部分列の組に対して、 $S_{i} = T_{j}$ である要素をそれぞれくっ付けることによって、等しい部分列の組が新しく出来る

ということです。図で表すとこんな感じです。

f:id:betrue12:20190617232048p:plain

このような考え方を元にDPを組んでいく、という点ではどの解法も共通しています。

公式解説のDP

公式解説のDPは、もうすこし具体的に書くと以下のものを状態として定義しています。

$dp\lbrack i \rbrack\lbrack j \rbrack =$ 数列 $S$ の $i$ 要素目までを使いちょうど $S_{i}$ で終わるような部分列と、数列 $T$ の $j$ 要素目までを使いちょうど $T_{j}$ で終わるような部分列の組で、列として等しいものの個数。

このように定義すると、もちろん $S_{i} \ne T_{j}$ のときは $dp\lbrack i \rbrack\lbrack j \rbrack = 0$ です。そして $S_{i} = T_{j}$ のときはそれより前で成立している部分列の組全てから遷移してくるため、公式解説のように二次元累積和を用いて遷移を計算できます。

この場合、答えは $\sum_{i=0}^{N}\sum_{j=0}^{M}dp\lbrack i \rbrack\lbrack j \rbrack$ になります。

ちょっとちがうDP

これとは少し違うやり方として、以下のような状態を考えることもできます。

$dp\lbrack i \rbrack\lbrack j \rbrack =$ 数列 $S$ の $i$ 要素目までを使った部分列と、数列 $T$ の $j$ 要素目までを使いちょうど $T_{j}$ で終わるような部分列の組で、列として等しいものの個数。

ここでは $T$ のほうだけに「ちょうど終わる」条件を付けています。ここで、空部分列同士のペアはそれぞれ0要素目で終わるものと見なします。

このDPテーブルを $i$ が小さいところから埋めていく遷移を考えましょう。

「貰うDP」で考えます。 $dp\lbrack i \rbrack\lbrack j \rbrack$ に遷移してくる遷移元として2通り考えられます。まずは、

$S$ のほうは $S_{i}$ より前で終わっていて、 $T$ のほうは $T_{j}$ でちょうど終わるような部分列の組

です。その個数はまさに $dp\lbrack i-1 \rbrack\lbrack j \rbrack$ で、これは $dp\lbrack i \rbrack\lbrack j \rbrack$ にもそのまま含まれます。

それとは別に、 $S_{i} = T_{j}$ のときに限り次のようなものが考えられます。

$S$ のほうは $S_{i}$ より前で終わっていて、 $T$ のほうも $T_{j}$ より前で終わっているような部分列の組に対して、それぞれ $S_{i}, T_{j}$ を付け足したもの

この場合の遷移元は、 $\sum_{k=0}^{j-1} dp\lbrack i-1 \rbrack\lbrack k \rbrack$ になります。「 $T_{j}$ より前で終わっている」という条件に合致するように、 $T$ のほうの添字について $j-1$ までの和を取っている形です。

これは言うなれば「一次元累積和」ですね。この和は各 $i$ について遷移を計算する際に、 $j$ を0から $M$ まで順に動かしながら順番に足していくことで管理することができます。

このDPを最後まで計算して、 $\sum_{j=0}^{M} dp\lbrack N \rbrack\lbrack j \rbrack$ が答えです。

もうちょっとちがうDP

詳しくは説明しませんが、他にも次のような状態を定義しても解くことができます。

$dp\lbrack i \rbrack\lbrack j \rbrack =$ 数列 $S$ の $i$ 要素目までを使った部分列と、数列 $T$ の $j$ 要素目までを使った部分列の組で、列として等しいものの個数。

どっちも「ちょうど終わる」という条件がなくなってますね。この場合の遷移はLCS（最長共通部分列）のDP遷移によく似たものになり、「LCSっぽく解く」と言っている人は多分これで解いていると思います。これでも解けます。

この場合は答えは $dp\lbrack N \rbrack\lbrack M \rbrack$ になります。

このように、状態の定義がちょっとずつ違うので遷移と最終的な答えがちょっとずつ違ってきます。冒頭に書いたとおり、本質的にやっていることは同じです。

ACコード

Submission #5962772 - AtCoder Beginner Contest 130

私が本番書いた解法は2番目に紹介した「一次元累積和」のものなので、そのコードリンクです。

ちょっとずつ違う解き方が色々あるぶん、解法の情報を断片的に見るとかえって混乱するかもしれません。どのように状態を定義した場合の解法なのかを区別しながら理解し、どれでもいいので1つ決めてから解いてみることをオススメします。

2019-06-17

AtCoder Beginner Contest 130 F - Minimum Bounding Box

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

F - Minimum Bounding Box

解法

各座標軸ごとに、動きのイメージをつかむ

時刻を文字 $t$ で表し、 $t$ に依存する変数を $x(t)$ のように表します。

まず、 $x, y$ 座標を分けて考えてみます。 $x$ 座標だけに注目すると、それぞれの点は以下の3つにグループ分けできます。

グループ1： $x$ 座標が時間あたり1ずつ増え続ける点（R）
グループ2： $x$ 座標が変わらない点（U、D）
グループ3： $x$ 座標が時間あたり1ずつ減り続ける点（L）

これらのグループそれぞれには点がたくさん含まれているかもしれませんが、そのうち座標の最大値と最小値だけを考えればよいことが分かります。求めたい答えに関わるのはこれら全ての座標の最大値 $x_{\max}(t)$ と最小値 $x_{\min}(t)$ であり、グループ内では相対的な位置関係が変わることはないからです。

そのため各グループは最小値から最大値までの区間と捉えることができて、動作のイメージは以下のようになります。もちろん位置関係がこの図のようになっているとは限りませんが、3つの区間がそれぞれ速度1, 0, -1で動いていると見なすことができます。

f:id:betrue12:20190617200007p:plain

最大・最小の入れ替わり点を考える

$x_{\max}(t)$ は3グループの最大値のうち最も大きいもの、 $x_{\min}(t)$ は同様に3グループの最小値のうち最も小さいものになります。これらの時間変化がどのようになっているか考えてみましょう。

3つの最大値のうちある値が最大値になっている間は、 $x_{\max}(t)$ は傾き-1, 0, 1のいずれかで変動します。そしてこの傾きが変わるのは、3点のうちどれが最も大きいかが入れ替わるときです。つまりこの時間変化は折れ線グラフになっています。

$x_{\min}(t)$ についても同様なので、 $x_{\max}(t) - x_{\min}(t)$ も折れ線グラフになります。そうすると何となく、この傾きが変わる時刻だけを候補として考えれば良いのでは？という仮説が立ちます。これらの時刻を「傾きが変わる」時刻と呼ぶことにしましょう。

これらの時刻は、異なるグループ間で最大値または最小値が同じ座標値になるような時刻と考えることができます。その組み合わせはそんなに多くないので、もしこれらの時刻だけを調べれば十分なのであれば、そのパターン数はとても少ないです。 $x, y$ 軸それぞれについてこのような時刻を列挙し、全探索しても十分間に合うでしょう。

この仮説が本当に正しいのか、もう少し細かく考えていきましょう。

本当に大丈夫？

ここまでは座標1軸だけで考えてきましたが、実際には2軸ありましたね。求めたいのは $(x_{\max}(t) - x_{\min}(t)) \times (y_{\max}(t) - y_{\min}(t))$ の最小値であり、この時間変化は折れ線グラフになるとは限りません。この式を $f(t)$ と置きましょう。

調べたいことは、先程の「傾きが変わる」時刻だけを調べれば十分かどうか。逆に言うと、 $x_{\max}(t), x_{\min}(t), y_{\max}(t), y_{\min}(t)$ の傾きがどれも変化しないような時刻 $t$ で $f(t)$ が最小値を取ることがあり得るかどうか？です。（ただし「傾きが変わる」時刻に挟まれた区間内の傾きがずっと0で、最小値を取り続けている場合は除きます）

結論を書いてしまうと、そのような場合は基本的には存在しないことが分かります。例外は「スタート時点である時刻0のときが最小値である」場合です。

このことを確かめていきましょう。時刻 $t$ における、 $x_{\max}(t) - x_{\min}(t)$ と $y_{\max}(t) - y_{\min}(t)$ の変化量の符号で場合分けします。それぞれの単位時間あたりの変化量を $dx, dy$ とします。

$dx \ge 0$ かつ $dy \ge 0$ の場合

このときは $f(x)$ は（広義）単調増加です。そのため途中の値で最小値を取ることはありません。

$dx \le 0$ かつ $dy \le 0$ の場合

このときは逆に $f(x)$ は（広義）単調減少です。そのため途中の値で最小値を取ることはありません。

$dx \lt 0$ かつ $dy \gt 0$ の場合、あるいはその逆

残ったのはこのケースです。このとき $f(t)$ はどうなるでしょうか。

どの値の傾きも変わらないような区間においては、 $x_{\max}(t) - x_{\min}(t)$ と $y_{\max}(t) - y_{\min}(t)$ はそれぞれ直線とみなせます。ここで $dx \lt 0$ かつ $dy \gt 0$ より、 $f(t)$ は正の実数 $a, c$ と実数 $b, d$ を用いて

$f(t) = (-at+b)(ct+d)$

と表すことができます。これは $t$ に関して放物線になり、2次の係数 $-ac$ が負であることから上に凸な放物線になります。そのため途中の値で極大値を取ることはありますが、最小値を取ることはありません。

以上の場合分けにより、 $f(t)$ の最小値を調べるには、 $x_{\max}(t), x_{\min}(t), y_{\max}(t), y_{\min}(t)$ のいずれかの「傾きが変わる」時刻だけを調べれば良いことが分かりました。これを全て列挙して全部試すと、答えを求めることができます。

※余談ですが、もしこの問題が「有限の時間だけ動かした場合の最大値を求めよ」という問題だったら、極大値を調べないといけないのでこのような解法は成り立ちませんね。

おまけ：実装をサボる

最後に実装についてちょっとしたテクを紹介します。先程まで説明してきたように、 $x, y$ 軸それぞれについて、各グループごとに最大値と最小値を出して、異なるグループのペアを全通り作って、それぞれの速度を考慮しながら最小値・最大値同士が交わる時刻を出して…と計算していくと確かに候補となる時刻を列挙できます。

ただ、場合分けが多くてちょっと面倒ですよね。もっと雑に集めることで、細かいことを気にしなくてもいいようにしましょう。

まず点たちを、LRUD の移動方向ごとに4つのグループに分けます。それぞれのグループから $x, y$ 軸それぞれについて最大値と最小値を出してきます。それらを $x, y$ 軸それぞれについてごちゃまぜに集めてしまい、 $X, Y$ とします。

そうすると、下記の時刻を全て集めたものの中に、必ず最小値を実現する時刻が入っていることが分かります。

0
$x_{1}, x_{2} \in X$ について、 $d = |x_{1} - x_{2}|$ としたときの、 $d$ と $\frac{d}{2}$
$y_{1}, y_{2} \in Y$ について、 $d = |y_{1} - y_{2}|$ としたときの、 $d$ と $\frac{d}{2}$

つまり、速さ1で動く点と動かない点が交わる時刻は（交わるとすれば）その距離と同じ値であり、逆方向に速さ1で動く2点が交わる時刻はその距離の半分です。ならばそれらの時刻は、上記の方法で得られる値を全てかき集めた中に必ず入っているはずです。

もちろんそうでない時刻もいっぱい入っているわけですが、「最小値を実現する $t$ が必ず入っている」ことさえ保証できていれば、そうでない時刻が候補に入っていても最小値を求める上で影響は与えません。

候補の個数は $X, Y$ の要素数がそれぞれ最大で8個であることから256点くらいになりますね。点の個数が高々 $10^{5}$ 個なので全探索で十分間に合います。

ACコード

Submission #5982952 - AtCoder Beginner Contest 130

コードに関する細かい補足としては、候補となる時刻のうち0は明示的に入れていないのですが、 $x_{1} = x_{2}$ の場合に自動的に入るようになっています。

またこれも小ネタですが、最初に全部の座標を2倍しています。先述の通り時刻の候補として $\frac{d}{2}$ が出てくるので、全部偶数にしてしまうことで切り捨てを防ぐことができます。これで普通に解いて、最後に答えを1/4すればOKです。

2019-06-10

AtCoder Regular Contest 098 F - Donation

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

お題箱より。

F - Donation

私も公式解説を見て通したので、公式解説の流れで書いていきます。

解法

時間を逆回しにしてみる

考察を進めていく順番ですが、まず「時間を逆回しにする」ことを考えてしまったほうが良いように思います。普通にゲームを進めると寄付をしていくごとに訪れることができる頂点が減っていきますが、頂点が減ることによるグラフの分断は扱いにくいことが多いです。そのため時間を逆回しにすることで頂点が増えるようにして扱いやすくします。

時間を逆回しにすると、 $B_{i}$ 円寄付するという行為は $B_{i}$ 円もらうという行為に変わります。また $A_{i}$ 円ないと頂点 $i$ に入れないという条件は、 $A_{i}$ 円ないとその頂点から出れないという条件に変わります。

では頂点 $i$ に最初に入るための条件はどうなるでしょうか。未訪問の頂点に入ったときには、 $B_{i}$ 円をすぐにもらってしまうのが良いです。それを貰った後に $A_{i}$ 円以上の所持金を持っている必要があるので、入るためには $A_{i} - B_{i}$ 円以上の所持金が必要であることが分かります。所持金が0未満になることはないので、 $C_{i} = \max(A_{i} - B_{i}, 0)$ としておきます。

つまり、 $C_{i}$ が大きい頂点ほど「入りにくい」頂点であるということが言えます。 $C_{i}$ が小さいところから回ってお金を集め、 $C_{i}$ が大きいところを攻略していくような方針になります。

また所持金は増えていく一方なので、一度入った頂点に後から入れなくなるということはありません。そのため「今どこの頂点にいて、どの頂点に寄付済みであるか」という複雑な状態ではなく、「今どの範囲の頂点を動き回ることが可能か（その範囲のお金は全て回収済み）」という視点で状態を管理することができます。この点で思考がシンプルになることが、時間を逆回しにすることの大きなメリットだと思います。

DPを考える

それでは実際に値を求めていきましょう。目的は元々の問題におけるスタート、つまり逆回しした時のゴール時の所持金を最小化することです。

ゲームの流れを追っていくにあたり、ゴール時の所持金はこれから求めるものなので、スタート時の所持金も当然分かりません。ただこれはあまり気にする必要がなくて、スタート時は所持金0円として、必要になったときに追加でお金を足すと考えても良いからです。各頂点でもらうお金の総額は固定なので、この「追加で足す金額の合計」を最小にするように動けばそれが最適になります。

イメージとしては $C_{i}$ が小さいところから回っていくので、まずは $C_{i}$ が小さい頂点だけで構成された連結成分を考え、その連結成分の全頂点のお金をもらうために追加のお金が最小でどれだけ必要かを求めます。その値を利用して、より大きな連結成分に対する答えを求めていくようなDPをします。

より具体的に説明します。以下のようなDPの値を考えます。

$dp\lbrack S \rbrack =$ ある頂点集合 $S$ に対して、 $S$ の全頂点のお金をもらうために必要な追加のお金の最小値

ここで $S$ としては連結であるもの、より正確には $S$ に属する頂点とそれらを結んだ辺だけからなる部分グラフを $G_{S}$ として、 $G_{S}$ が連結であるものだけを考えることにします。

$S$ の中で $C_{i}$ が一番大きい頂点を1つ選んで $x$ とします。そうすると $x$ は $S$ の中で最も「入りにくい」頂点であることが分かります。その頂点を境にして、 $S$ はさらにいくつかの頂点集合に分断されます。これらの頂点集合を $s_{0}, ..., s_{K}$ としておきます。

$S$ に含まれる頂点からもらうお金の合計を $T_{S} = \sum_{i\in S}B_{i}$ と表記することにします。 $s_{0}, ..., s_{K}$ に対して既に $dp\lbrack \cdot \rbrack$ の値が求まっているとします。このときに $S$ の回り方としては、以下のようなものが最適となります。

$s_{0}, ..., s_{K}$ から、スタート地点を含む集合を1つ選ぶ。これを $s_{k}$ とすると、まずは所持金 $T_{s_{k}} + dp\lbrack s_{k} \rbrack$ を持った状態で $s_{k}$ の全頂点を回り終える。
次に頂点 $x$ を訪れる。このとき所持金が足りなければ追加する。ここで追加する金額は $\max(0, C_{x} - (T_{s_{k}} + dp\lbrack s_{k} \rbrack))$ となる。
$s_{k}$ に含まれているもの以外の頂点を訪れ、お金を回収する。頂点 $x$ が最も入りにくい頂点なので、残りの頂点はお金を追加することなく回ることができる。

f:id:betrue12:20190610221926p:plain

ここまでで追加した合計金額を計算すると、 $dp\lbrack s_{k} \rbrack + \max(0, C_{x} - (T_{s_{k}} + dp\lbrack s_{k} \rbrack)) = \max(dp \lbrack s_{k} \rbrack, C_{x} - T_{s_{k}})$ となります。これを全通り試して一番小さいものを $dp\lbrack S \rbrack$ として採用すればよいです。

このDPは「ある集合 $S$ の中で $C_{i}$ が一番大きい頂点 $x$ を1つ選び、 $x$ で分断される部分集合たちのDPの値から計算する」という構成になっています。つまり小さい方から計算していくなら、 $C_{i}$ の値が小さい頂点から1つずつグラフに足していき、それによって出来る連結成分ごとにDPの値を計算していけばよいです。これはUnion-Findを用いて計算していくことができます。

ACコード

Submission #3924856 - AtCoder Regular Contest 098

2019-06-10

AtCoder Beginner Contest 129 E - Sum Equals Xor

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

E - Sum Equals Xor

解法

※ $a$ と $b$ のXOR演算を、 $a \oplus b$ という記号で表すことにします。

まず注目すべきは $a+b = a \oplus b$ という条件です。これは知識として覚えておくと得な性質なのですが、XOR演算は繰り上がりのない足し算と思うことができます。

このことを確かめるために、 $a, b$ のある桁のビットとして考えられるパターンを列挙してみましょう。

$a, b$ の $d$ ビット目	$a \oplus b$ への影響	$a + b$ への影響
$0, 0$	$d$ ビット目が0になる	$d$ ビット目が0になる
$0, 1$ または $1, 0$	$d$ ビット目が1になる	$d$ ビット目が1になる
$1, 1$	$d$ ビット目が0になる	$d$ ビット目が0になり、1つ上のビットに1繰り上がる

繰り上がりが生じる $(1, 1)$ の場合を除いて両者は一致していることが分かります。そして繰り上がりのあるところでは $a+b$ のほうが大きくなります。

このことから $a+b = a \oplus b$ という条件は、ビットで考えた足し算において繰り上がりが1回もない、つまりどの桁のビットも $(1, 1)$ でないことと同値であると分かります。

そのため $a, b$ の各ビットの選び方は $(0, 0), (0, 1), (1, 0)$ の3通りの選び方があります。これで $a+b = a \oplus b$ という条件はクリアです。

次に $a+b \le L$ という条件を考えます。ここで、

ある上限値以下で条件を満たす値の個数を求める問題である
上限値 $L$ が非常に大きい
桁（ここではビット）に関する条件が存在する

という性質があるときには、桁DPで解ける可能性が非常に高いです。

ということでDPを組みましょう。桁DPの基本は、状態を以下のような形で持つことです。

$dp\lbrack (どの桁まで見て) \rbrack\lbrack (これまでの状態が○○で) \rbrack \lbrack (上限より小さいことが確定している・いない)\rbrack$

真ん中に入るのは桁にまたがるような条件です。例えば「桁和が $M$ の倍数であるもの」を数える場合には、真ん中には「これまでの桁和を $M$ で割った余り」などが入りますね。今回はそのような条件が特にないので不要です。そのため

$dp\lbrack i \rbrack\lbrack j \rbrack =$ 上から $i$ 桁目までを決めて、その桁までが $(0, 0), (0, 1), (1, 0)$ の3通りから選ばれていて、 $a+b$ が $L$ より小さいことが確定している $(j=1)$ /いない $(j=0)$ ような選び方の個数

とすることができます。（この記事においては、一番上の桁を1桁目としておきます）

遷移を考えましょう。上の桁から順番に考えていく時には、桁DPの遷移は以下のように考えることができます。

からの遷移（より小さいことが確定している）
- このとき $i$ 桁目の値はどのように選んでもよい。 $L$ より小さいことが確定済みなので、 $dp\lbrack i \rbrack\lbrack 1 \rbrack$ に遷移する。
からの遷移（より小さいことが確定していない）
- このときの桁目の値を、の桁目の値をとして、
  - $d_{i} \gt l_{i}$ のとき、 $a+b$ が $L$ を超えてしまうのでアウト。ここには遷移できない。
  - $d_{i} = l_{i}$ のとき、変わらず $dp\lbrack i \rbrack\lbrack 0 \rbrack$ に遷移する。
  - $d_{i} \lt l_{i}$ のとき、 $a+b$ が $L$ より小さいことが確定するので $dp\lbrack i \rbrack\lbrack 1 \rbrack$ に遷移する。

ここで各桁の数字の組み合わせは $(0, 0), (0, 1), (1, 0)$ なので、 $d_{i} = 0$ となるものは1通りで $d_{i} = 1$ となるものは2通りであることに注意してください。

$L$ の桁数（文字数）を $N$ として、 $dp\lbrack N \rbrack \lbrack 0 \rbrack + dp\lbrack N \rbrack \lbrack 1 \rbrack$ が答えになります。

ACコード

Submission #5844961 - AtCoder Beginner Contest 129

2019-06-08

Codeforces Round #564 C. Nauuo and Pictures

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

Problem - C1 - Codeforces

Problem - C2 - Codeforces

問題概要

$n$ 枚の画像がランダムに表示されるWebサイトがある。各画像には重み $w_{i}$ が設定されていて、画像 $i$ の表示確率は $\frac{w_{i}}{\sum_{j} w_{j}}$ である。

画像を $m$ 回表示させる。このとき画像が1回表示されるごとにその画像の重みが変動する。各画像には0または1の値 $a_{i}$ が定められていて、表示された画像 $i$ について $a_{i} = 0$ であれば重みが-1、 $a_{i} = 1$ であれば重みが+1される。

画像を $m$ 回表示させた後の各画像の重みの期待値を、有理数 $\bmod 998244353$ で求めよ。

C1

制約

$1 \le n \le 50$
$1 \le m \le 50$
$a_{i}$ は0または1
$1 \le w_{i} \le 50$

解法

制約が小さいので、 $n$ 枚の画像それぞれについて別々に計算することを考えてみましょう。答えを求めたい画像を $x$ とします。

そうすると、 $x$ 以外の画像について具体的に何が選ばれたかはあまり興味がありません。

画像 $x$
画像 $x$ 以外の $a_{i} = 0$ である画像たち（グループ0とします）
画像 $x$ 以外の $a_{i} = 1$ である画像たち（グループ1とします）

の3つだけを区別すれば十分です。ここで、グループ0, 1に属する画像の初期重み合計をあらかじめ計算し、それぞれ $s_{0}, s_{1}$ としておきます。

以下のような状態を持つDPを考えます。

$dp\lbrack i \rbrack\lbrack j \rbrack\lbrack k \rbrack =$ 画像をこれまで合計 $i$ 回表示させて、画像 $x$ が $j$ 回、グループ0の画像たちが合計 $k$ 回表示されている確率

グループ1の画像たちが選ばれた回数が入っていませんが、合計回数が分かっているので $i-j-k$ で求められます。これらの情報があれば、この時点での

$x$ の重み $= w_{x} \pm j$ （ $a_{x} = 0$ ならマイナス、 $a_{x} = 1$ ならプラス）
グループ0の画像たちの重み合計 $= s_{0} - k$
グループ1の画像たちの重み合計 $= s_{1} + (i-j-k)$

が求められるので、そこから遷移確率を計算することができます。最終的に $dp\lbrack M \rbrack\lbrack j \rbrack\lbrack k \rbrack$ を使えば期待値を計算できます。

ACコード

Submission #55259545 - Codeforces

重みが負になるケースを無理やり計算しようとするとおかしなことが起こり得るので注意。負になるケースに正の確率で遷移することはないので、 if(dp[i][j][k] == 0) continue; のような1行を入れておけば大丈夫です。

C2

制約

$1 \le n \le 2\times 10^{5}$
$1 \le m \le 3000$
$a_{i}$ は0または1
$1 \le w_{i}$
$\sum_{i} w_{i} + m \lt 998244353$

解法

C2では制約が大きいので全部別々に計算することはできません。

$a_{i} = 0$ である画像たちをグループ0、 $a_{i} = 1$ である画像たちをグループ1とします。それぞれの初期重みの和を $s_{0}, s_{1}$ とします。

まずは1つ1つの画像が何回選ばれるかを考えずに、グループ0, 1それぞれの合計表示回数が確率いくらで何回になるかを考えます。すなわち以下のようなDPを考えます。

$dp\lbrack i \rbrack\lbrack j \rbrack =$ 画像をこれまで合計 $i$ 回表示させて、グループ0の画像たちが合計 $j$ 回表示されている確率

これはC1と同じような遷移で、状態数 $O(m^{2})$ で計算できます。

ここから1つ1つの画像について考えていきます。ある1つの画像 $x$ について考え、例えばそれがグループ0に属しているとします。グループ0の画像が $k$ 回選ばれた時の画像 $x$ の重みの期待値を $E_{k}$ と表記すると、画像 $x$ についての答えは $\sum_{k} (E_{k} \times dp\lbrack M \rbrack\lbrack k \rbrack)$ となります。

初期値は $E_{0} = w_{x}$ です。 $E_{k}$ から $E_{k+1}$ を計算できないか考えてみましょう。

グループ0の画像を $k$ 回選んでいる時点で、グループ0の重み合計は $s_{0}-k$ です。そのうち画像 $x$ の重みがいくらかによって遷移確率が決まり、その値は確率によって変動しますが…その期待値はまさしく $E_{k}$ として求められています。そのため $k+1$ 回目で画像 $x$ が選ばれる確率は $\frac{E_{k}}{s_{0}-k}$ とみなすことができて、その確率で $x$ の重みが1減るため

$E_{k+1} = E_{k} - \frac{E_{k}}{s_{0}-k} = E_{k}(1 - \frac{1}{s_{0}-k})$

と計算することができます。

さらにこの式から、 $E_{k}$ の値は初期値 $E_{0} = w_{x}$ に比例していることが分かります。つまり全ての $x$ についてこの $E_{k}$ の値を全部計算しなくても、 $E_{0} = 1$ とみなして $E_{k}$ を求め、 $\sum_{k} (E_{k} \times dp\lbrack M \rbrack\lbrack k \rbrack)$ まで計算してしまってから、最後に各 $x$ ごとに $w_{x}$ を掛けることで答えを求めることができます。

ここまではグループ0についての計算でしたが、グループ1の計算についても同様に求めることができます。グループ0のときは重みが0以下になってしまう場合に注意してください。

ACコード

Submission #55265191 - Codeforces

計算量は逆元計算を除くと $O(m^{2} + n)$ になるのですが、制約がまあまあキツ目なので重いところに逆元計算が掛かるとちょっと危なくなります。上記のコードは $p = 998244353$ として $O(m^{2}\log p + n)$ になっていますが何とか通りました。

必要な逆元は $s_{0}, s_{1}, s_{0}+s_{1}$ の前後にある高々 $m$ 個くらいなので、必要なものを前計算しておくことで $O(m^{2} + m\log p + n)$ に節約することができます。

解法

解法1

解法1 ACコード

解法2

解法2 ACコード

2023/03/06追記

私の立場

スクリプト言語での競技プログラミングについて

スクリプト言語利用者の方へ

そうではない方々へ

コンテストを運営されている方々へ

おわり

解法

記法について

基本の考え方

公式解説のDP

ちょっとちがうDP

もうちょっとちがうDP

ACコード

解法

各座標軸ごとに、動きのイメージをつかむ

最大・最小の入れ替わり点を考える

本当に大丈夫？

かつ の場合

かつ の場合

かつ の場合、あるいはその逆

おまけ：実装をサボる

ACコード

解法

時間を逆回しにしてみる

DPを考える

ACコード

解法

ACコード

問題概要

C1

制約

解法

ACコード

C2

制約

解法

ACコード

$dx \ge 0$ かつ $dy \ge 0$ の場合

$dx \le 0$ かつ $dy \le 0$ の場合

$dx \lt 0$ かつ $dy \gt 0$ の場合、あるいはその逆