Processing math: 100%

目次

デンソークリエイトプログラミングコンテスト2022(AtCoder Beginner Contest 239)D,F,G,Ex問題メモ

デンソークリエイトプログラミングコンテスト2022(AtCoder Beginner Contest 239)

電装とは、自動車の内部パーツのうち、電気・電子機器の総称。

D - Prime Sum Game

D - Prime Sum Game

問題

解法

制約が少ないので単純にループを回せばいいけど、より値の範囲が大きい場合でも可能な解法(公式解説のBonus)。

N を、2人の整数の和の取り得る最大値(=B+D)とする。

N までの、素数なら1、それ以外なら0の配列を作る。エラトステネスのふるいで O(NloglogN) で作れる。

0 1 2 3 4 5 6 7 8 9 10 11 ... 200
0 0 1 1 0 1 0 1 0 0  0  1 ...  0

「自身を含めたこの先 DC+1(青木君が自由に選べる幅)個の連続する整数の中に素数があれば0、なければ1」の配列を作る。
これを f(x) とする。枠をずらしながらの差分更新などで O(N) で作れる。

D-C+1 = 3

  x   0 1 2 3 4 5 6 7 8 9 10 11 ... 198 199 200
素数  0 0 1 1 0 1 0 1 0 0  0  1 ...  0   1   0
f(x)  0 0 0 0 0 0 0 0 1 0  0  0 ...  0   -   -

高橋君は、f(+C)=1 となる数を選べば、勝てる。AB の中にそのような整数が無い場合は、必敗。
存在するかどうかは、A+CB+C の合計が 1 以上かどうかで判定できる。O(N)

全体で O(NloglogN)

Python3

F - Construct Highway

F - Construct Highway

問題

解法

木に関するデータ構造についての典型を組み合わせた上で、ある程度の実装力が求められる。

最終的なグラフは N 頂点 N1 辺で全体が連結となり、その条件を満たすグラフはすなわち木となる。

よって、以下に1つでも該当するものはハナからアウト。

閉路の条件はUnionFindで、追加しようとしている辺が既に同じ連結成分で無いかチェックしていけばよい。

最初のM辺を追加し終わったら追加する辺を求めていく。
常に別々の連結成分に属する頂点同士を結んでいくことを繰り返せばいつの間にか木ができるはずなのだが、 下手に結んでしまうと上記アウト条件の4番目のような、残り次数0の独立した連結成分ができてしまう。

そのような場合というのは(最後以外で)互いに残り次数が1の連結成分同士を結んでしまう時。
よって、残り次数の多い連結成分から結んでいけば、回避できる。
以下の方法などで実装できる。

(連結成分の総次数, 連結成分内で次数が残っている頂点リスト) みたいにして順につなぐと完成。

また解説のように、「次数が残っている頂点リスト」を「残っている次数だけ頂点番号を重複させたリスト」にしておくと、 個数を気にせずpop・統合していけばよいので実装は楽になる。ただしリストの要素数が増えるため、統合にかかる実行速度は若干遅くなる。

Python3

G - Builder Takahashi

G - Builder Takahashi

問題

解法

ほぼ最小カット問題そのままなので、知ってるかどうかが大きかったか。

最小カットは辺にコストが設定されているが、 今回は頂点にコストがあるので、そこは少しグラフを工夫する。
頂点を2重にして、「どっかから入るための頂点」「どっかへ出るための頂点」に分け、 入→出を結ぶ辺にコスト Ci を設定すればよい。

さらに今回は、カットすべき辺を求める必要がある。

最大流を求めた後のグラフでもう一度始点から探索し、たどり着ける頂点→たどり着けない頂点を結ぶ辺が、その辺となる。

「容量が残っていない辺」とかだとダメで、ボトルネックが複数あった場合にどれを使うべきか判断できなくなる。

                    (※頂点を2重にする表現は省略)
    ①→②→③→④    最大流まで流した後のグラフでは
Ci       5   5        ②も③も容量が残っていないが、
                      通行不能にするのはどちらかだけでよい

Python3

Ex - Dice Product 2

Ex - Dice Product 2

問題

解法

O(NM) 解法

余裕のTLEとなるが、まずはゴールから計算していくことを考える。

現在の値が X=x であるときの残り回数期待値を f(x) とする。
xM+1 において、f(x)=0 である。

ゴール一歩手前 f(M) を求める。X=M である状態からサイコロを1回振ったときの残り回数は、

よってこれらをまとめると f(M)=1Nf(M)+1 より、f(M)=NN1 となる。
1が出たとき X が変わらないため、式の両辺に同じ値が出てくるが、そこは上手く移項して打ち消す。

f(M1),f(M2),... と徐々に減らした値が順次 O(N) で求まっていき、f(1) が求まると答え。

実際は、サイコロの目 k=1,2,...,N を調べる過程で kx>M となったら打ち切れるので、 f(x) の遷移先の個数は Mx となり、全体で均すと O(MlogM) で求められる。
まぁ、いずれにしろTLE。

想定解法

実は上記の話で、f(M)f(M2+1) は全て同じ値である。
なぜなら、いずれも 2 以上が出たらゴールなので、計算式が変わらないため。

また、f(M2)f(M3+1) も全て同じ値。
2 が出たら MM2+1 のどこかに遷移し、3 以上が出たらゴールのため。

このように、g(d)=d 倍まではゴールしない(d+1 倍ではじめてゴールする)場合の残り計算期待値、 という括りでまとめても問題ない。

M=39
x  >=40  39-20  19-14  13-10  9-8  7  6  5  4   3   2   1
d    0     1      2      3     4   5  6  7  9  13  19  39

g(d) の状態からサイコロの目 k が出たら、遷移先は g(d/k) となる。(切り捨て)

g(0)=0 を始点として d=1,2,... と順に求めていき、g(M) を求められれば答えとなる。

だが上の表を見ると、x が大きいときには1つの d が多くの x を代表するが、 中盤で1対1対応となり、終盤では飛び飛びになっている。g(d) を1つずつ求めるのも、終盤は非効率。

だが、実質的な状態数は、だいたい

の、約 2M 個の状態に限られることがわかる。
これらについて、f(x) または g(d) を求められればよいことになる。

実装方法はいろいろ考えられるが、例えば再帰関数で次のように求められる。

ただし同じ g(d) が何回も呼ばれうるため、高速化のためメモ化しておく。

O(M) 個の状態につき g(d) を求め、それぞれは O(d) 回の遷移先の計算をする場合、 全体では O(M3/4) となるらしい。

M=109 の場合は約 5.6×107 程度となるが、まぁ定数倍の関係か、実際にやってみると間に合う。

Python3