2020-05-18

CodinGame Spring Challenge 2020 参加記

CodinGame プログラミング競技プログラミングマラソンコンテスト

CodinGame Spring Challenge 2020に参加して、Legendリーグ57位でした！

f:id:betrue12:20200519105641p:plain f:id:betrue12:20200518193410p:plain

対戦動画をTwitterで見て、何となく面白そうだなと思って参加したらドハマリしました。睡眠時間と休日とCodeforcesのコンテスト2回分が犠牲になりましたが、Legendリーグに進出することができて嬉しいです。

戦略

完全にルールベースです。分かっている情報からマスの得点評価をして、経路のスコアを計算しながらDFSをして、いくつかの行動パターンに従って行動します。

試合を見ながら思いついた行動パターンやスコアの補正をどんどん入れていったので、勘で決めたパラメータがあちこちに散らばってカオスになりました…。

項目ごとに列挙していきます。

進行度判断

総得点の1/2が取られるまでを序盤、3/4が取られるまでを中盤、それ以降を終盤と定義し行動を少し変える。

じゃんけん

距離が近くて手が負けていたら逃げる。ただしスキルが使える時は相手に勝てる手にSWITCH。
逃げている途中の曲がり角で相手が見えなくなった瞬間に引き返して食われることが多いので、逃走中は引き返し禁止。
手が勝っているときに追いかけるのは、絶対に相手の後を通ってペレットを得られないので微妙かなと思っていた。ただ自分がやられるとルートを崩されて嫌なので、相手も同じかなと思い追加。

スキル

前記の迎撃SWITCH以外はSPEED連打。即逃げが必要な場面を除いて、使える時に使う。

マスの評価

どのマスが通行済（もうエサがない）かを記録。自キャラが通過したマス、視界内のマスで既にエサが消えているマス、相手の初期マスなど。
SPEEDを使うと交差点を通り過ぎた時に情報が得られずエサを見落とすことが多かったので、SPEED中でも次のマスから得られる情報が多いときは1マスしか進まないようにした。
最初は情報がないマスに均等に期待値（残り得点数÷不確定マス数）を当てていたが、探索の効率を根本的に改善する必要があったので重み付けだけでも追加。敵を見た位置の周辺や、その敵を前に見た位置からの最短経路上の重みを減らすようにした。
見えているペレットの状態と経路の形から、その周囲のペレットの存在/非存在がほぼ確定する場面がある。例えば、壁と見えているペレットに囲まれた不確定マスの領域があって、その中に自分と敵の初期位置が存在しない場合、その中のペレットは確実に存在。

f:id:betrue12:20200519103925p:plain

↑例えばこういうケースで入り口のペレットが見えていると、奥のペレットは全部残っていることが確定する。

f:id:betrue12:20200519110942p:plain

↑こういうマップ形状で奥の通路側のペレットだけ消えているのが見えた場合、その通路のペレットは高確率で取られている。

経路探索

大ペレットに向かうルート。大ペレットからBFSして一番近い自キャラに割り当てる。
DFSルート。基本的にこれで、ルートのスコアを計算しながらDFS。
未訪問の塊を掘りに行くルート。終盤に残っている塊を探すため、不確定マスだけで取った連結成分を求め、その中のペレット期待値合計が大きいところに行く。

経路スコア

色々補正項を入れていてカオス…

基本的な計算式は、マスのペレット期待値に距離で減衰する係数を掛けて合計。
味方を分散させるために、他の味方に近いマスは減点。
序盤に袋小路に行くと減点、逃走中に袋小路に行くと大幅減点。
勝てる敵がいるマスを通ると加点。
引き返しは無駄が多いので減点。
既に袋小路の中にいるときは奥まで取り切ると加点。これやらないと奥に1個残したりしてもったいなかった。

衝突回避

味方同士が衝突すると悲しい。敵との衝突は等しく損をしているし、避けるとおいしいルートを譲ることになるので放置。
各マスに「所有権」を設定し、各キャラの経路のうち最初の数ターン分で通るマスを所有扱いにして、他の味方が使わないようにした。
敵と何回も衝突しているときはSPEEDを使わないようにした。相手と同じ周期でスキルを使っているとタイミングが被るので、相手がSPEEDを撃っている間に潜り込むことができる。

リプレイ見てたらこんなの入れてたことを思い出した
2箇所同時にキレイに決まっていた pic.twitter.com/bOghRh6bfG
— アルメリア (@armeria_betrue) 2020年5月19日

コード

gistに載せようと思ったのですが公開禁止だそうで…最終的に800行くらいになりました。

色々試行錯誤してたときにWinMergeで差分追うことになって辛かったので、最初からgit使えば良かった…

雑感

やり慣れている人とは全然違うやり方をしているんだろうなという気がしています。BFS/DFS/UnionFindと大量のif文と手動調整パラメータで押し切りました。

じゃんけんの攻防も大事ではありますが、とにかく探索の効率で負けているとGoldで感じたので、そこをなんとかしようと頑張りました。見えている相手の位置をもとにマスに重みを付ける、見えているマスの情報から周りの状況を論理的に推論する、うろうろしたり引き返すなど非効率な行動を抑制する、こういった地道な改善によってLegendまで行けたと思います。

見えていない間の相手の行動を読んだり、先のターンの展開を予測したり、そういったところまでやるとゲームAIっぽいなあと思うんですけど、スキルも時間も足りなかった…上位勢がどういうアプローチをしているのか気になります。

ビジュアライザを眺めるだけでも面白く、実際の試合をすぐにIDE環境に持ってきて試行錯誤できるので改善しやすかったです。負けた試合と同環境でなるべく勝てるように改善する、というのが基本スタイルでした。一方で運に左右されがちなゲームなのにデータを大量に取るということがやりづらく、何が正解なのか分からなくなってしまうのは辛かったです。

めっちゃ楽しかった。次も参加したいです。

感想戦を経て追記

上位の人の方針ツイートを見たり反省会の配信にお邪魔したりしていたのですが、山登り/焼きなまし系やビームサーチ系に落とし込んで探索時間を上手に活用している印象でした。

私の方針だとほぼ時間を使わないのでTLEとは無縁だったのですが、とにかく「想定していない状況」に弱くて、特に大ペレットとキャラの初期位置がちょっと変な形だったときに最適とは言い難い行動を取ることが多かったです。またキャラごとに順番に経路を決めていたので、他の味方の良い経路を潰してしまうこともありました。

経路のスコア化はできていたので、もう少し頑張って行動や盤面のスコア化まで作っていれば、あとは探索アルゴリズムに任せれば特殊な状況でも総合的に判断してくれそうです。正直「不完全情報だしターン毎の制限時間50msだし焼きなませないだろう」と考えていたんですが、そこを何とかするのが上位勢の実力だなと思いました。

2020-05-18

AtCoder Beginner Contest 168 F - . (Single Dot)

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

F - . (Single Dot)

解法の理解というよりは実装慣れのほうが重要な問題だと思います。末尾につけているACコード例と対応させながら読んでいくといいかもしれません。

解法

図における座標軸は問題文に従い、北を上にして図示するようにします。一般的なXY平面とは異なるので注意してください（プログラミングでグリッド等を扱うときによく使われる取り方です）。

座標平面をグリッドのマスのように考えると、UnionFindで連結判定をしたりグリッド上でBFSをしたりして牛から到達可能なマス数を数える、という解法が思い浮かびます。しかし $1\times 1$ の領域を1つのマスとして扱うには座標の値が大きすぎます。そこで座標圧縮をします。

圧縮座標の取り方は細かい違いを考慮すると色々ありますが、この解説では以下のように取ります。

f:id:betrue12:20200518002554p:plain

それぞれの線分の端点の座標を集めてきてソート＆重複除去を行い、座標圧縮します。ここで実装上は無限に遠い座標（無限遠、十分大きな整数）を正負それぞれ含めておくと楽です。

そしてその座標値で区切られる長方形領域を、その左上の圧縮座標のインデックスと対応付けます。このようにすれば領域の面積が求められて、領域同士の連結判定もUnionFindなどで扱うことができます。

次に線分の扱い方を考えましょう。ここではそれぞれの線分から、各長方形領域について

その領域のすぐ上側に線分が存在する/しない
その領域のすぐ左側に線分が存在する/しない

という情報を求めてしまうと扱いやすくなります（下側/右側でも添字が1つずれるだけなので可能です）。例えば上図の縦線は、領域 $(2, 1)$ と領域 $(3, 1)$ の左側に線分が存在する、という情報にすることができます。

こうしてしまえば、例えばUnionFindを用いて各領域が接しているところについて「間に線分がなければ併合」という処理を行うことで連結判定ができるようになります。牛が存在する領域と連結な領域の面積を合計すれば答えになります。ただし無限遠の座標に対応する領域と連結であれば答えは INF です。

ACコード

Submission #13352386 - AtCoder Beginner Contest 168

実際に解く時には、手元で図を描いて、ちゃんと座標と領域の対応付けを決めてから実装に落とし込むと良いです。

2020-05-11

AtCoder Beginner Contest 167 E - Colorful Blocks

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

E - Colorful Blocks

解法

「隣り合うブロックの組であって同じ色で塗られている組」がちょうど $k$ 個あるとして、 $k=0, 1, ..., K$ についてそれぞれ求めた場合の数を合計することで答えを求めます。

ブロックは全部で $N$ 個なので、ブロックが隣り合っている箇所は $N-1$ 箇所です。このうちブロックが同じ色である箇所を $k$ 個選ぶ選び方は $_{N-1}C_{k}$ 通りです。

そして選んだ箇所を挟んだブロック同士は同じ色にしなければいけないので、結合してしまうと考えましょう。

f:id:betrue12:20200511092714p:plain

図で示すように、ブロックが同じ色である $k$ 箇所の選び方がどのようなものであっても、結合後のブロックは $N-k$ 個になります。そしてこれらのブロックの間は先ほど選ばなかった箇所なので、隣り合うブロック同士は異なる色である必要があります。

つまり「 $N-k$ 個のブロックに、隣り合うブロックの色が異なるように色を塗る方法の数」を求めれば良いです。これは、

1つ目のブロックは、自由に色を選ぶので $M$ 通り
2つ目のブロックは、1つ目のブロックの色以外から選ぶので $M-1$ 通り
3つ目のブロックは、2つ目のブロックの色以外から選ぶので $M-1$ 通り
…

と考えると、 $M(M-1)^{N-k-1}$ 通りと計算することができます。

よって、 $_{N-1}C_{k} \times M(M-1)^{N-k-1}$ を $k=0, 1, ..., K$ について合計すれば答えを求めることができます。

ACコード

Submission #13044373 - AtCoder Beginner Contest 167

2020-05-10

AtCoder Beginner Contest 167 F - Bracket Sequencing

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

F - Bracket Sequencing

解法

「正しい括弧列」について

この問題だと単に括弧列という言葉が使われていますが、どちらかと言うと「正しい括弧列」みたいな呼ばれ方をされることが多いです。

正しい括弧列の条件は、言葉で書くと

開き括弧と閉じ括弧の数が等しい。
それぞれの閉じ括弧について、それに対応する開き括弧がそれより前に出現している。

となりますが、これを ( を $+1$ 、) を $-1$ として見たときの先頭からの累積和で考えるのが定石です。すなわち上記の条件はそれぞれ累積和によって

全体の和がちょうど $0$ である。
先頭から累積和を取った時に、その最小値が $0$ 以上である。（つまり、先頭からどの地点までの累積和の値も負でない）

と書くことができて、これらを両方を満たすことが正しい括弧列であることの必要十分条件です。

f:id:betrue12:20200511080152p:plain

パーツを繋げられる条件を考える

与えられた「パーツ」である $S_{i}$ それぞれについて、累積和の最小値 $m_{i}$ と全体の和 $s_{i}$ を求めます。パーツ $S_{i}$ はこの2つの値の組 $(m_{i}, s_{i})$ で特徴づけられます。

全てのパーツを連結した文字列が先ほどの条件を満たせるかどうかを考えます。まず条件1について、全体の和は繋げ方に依らず全てのパーツについての $s_{i}$ の和になります。なのでこれが $0$ であるかどうかを調べれば良いです。

条件2について考えます。パーツを前から順番に繋げて行って、それまでの累積和（つまりそれまでに使ったパーツの $s_{i}$ の和）が $T$ であるとします。初期状態では $T=0$ です。ここにパーツ $S_{x}$ をつなげると、

パーツ $S_{x}$ の中での、先頭からの累積和の最小値： $T + m_{x}$
パーツ $S_{x}$ 終了地点での、先頭からの累積和： $T + s_{x}$

となります。このとき $T+m_{x}$ が負になってしまうと条件2に違反するので、それまでの累積和が $T$ であるときにパーツ $S_{x}$ を付けられる条件は $T+m_{x} \ge 0$ と表現できます。そして累積和 $T$ は $T + s_{x}$ に変化します。

言い換えると $m_{x}$ は「大きいほどパーツ $S_{x}$ 自身を付けられる条件が緩くなる」、 $s_{x}$ は「大きいほどそれ以降のパーツを付けられる条件が緩くなる」ような値だと考えることができます。

f:id:betrue12:20200511081221p:plain

最適な連結順序を考える

以上の考察から、なるべく条件を満たせるようにするにはどのような順序でパーツを連結していけば良いかを考えます。

まず $s_{i} \ge 0$ であるパーツは、付ければ付けるほど $T$ が増加して条件を満たしやすくなるので、付けられるようになったものから付けてしまって良いです。よって付けられる条件が緩いもの、つまり $m_{i}$ が大きいものから順番に使うことにします。

それから $s_{i} \lt 0$ であるパーツを使っていきます。これは付けるほど後が厳しくなっていくので $m_{i}$ と $s_{i}$ の両方が絡んできます。「条件の厳しいものを早く消化したい」と思うと $m_{i}$ が小さいものから、「後の条件を厳しくしたくない」と思うと $s_{i}$ が大きいものから使いたくなります。

では結局どうすれば良いのかと言うと、 $s_{i} - m_{i}$ が大きいものから順番に使うのが最適になります。

証明1

実は過去に書いた記事に全く同じ証明があります。こちらを参照してください。場合分けが必要なのでちょっとややこしいです。

Codeforces Round #579 (Div. 3) F1. Complete the Projects (easy version) - ARMERIA

リンク先の記事における $(a_{i}, b_{i})$ を本解説の $(-m_{i}, s_{i})$ に置き換えてください。

証明2

対称性を利用します。

先ほどとは逆に、文字列末尾から見て ) を $+1$ 、( を $-1$ としたときの累積和を考えます。その最小値と全体の和を $m^{\prime}_{i}, s^{\prime}_{i}$ と書くことにします。

ここで $s^{\prime}_{i} = -s_{i}$ なので、 $s_{i} \lt 0$ であるパーツについては $s^{\prime}_{i} \gt 0$ です。そのため先ほど $s_{i} \ge 0$ であるパーツについて書いたことと同じように、これらのパーツは末尾から見て $m^{\prime}_{i}$ が大きいものから順番に使うとして良いです。

また図を見ると分かるように、末尾から見た累積和は先頭から見た累積和と比べて $s_{i}$ のぶんだけずれています。そのため $m^{\prime}_{i} = m_{i} - s_{i}$ が成り立ちます。よって末尾から見て $m_{i} - s_{i}$ が大きいものから、つまり先頭から見て $s_{i} - m_{i}$ が大きいものから順番に使うとして良いです。

f:id:betrue12:20200511083928p:plain

まとめ

パーツとなる各文字列 $S_{i}$ について、括弧を $\pm 1$ に置き換えた時の先頭からの累積和を求め、 $m_{i}, s_{i}$ を計算します。

それらを以下の順序で連結し、累積和が途中で負にならないかどうか、合計が $0$ になるかどうかを確認します。

まず $s_{i} \ge 0$ であるパーツを、 $m_{i}$ が大きいものから順番に使う。
それから $s_{i} \lt 0$ であるパーツを、 $s_{i} - m_{i}$ が大きいものから順番に使う。

ACコード

Submission #13086967 - AtCoder Beginner Contest 167

2020-05-09

yukicoder No.1051 PQ Permutation

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

No.1051 PQ Permutation - yukicoder

※当初の公開時点での解説およびリンク先コードが誤っていたため、修正しました。

解法

※以下の解説中で「辞書順で1つ進める」と書いた時には、「もし進められない（既に辞書順最大である）ときには -1 を出力して終了する」という意味を含むものとします。実装上はC++であれば next_permutation を用いると楽です。

答え $B$ は与えられた $A$ より辞書順で大きくないといけないので、まず与えられた $A$ を辞書順で1つ進めます。この状態で $P, Q$ の位置をチェックして、 $P$ が $Q$ より左にあればこれが答えです。

$Q$ のほうが左にある場合、先頭から $Q$ までの並びがこのままである限りは条件を絶対に満たせません。よって先頭から $Q$ までの並びが崩れるまで順列を進めます。具体的には $Q$ より後ろ（ $Q$ を含まない）を逆順ソートして、さらに辞書順で1つ進めます。

この操作後に順列がどうなるかを場合分けします。（-1 で終了するパターンは書いていません）

f:id:betrue12:20200509005123p:plain

細かく分けるとこんな感じですが、パターン1とパターン3、パターン2とパターン4はほぼ同じです。 $Q$ より後ろを逆順ソートしてさらに1つ進めると、 $Q$ もしくはそれより前の位置のどこかが「繰り上がり」、それ以降は余った値が昇順ソートされた順列になります。

これらのパターンにおける $P, Q$ の位置関係を見ると、

パターン1, 3のように「繰り上がり」に $P$ が使われた場合、必ず $P$ が $Q$ よりも左に来るので、これが答えとなる。
パターン2, 4のように「繰り上がり」に $P$ も $Q$ も使われなかった場合、 $P, Q$ は昇順ソートされた領域に属するため、その位置関係は大小に依存する。 $P \lt Q$ であればそれが答えであり、 $Q \lt P$ であれば $Q$ を $P$ のすぐ右隣に移動させるのが最適である。
パターン5のように「繰り上がり」に $Q$ が使われた場合、必ず $Q$ が $P$ よりも左に来る。

となります。パターン5以外の場合はこれで答えが求められます。

パターン5だけは決着が付かないので、「再度 $Q$ より後ろを逆順ソートする→さらに辞書順で1つ進める→繰り上がりパターンチェック→パターン5なら再度…」という流れを繰り返すことになります。これは最悪ケースで約 $N$ 回繰り返すことになるので、毎回ソートと next_permutation を実行していると間に合いません。しかし次のようにやると間に合わせることができます。

そもそも「さらに辞書順で1つ進める」処理の時に繰り上がる位置はどこなのか考えます。それは $Q$ が存在する位置から左に見ていって、初めて $A_{p} \lt A_{p+1}$ となるような位置 $p$ です。そして $A_{p+1}, ..., A_{N}$ の中で $A_{p}$ より大きいもののうち最小の値が位置 $p$ に来ることによって繰り上がります。

もし位置 $p$ に来る値が $Q$ 以外であれば、先述のパターン5から逃れられます。そして $Q$ が来てしまう場合は、「辞書順で1つ進めて、再び $Q$ より後ろを逆順ソート」という一連の処理の代わりに、 $A_{p}$ と $Q$ をスワップしてしまうことができます。

その理由は以下の通りです。繰り上がり処理を行う前の状態では $A_{p+1}, ..., A_{N}$ が降順ソートされていました。そして「 $A_{p+1}, ..., A_{N}$ の中で $A_{p}$ より大きいもののうち最小の値」が $Q$ だったので、値 $Q$ があった位置に値 $A_{p}$ が代わりに入っても位置 $p+1$ 以降における相対的な順序は変わりません。そのため「 $Q$ より後ろが降順ソートされている」という条件が保たれます。

f:id:betrue12:20200509025201p:plain

繰り上がりの位置 $p$ をずらしていくのは全体で $O(N)$ 、繰り上がりで位置 $p$ に来る値の判定は set 等を用いて1回あたり $O(\log N)$ 、値のスワップは1回あたり $O(1)$ です。よってこの処理を約 $N$ 回繰り返しても大丈夫です。 $Q$ が繰り上がりに使われるパターン5を抜け出して答えに辿り着くか、または $A_{p} \lt A_{p+1}$ となるような $p$ が存在しなくなってしまい -1 で終了するまで繰り返せば良いです。

ACコード

#479427 (C++17(1z)) No.1051 PQ Permutation - yukicoder

2020-05-08

Educational Codeforces Round 35 G. Mass Change Queries

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

お題箱より。

Problem - G - Codeforces

Editorialのコメント欄に色々別解が書かれているのですが、この記事はEditorial本文の解法を扱います。

問題概要

長さ $n$ の整数列 $a_{1}, ..., a_{n}$ が与えられる。この数列に対する操作が $q$ 個与えられ、これを順番に施す。

操作 $(l, r, x, y)$ ： $l \le i \le r$ である $i$ それぞれについて、もし $a_{i} = x$ であれば $a_{i} = y$ に置き換える。

操作完了後の数列を求めよ。

制約

$1 \le n \le 200000$
$1 \le a_{i} \le 100$
$1 \le q \le 200000$
各操作について、 $1 \le l \le r \le n$ かつ $1 \le x, y \le 100$

解法

「写像」として捉える

値の置き換えを「写像」として捉えます。この写像は「操作前に $x$ だった値は操作後に何になるか」というものを $x = 1, ..., 100$ について求めたものであり、長さ $100$ の配列として表現できます。

何も操作しないことを示す恒等写像は配列 $v = \lbrace 1, ..., 100\rbrace$ で表現し、「 $x$ を $y$ に置き換える」という操作の写像は恒等写像から $v\lbrack x \rbrack = y$ だけを変更したものになります。

そして操作を複数行うことは写像の合成に相当します。 $v_{1}$ で表現できる写像と $v_{2}$ で表現できる写像をこの順に適用するという合成写像は、値 $x$ が $x \to v_{1}\lbrack x \rbrack \to v_{2}\lbrack v_{1}\lbrack x \rbrack \rbrack$ と変化していくので、 $v_{2}\lbrack v_{1}\lbrack x \rbrack \rbrack$ の値を $x=1, ..., 100$ について並べた配列で表現できます。これを $v_{2}\circ v_{1}$ と表記することにします。

この写像の合成は結合法則を満たします。写像 $v_{1}, v_{2}, v_{3}$ について、 $(v_{3}\circ v_{2}) \circ v_{1}$ と $v_{3}\circ (v_{2} \circ v_{1})$ は等しくなります。これらはどちらも値 $x$ を $v_{3}\lbrack v_{2}\lbrack v_{1}\lbrack x \rbrack \rbrack \rbrack$ に変化させる写像であるからです。この性質は後で使います。

数列の位置を走査する

もし仮に全操作が全ての要素に適用される（つまり $l=1, r=n$ である）ならば、全ての操作を合成した写像を求めてしまえば全部の値の行き先がわかるので答えを求めることができます。

しかし実際の各操作では、それを数列 $a_{1}, ..., a_{n}$ のどの位置に適用するかという有効範囲 $\lbrack l, r \rbrack$ が指定されています。そのため位置によってそこに適用される写像が異なります。

なので位置を $i = 1, ..., n$ と順番に見ていきながら、「今見ている位置に適用されている操作を全て合成した写像は何か？」を求めていくことを考えます。これを実現するためには、各操作の有効範囲を出入りするタイミングでその操作の影響を足したり消したりする仕組みが必要です。そのためにセグメント木を利用します。

このセグメント木は長さが $q$ で、実装上は各ノードは長さ $100$ の配列を持ちます。 $k$ 番目の葉のノードは $k$ 個目の操作の写像に相当します。そして上位ノードではその下のノード2つの写像を合成した写像を保持することにします。

この写像の合成をセグメント木で処理できる理由として、先ほど確認した結合法則が効いてきます。単位元は恒等写像です。

こうすると「操作の影響を足したり消したりする」処理を実現できます。最初は全ての葉ノードを恒等写像にしておき、操作の有効範囲に入ったらその操作に相当する葉ノードの写像を変更し、有効範囲から出たらまた恒等写像に戻せば良いです。通常のセグメント木のように葉ノードを変更するたびにその上位ノードを更新していけば、最上位ノードでは今有効な操作を全て合成した写像が得られます。これで答えを求めることができます。

ただしこの解法では計算量がかなりタイトです。 $A = 100$ として1回写像を合成するたびに $O(A)$ かかるので、全体計算量が $O(Aq\log q + n)$ となります。

ACコード

Submission #79365446 - Codeforces

セグメント木の各ノードの型を vector<int> にするとギリギリだったんですが、array<int, 100> にしてみたら結構速くなりました。

2020-05-02

AtCoder Beginner Contest 165 C - Many Requirements

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

AtCoder Beginner Contest 165 - AtCoder

解法

得点の計算方法が面倒で、賢い解き方はなかなか思い浮かびません。制約が小さいことに注目して全探索の方針を考えます。

制約上の最大値である $N=M=10$ で考えます。数列 $A$ としてあり得るものは、単純に見積もると $1$ 以上 $M$ 以下の整数が $N$ 個なので $M^{N} = 10^{10}$ 通り、これを全探索するのは厳しいです。ですが広義単調増加、つまり $A_{1} \le A_{2} \le \cdots \le A_{N}$ という条件によってこれがなんと $92378$ 通り であると計算できます。これなら全探索ができます。

その計算方法として、まず1つは後で「実装」のところで書くようなコードを実際に書いてしまってその個数を出力してみる、という方法があります。事前に見積もれていなくても、ダメ元で最大ケースを調べてみるのは良い戦略です。試しに計算してみてめちゃくちゃ多いようだったら別の方針に行けば良いので。

もう1つは数え上げの考え方を使います。以下の図にまとめました。

f:id:betrue12:20200502231759p:plain

このような考え方で、あり得る数列の個数は $_{N+M-1}C_{N}$ であることが分かります。手計算はつらいので Wolfram|Alpha に投げましょう。 $_{19}C_{10} = 92378$ であると計算してくれます。

実装

実際に $_{N+M-1}C_{N}$ 通りの数列を列挙する方法ですが、再帰で作ったり長さの小さいものから順番に作ったり、色々実装方針があります。私の実装を以下に貼ります。これは長さの小さいものから順番に作っていく方法です。

C++

// V[k] : 長さkである単調増加数列たち
vector<vector<int>> V[11];

// 初期値として長さ1のものを入れる
for(int i=1; i<=M; i++) V[1].push_back({i});

// V[k] から V[k+1] を作る
for(int i=1; i<N; i++) for(auto& v : V[i]){
    // 単調増加なので、末尾の値以上であるものを全て試す
    int b = v.back();
    for(int a=b; a<=M; a++){
        auto v2 = v;
        v2.push_back(a);
        V[i+1].push_back(v2);
    }
}
// V[N] に求めたいものが入っている

Python

# V[k] : 長さkである単調増加数列たち
V = [[] for _ in range(N+1)]

# 初期値として長さ1のものを入れる
for i in range(1, M+1):
    V[1].append([i])

# V[k] から V[k+1] を作る
for i in range(1, N):
    for v in V[i]:
        # 単調増加なので、末尾の値以上であるものを全て試す
        b = v[-1]
        for a in range(b, M+1):
            v2 = v + [a]
            V[i+1].append(v2)
# V[N] に求めたいものが入っている

これであり得る全ての数列を作ることができるので、それぞれに対して得点計算することで答えを求めることができます。

ACコード

（C++）Submission #12596954 - AtCoder Beginner Contest 165

（Python）Submission #12656942 - AtCoder Beginner Contest 165