2019-01-14

青色になるまでの軌跡

色が変わったら記事を書く人がそこそこいる競プロ界隈ですが，自分もその流れに便乗してみようと思います。ついでに，茶色からの話も少しだけしてみようかと思います。(本編は水色～青の話です。)
最初にこの記事の結論を言ってしまうと，「ちょっとレベルが高めの問題を解こう！」ということに尽きます。レベルを上げるためには自分のレベルより少し上に触れる必要があると思います。

茶色まで

200点までがサクッと解けて，300点もたまに解ければなれるラインだと思っています。こんな言い方ですが，決して簡単なラインではないと思います。200点までをしっかり埋めていきましょう。

緑まで

緑になるためには，計算量という概念についての理解と，それを改善するための具体的な手段をいくつか身につける，思いつけるようになる必要があります(300点で求められるラインです)。愚直にやるとTLEしてしまう解法をうまくやって計算量改善する，という営みの基本的な能力が求められます。300点を解きながらそういうところを意識して学んでいくとよいと思います。
あとは簡単な数学の知識が必要になります。特に整数分野が頻出な印象があります。ここは数学の勉強が必要になると思います。

水色まで

水色に求められるのは以下のようなレベルだと考えています。

300までが早い
400~500がたまに解ける

特に300までに早さに安定感があると，緑帯ならほとんどレートは下がりませんし，AGCなら1完で青パフォが出たりするのでお得です。僕は基本的に遅いのでどうすればいいかわかりません。
400~500あたりですが，知識としては蟻本2章+4章のゲーム・数え上げの節程度で十分だと思います。あとはもう問題を解きながら，経験を積んでいくのがよいと思います(投げやり)。
僕は緑で苦戦していた時期が長く，「競プロは地頭ゲーでは...」という気持ちになり正直苦しかったです。なんとか続けてここまで来れているのはよかったなあと思っています。今でも頭は大切だと思っていますが，勉強量でなんとかなる部分もあると思います。

余談ですが，水色になるまでに必要な知識やテクニックをまとめたpdfでも作ろうかな...とちょっと考えています。蟻本では触れられていない部分や，やや言語化しにくいテクニックをまとめたものってないなあという気持ちがあります。

青になるまで

青に求められるレベル

青に求められるものは以下レベルだと考えています。

400(~500)までが早い
500~600はそこそこ解ける
700~900がたまに解ける

頻度の書き方が雑ですが，気持ちとしてはそれくらいです。ちなみに僕は(グラフの通り)安定感は皆無ですが，AGCで800とか900をたまに通してレートが+100みたいなことをして青になったタイプの人です。もちろん，堅実に500~600あたりを通してレートを上げた回もあります。

パフォーマンスの推移

f:id:sigma1113:20190114130635j:plain

時折爆死していますが()，基本的には順調に伸びているように思ってます。どんどん伸ばすのが難しくなると思っているので，このぺースが維持できるかはわからないですね....。
さて，このグラフを見るとわかる通り，2018年の9月から突然黄色パフォや青パフォがよく出るようになりました。ここら辺であったことを簡単に述べたいと思います。

冒頭に述べた通り，2018年の8~9月頃から，自分のレベルより少し難しい問題を解き始めました。これは400~500が埋まってきたということもあるのですが，結局700あたりが解けるようになるためには，700あたりを知らないとどうしようもないわけです。敵を倒すには敵を知らなければいけません。
さて，当然自分のレベルより高い問題なのでだいたい自力で解けないのですが，積極的に解説ACをしていきました。この「過去問埋めのときに解けなかった問題の解説を見るべきか？」という問題はよく(?)話題になりますが，僕は積極的に見ることを推奨する派閥(?)です。コンテスト中に問題が解けるかどうかが全てだと考えているので，過去問埋めでは基本的に知識や経験を蓄えるべきと考えています。もちろん，解説を見ずに詰めるということも大切な経験ですが，コンテスト時間は高々2時間ですから，僕は2時間くらいで諦めることが多いです。
また，これはこれくらいの得点帯の問題あるあるですが，解説を見たらすぐACできるとかそんな甘いものではありません。解説は往々にして実装レベルに落とすまでの細かい部分が省略されています。また，当然いくつかの知識が仮定されてることが多いです。このような理由で，解説を見て理解して実装するということも十分負荷のある経験であり，実力を伸ばすことに大きく寄与すると考えています。
このような取り組みを始めるまでは，400~500も怪しかったですが，最近は400はほとんど落としませんし，700以上もたまに通せるようになってきました。点数の高い問題は踏むべき考察ステップが多く，1問埋めるだけで多くのことを得ることができます。その結果としてそれより低い問題の正答率にも貢献しているのだと思います。

精進の方法について1つの考え方を述べてみましたが，人それぞれではあるものの，結局自分が難しいと思うレベルの問題もこれから解けるようにならないといけないので，いくつか見ておくということは有用だと考えています。

今年中に「黄色になるまでの軌跡」というタイトルで記事が書けることを祈って本記事を締めくくりたいと思います。引き続き頑張りましょう。

2018-12-29

AGC-030:Tree Burning

解けてよかった。

問題:

B - Tree Burning

考察

まず，高橋君はどういう動きをすべきかを考えよう。直感的に， $0(L)$ を中心として，左右に振れるような動きをしたくなる。つまり

最初は $i$ 本分右に進んで，それ以降は左→右→...と進む。(1)
最初は $i$ 本分左に進んで，それ以降は右→左→...と進む。(2)

これを $i=1...N$ で試したとき，その最大値が答えになる(この部分が非自明ですね，わかり次第(そして余裕ができ次第)追記します)。部分点解法は， $i$ を固定したあと，この動きを愚直にシミュレーションすればよい。
Submission #3894463 - AtCoder Grand Contest 030

では，満点解法を考えよう。要は，部分点解法ではシミュレーションに $O(N)$ かけて答えを求めているが，これが $O(1)$ でできれば満点だ。これはすぐにはわからないので，実験をしてみよう。例えば $N=5$ で， $i=1$ としてみよう。このとき，高橋君の歩いた距離は(実際に手を動かしてください)
$x_1 + \{x_1 + (L-x_5)\} + \{(L-x_5) + x_2\} + \{(x_2 + (L-x_4)\} + \{(L-x_4) + x_3\}\\\ =2x_1 + 2x_2 + x_3 - 2x_4 -2x_5 + 4L$
さて，これを見てなんだかきれいそうな形をしているなあと思えないだろうか。実は，一般的には以下のような結果になる。対称性のため，(1)のパターンだけ述べることにする。

$(i+N)$ が偶数のとき

$m = (i+N)/2$ とする。数列 $\{S_i\}$ を $\{X_i\}$ の第 $i$ 項までの累積和とする。このとき，高橋君の歩いた距離は
$2(S_m-S_{i-1})-X_m - 2(S_N-S_m) + (N-i)L$
である。

$(i+N)$ が奇数のとき

$m = (i+N+1)/2$ とする。このとき，高橋君の歩いた距離は
$2(S_{m-1}-S_{i-1})- 2(S_N-S_{m-1}) + X_m + (N-i)L$
である。

本当にこうなるかどうかに関しては，実際に確認してみることを勧める(万が一違ったら，提出を参考にしてください)。(2)のパターンも同様の式で書ける(提出を参考にしてください)。
これは累積和を事前に計算すれば $O(1)$ でできるので，全体で $O(N)$ で解ける。

提出

Submission #3895747 - AtCoder Grand Contest 030

Garbage Collectorの公式の解説放送では，りんごさんが実際に具体例で計算することでキーとなる式を導いていた。これと同じことを試したら解けたので，具体例での計算は大切だと実感。
青にあと7届かず。

2018-12-08

ABC115-D:Christmas

Pythonで解いた記念。

問題

レベル $L$ バーガーを以下のように定義する。

$L=0$ のとき，パティ1枚。
$L\geq 1$ のとき，パン1枚，レベル $L-1$ バーガー，パティ1枚，レベル $L-1$ バーガー，パン1枚　を下から重ねたもの。

レベル $N$ バーガーの下から $X$ 枚目までに，パティは何枚あるか。
$1\leqq N \leqq 50$

考察

レベル $L$ バーガーが再帰的に定義されていることを使いたい。絵を描いてみるとこんな感じ。
f:id:sigma1113:20181208224144p:plain
これの $X$ 番目が例えばここだとする。
f:id:sigma1113:20181208224158p:plain
これを見れば，「レベル $L$ バーガーの $X$ 番目までのパティの数」は「レベル $L-1$ バーガーの $X-1(=X')$ 番目までのパティの数」だとわかるだろう。同様に，レベル $L-1$ バーガーはこんな感じで， $X'$ 番目がここだとする。
f:id:sigma1113:20181208225003p:plain
これを見れば「レベル $L-1$ バーガーの $X'$ 番目までのパティの数」は
「レベル $L-2$ バーガーの $(X'-2-(レベルL-2バーガーの長さ))$ 番目までにパティの数 $+$ レベル $L-2$ バーガーのパティの数 $+1$ 」
とわかる。こう考えると，再帰的に問題を解いていけばよさそうという気持ちになれる。
　では，具体的に再帰関数を書いていくことを考えよう。まず，レベル $i$ のバーガーの長さを $l_i$ ，レベル $i$ のバーガーにあるパティの数を $p_i$ とすると，これらは次の漸化式を満たす。

$l_i = 2l_{i-1}+3,l_0=1$
$p_i = 2p_{i-1}+1,p_0=1$

これはバーガーの定義からわかるだろう。事前にこれらの値は求めておく。
そして， $dfs(level,dist)$ を次のように定義する。

$level=0$ のとき， $1$
$level\neq0,dist=1$ のとき， $0$
$level\neq0,dist=l_{level}$ のとき， $p_{level}$
$level\neq0,dist=2+l_{level-1}$ のとき， $p_{level-1}+1$ (ちょうど真ん中)
$level\neq0,dist \leqq 1+l_{level-1}$ のとき， $dfs(level-1,dist-1)$
$level\neq0,dist \geqq 3+l_{level-1}$ のとき， $p_{level-1}+dfs(level-1,dist-2-l_{level-1})$

これを実装すればOK。計算量は $O(N)$ である。

提出

Submission #3744671 - AtCoder Beginner Contest 115

Pythonで書いた。
for文でも同様のことができるらしい(たしかに)。

2018-12-02

HTTF2019本選:モンスターテイマー

オープン $4$ 位だったので記念に投稿。本選の人と合わせると $14$ 位かな？
( $12/03$ : $4$ 億点が出たので追記しました)

問題

A - モンスターテイマー

　モンスターの高橋君(?)を育てながら，野良モンスターを討伐し，所持金を増やすという問題。

f:id:sigma1113:20181201233818p:plain:w300 — 初期状態の高橋君

正の得点を得る

　この問題では，正の得点を得るのは容易だ。高橋君も討伐依頼も無視し，ひたすらアルバイトする。
Submission #3692024 - HACK TO THE FUTURE 2019 本選オープン

レベル上げは重い...?

　問題文をぱっと見ると，レベル上げのコストがかなり重そうに見えた。そこでとりあえず，討伐依頼のうち，必要なスキルレベルの最大値が $1$ であるもののみを相手にすることにしてみる。最初はすべてのスキルのレベルを $1$ にすることを目指し，その後はひたすら討伐する。テストケースの作り方より，相手にする討伐依頼は $30000\times 0.1=3000$ 個くらいだろう。
　提出してみると $14509$ 点で思ったより良かった。
Submission #3692352 - HACK TO THE FUTURE 2019 本選オープン

それでもレベルは上げたほうがいい

　この時点ですでに $2$ 億点に乗せている人がいたため，何かを勘違いしているのだろうと察する。どうやら，レベルは上げてしまった方がいいらしい。簡単に見積もってみる。すべてのスキルのレベルを $10$ にするのに必要な金額は
$10\sum_{k=1}^{10}k\cdot 2^k = 1.8434\times 10^9$
やはり重いように見えるが，ここですべてのスキルを上げたときに，討伐によってどれくらいの報酬が見込めるかを考えてみる。それは，テストケースの作り方から見積もれる。まず， $1000$ ターンにたいして依頼は $30000$ 個あるから，各ターンに $30$ 個はそのターンが締め切り日であるような依頼があると考えてよい。また， $30$ 個もあれば， $1$ つくらいは必要スキルの総和が $50$ くらいのものがあることを期待することにする(そんなに変な期待ではないはず...)(レベルmaxなので，各ターンで報酬が最大のものを取るのが基本になることに注意，もちろん実際に見るのは $C_i$ の値だが)。さらに，スキルボーナスも必ず獲得できる。そうすると，討伐によって見込める利益は
$(1.3^{50}\times 1000) \times 10 \times 10 \approx 4.9\times 10^{10}$
であり，たった1回の討伐で元が取れそうとわかる。(ちなみに実際に平均を取ってみると $3.0\times 10^9$ くらいでした，すいません。一応元は取れていますが。)
要は，

前半はできるだけ早くすべてのスキルをmaxにする
後半は討伐内容をうまく選んで，報酬を最大化する

という問題にしてしまった方が，後半でがっぽり稼げるので最終的にもスコアが高くなるのである(基本はそうというだけで、実際は後述するようにレベルを上げながら何をするかということも重要になってくる)。すぐには確信できない部分はあったが，時間はあるので物は試しという気持ちでとりあえず実装する。もう少し詳しく書くと

討伐依頼のリストは締め切り時刻ごとに管理する。
トレーニングするお金がないとき:その時点で報酬が最も高い討伐をするか，アルバイト
トレーニングするお金があるとき:トレーニングする。すべてのスキルをレベル $1$ に→すべてのスキルをレベル $2$ に→...→すべてのスキルをレベル $10$ にとなるようにトレーニングする。スキル $1$ から順番にレベルを上げる。
すべてのスキルレベルが $10$ になったら，そこからは各ターンで最も高い報酬の得られる討伐を行う。

これを実装して提出するとなんと $2.9$ 億点！ナイーブな発想だが，これがちゃんとできるかが一つの山だったようである。
Submission #3693049 - HACK TO THE FUTURE 2019 本選オープン

f:id:sigma1113:20181202160326p:plain:w300 — レベル $10$ の高橋君

地道な工夫

　ここからはろくなことができなかったので，実際にやった地道な工夫を紹介。

レベル上げの途中にも，おいしい討伐依頼が転がっている可能性がある。そのため，報酬がある閾値 $s$ を超えるような討伐依頼は受けるということをする。計算時間が余っていたので，この $s$ は適当そうな範囲を探索した。
レベル上げが終わってからは，受ける討伐依頼を前から決めるより，後ろから決めた方がスコアがよかったのでそうした。この貪欲も厳密ではない(短期間の依頼は報酬の落ち方が激しいため，その分損をする可能性がある)。
全く本質的ではないが，スキル上げの順番を $2$ 通り(だけ)試していい方を選んだら少し上がった。

というわけで，最終結果となった提出がこれだった。
Submission #3694390 - HACK TO THE FUTURE 2019 本選オープン

反省と感想

レベル上げの順番を焼きなましやら山登りやらするといいらしい。試してみていい結果がでたら加筆します。
レベル上げの途中にどの討伐依頼を受けるかというところでも工夫の余地がある。
後ろから貪欲に加えて $1$ つ前のターンとの差分を考えるとうまくいくらしい。
楽しかった。来年は新卒枠なので賞金を狙えるくらいになりたい...。

追記( $12/03$ ):山を登る

　山登り法を試したところ効果があったので，その詳細を述べる。
レベル上げの順番を最適化することを考える。レベル上げの順番は， $1$ から $10$ のスキルの番号を $10$ 個ずつ持つ大きさ $100$ の配列 $p$ で管理する。例えば，配列の $\{\dots,1,3,10,1,\dots\}$ という部分は，「スキル $1$ のレベルを $1$ 上げる→スキル $3$ のレベルを $1$ 上げる→スキル $10$ のレベルを $1$ 上げる→スキル $1$ のレベルを $1$ 上げる」ということを意味する。 $p$ の初期値をてきとーに設定し，そこから $2$ つの要素をswapした配列に対し $1000$ ターン分のスコアを計算し，良くなれば採用，ということを制限時間いっぱいまで繰り返す。
　山登り法では，できるだけシミュレーション回数を増やしたいため，サボれるところはサボることを考える。レベル上げ終了後は，レベルをどういう順番で上げたかということに依存せずに行動を決定できる。今回は，レベル上げ終了後は「ターンの遅い順に討伐する依頼を決定する」という方針を引継ぐことにする。山登りを始める前に， $t$ ターンからレベル上げ後の行動に移るときの報酬の総和と行動を事前に求めておけば，だいたい $350\sim 400$ ターン分くらいはサボれることになる。
　ここまでやったのが以下。 $3.3$ 億点で，やはり「レベル上げの間でも取るべき報酬は取る」ということが必要そうだ(とはいっても，レベル上げの順番を考えないよりははるかに高いスコアだ)。
Submission #3707961 - HACK TO THE FUTURE 2019 本選オープン

　では，レベル上げの間に取るべき報酬をどう決めるかということを考える。なぜわざわざレベル上げの途中に報酬を貰いに行くかというと，その報酬がレベル上げ後に取る報酬といい勝負だからであろう。よって，レベル上げ後に取る報酬を用いてこの基準を定める。具体的にどう決めるかはいろいろあるが，
$0.55\times$ 「(今からストレートでレベル上げが終わるターン $+10$ ターン)後に得る報酬」
以上の報酬であれば，取りに行くことにした。 $0.55$ や「 $10$ ターン」という謎の数字はエスパーで決めた。
　これを提出すると，運が少し良いと $4$ 億に乗る(だめでも $3.8$ 億はある)。安定してより高いスコアを出すにはさらなる工夫が必要そう...。
Submission #3708880 - HACK TO THE FUTURE 2019 本選オープン

追記(12/07):焼きなまし法を試したら4.13億に到達。パラメータ調整が難しすぎる。今は温度を減らしていない(は？)のでまだいけるかも？
Submission #3730828 - HACK TO THE FUTURE 2019 本選オープン

おまけ

ビジュアライザでは $4$ 種類の高橋君が登場するらしいのでコンプした。うち $2$ 種類は上に挙げたので省略。

分岐1

f:id:sigma1113:20181202200935p:plain:w300 — かわいい

f:id:sigma1113:20181202201203p:plain:w300 — かわいい

f:id:sigma1113:20181202201300p:plain:w300 — 空気変わったよ...

f:id:sigma1113:20181202201334p:plain:w300 — 子供の恐竜感

f:id:sigma1113:20181202201410p:plain:w300 — BLUE DRAGONと聞いて何を連想する...?

f:id:sigma1113:20181202201607p:plain:w300 — ドラゴンボールのあれみたい

分岐2

f:id:sigma1113:20181202201511p:plain:w300 — 森にいそう

f:id:sigma1113:20181202201626p:plain:w300 — 飼いたい

f:id:sigma1113:20181202201650p:plain:w300 — 倒すと宝石が貰えそう

f:id:sigma1113:20181202201720p:plain:w300 — ゲームの中盤くらいからモブで出てきそう

f:id:sigma1113:20181202201837p:plain:w300 — こっちは緑系ですね

f:id:sigma1113:20181202202022p:plain:w300 — GREEN DRAGONでした

2018-11-24

第5回ドワンゴからの挑戦状-C:k-DMC

終了46秒前に通ってアツかった。

問題

C - k-DMC

解法

dpがちらついたが，順番に並んでいる3つ組を数えるときは，中央を固定するのが定石なので，とりあえずそれに従って考えてみる。ここで，もし $c-a\lt k$ という条件がなければ，これは単に $S$ に現れる「DMCという部分列の数」を数えるだけである。つまり，'D','M','C'の出現数について累積和を取っておき，各'M'について「その'M'より左にある'D'の数」と「その'M'より右にある'C'の数」の積を取ればよい。
さらに，「 $c-a\geqq k$ をみたすDMCという部分列の数」がわかれば，これを「DMCという部分列の数」から引くことで答えが求まる。ここが1つのポイントだろう。

それでは，「 $c-a\geqq k$ をみたすDMCという部分列の数」を求めよう。'D'の位置を $a$ ，'M'の位置を $b$ ，'C'の位置を $c$ とする。DMCという部分列であって，この条件を満たすとき， $a,b,c$ の関係として考えられるものは

$b\lt a+k$ かつ $a+k \leqq c$ ('C'だけ遠い)
$a+k \leqq b \lt c$ ('M'も'C'も遠い)

の2つであり，これらは排反である。1の方は，区間 $[a+1,a+k)$ にある'M'の数と， $[a+k,N$ ]にある'C'の数が求まればよいから，'M'と'C'の累積和を使えば $O(1)$ で求まる(詳細は提出参照)。2の方は，「位置 $i$ より右にあるMCという部分列の数」を事前に求めておけば $O(1)$ で求まる(これも累積和，提出参照)。よって，各 $k$ の値に対して $O(N)$ で答えが求まるので，全体として $O(QN)$ であり，十分高速である。

提出

Submission #3660113 - Dwango Programming Contest V / 第5回ドワンゴからの挑戦状予選

コンテスト後に少し整理したものを貼った。
$a+k$ が $N$ を超える場合の処理に注意。

Bでひどいミスをしたのだがこれが解けたおかげで耐えた。
$c-a\lt k$ という条件は， $c-a\geqq k$ という形にした方が扱いやすい印象があった。C - 徒歩圏内を思い出して解いていた。
公式解説見たら尺取りだった。

2018-11-11

HTTF2019予選:ばらばらロボット

はじめてのマラソン参加記。
結果は60位と，なんとも言えない成績だが，2桁順位とれるかどうかが実力相応かなと思っていたので，善戦したと思う。上位の方々も何人か記事を上げているので，これがどの程度参考になるものとなるかわからないが，記念に残しておこうと思う。

問題

A - ばらばらロボット
マラソンは問題を理解するのも一苦労だ。要求も難しく，問題文を読み切ったときはどうしたものかと思っていた。

正の点数を得る

最初にやるべきことは「正の点数を得る」(有効な提出をする)ことだと思う。これは本当に何も考えずに書いたプログラムを提出する。今回の場合は，周りは壁マス，その他は空白マスにするというものだろう。これは競プロやってますという人なら書けるレベルである。開始5分で提出した。
Submission #3572613 - HACK TO THE FUTURE 2019予選
これで80940点。これは1つの基準になる。何か工夫をしたプログラムを提出して，この点数より悪くなったら，よっぽど変なことをしている(もしくはバグ)ということである。
このときの様子をビジュアライザで見てみる。
f:id:sigma1113:20181111125650p:plain
これを見たときは意外と青が多いなと思ったのだが，緑や黄色も多いのでスコアは伸びない。
正の点数を得たので，どうやって得点を伸ばすか考える。

苦悶

ここから2時間は全くまともなことができなかった。いい感じの盤面を構成しようにも全然うまくいかない，ということを繰り返していた。
1つだけ考えたものを公開すると，周辺を2倍マス(D)で埋めるというもの。端に溜まりがちかと思ったので，端に来たら帰りやすくするようにしたかった。
f:id:sigma1113:20181111130204p:plain
Submission #3573461 - HACK TO THE FUTURE 2019予選

結果は微増。逆に端が疎になりすぎてしまった。

山登り法

2時間経ってから，マラソンの定番である山登り法を試していないことに気付く。これはあかん。
山登り法とは，端的には以下のような方法である。

適当な初期状態を定める。
現在の状態から，「少しだけ」変わった状態を作る。その状態の得点を実際に計算する。
その得点が現在の状態より良かった場合は，「少しだけ」変わった状態に遷移する。2に戻って繰り返す。

要は，今いるところより高い方に進んでいくという気持ちそのままである。この「高いところを探す→更新」という流れを制限時間いっぱいまで繰り返す。局所解に陥る可能性はあるが，それはもう仕方ない。(焼きなまし法はこの局所解に陥るという可能性を減らす方法であるが，実装できないので(おい)使わなかった。)
この問題における「少しだけ」変わった状態とは，あるマスの種類を別の種類に置き換えるというものであろう。よって，以下のようにして山登りを行った。

初期盤面を「周りは壁，その他は空白マス」と定める。
現在の盤面からあるマスを乱択で選び，別の種類のマスに置き換えてみる(これも乱択)。その後，実際にコマンドに従って $N$ 体のロボットを動かし，得点を計算する。
その得点が現在の盤面より良かった場合は，マスの変更を採用する。2に戻って繰り返す。

やっていることは難しくないが，ロボットの動きをシミュレーションするなど，それなりの実装力が要求される。コンテストの時間は8時間もあるのだから，じっくり実装できる。多少バグらせたが，1時間程度で実装できた。結果はこちら。
f:id:sigma1113:20181111131707p:plain
青マスがだいぶ増えている。スコアも劇的に伸びた。これを提出すると113776点。やる気が出てきた。
Submission #3575341 - HACK TO THE FUTURE 2019予選

シミュレーション高速化(差分更新)

愚直な山登り法がとりあえず動いたので，この方向性でスコアを伸ばすことを考える。当たり前だが，山登り法は「高いところを探す→更新」というループの回数をできるだけ多くした方がよい。制限時間があるので，シミュレーションを早くすることでこの回数を増やすことを考える。上のプログラムのループ回数をAtCoderのコードテストで見たところ，1777回であった。
上のプログラムでは，あるマスを変えたときにすべてのロボットを動かしなおしているので，計算時間が $O(NL)$ かかる。ところが，あるマスを変えたときに，動きが変わるようなロボットというのはそこまで多くないはずである。よって，各ロボットについて，現在の盤面のときにどのマスでコマンドを実行するかということを記録しておく。すると，あるマスを変えたときに影響を受けるロボットがわかるので，そのようなロボットについてのみ操作をやり直す。これも実装力が要求されるが，時間があるので頑張る。これもかなりバグったが，なんとか実装しきる。結果はこちら。
f:id:sigma1113:20181111132736p:plain
さらに良くなったことがわかる。ループ回数は8232回だった。実装がよければもっと伸びると思う。提出すると得点は120148になった。順位表を眺めていて12万点は乗せたいと思っていたのでよかった。

さらなる工夫

ここからは問題固有の考察が必要になる(と言っても，ここからはあまり伸ばせなかった)。よく考えると，壁マスを置いてしまうと，ロボットの到達できるマスが減ってしまうため，ばらばらにしたいという問題の要求に逆行している。よって，壁マスは使わないことにする。あとは，角のあたりに2倍マスや3倍マスを置いてから山登りするとなぜかスコアが伸びたので，そうしたものを提出した。一応，角に集まり過ぎないようにするという作戦は微量だが効果を発揮したらしい。
f:id:sigma1113:20181111133630p:plain
Submission #3579046 - HACK TO THE FUTURE 2019予選
122547点。これが最終得点となった。この後，「コマンド列のどの時点どのマスにいるか」を記録して操作を最初からやり直さなくていいようにしようとしたのだが，バグが取れず間に合わなかった。

終了後

終了後に得た知見を少し紹介。

LとRだけ使う

自分はDとTだけ使うということをしていたのだが，シミュレーションの高速化上都合が悪い。無駄な動きが増えてしまうからである。これは気づきたかった。

初期盤面をLで埋める

これに気付いた人はすごい。すべてのロボットを左向きに回転させてから山登りするとうまく散るということらしい。
とりあえずこの2つの工夫はすぐに試せるのでやってみた。
f:id:sigma1113:20181111134442p:plain
Submission #3581258 - HACK TO THE FUTURE 2019予選
125545点に。ここまでやれば30位台に入れたが，気づかなかったので仕方ない。

コマンド列の圧縮

例えば，LRというのは何もしないというのと同じだし，SSSというのは3マス前に進むというのと同じである。こういう圧縮をすべてのロボットのコマンド列に適用する。これだけでコマンド列はかなり短くなるはずで(悪くても1/2くらいにはなるはず)，高速化にかなり効いている。

感想

実は1週間前からマラソンの勉強を少しだけしていて，その成果が出て12万に乗せられたのはよかったと思う。その先は問題固有の考察が必要で，これはアルゴリズム同様に鍛えていかなければいけないところだと感じた。焼きなましやらビームサーチやら習得すべき技術はあるが，結局問題の性質を掴めるかの方が大切そうと感じた。
終わってみれば8時間はあっという間で，非常に充実した時間を過ごすことができた。chokudaiさんとtsukammoさんに感謝します。
本戦オープンコンテストの日はバイトを入れようと思っていたが，オープンコンテストに真面目に参加しようと思う。

追記(11/13)

20卒だったら本戦オープン行けてたらしい。残念！

2018-11-04

ABC113-D:Number of Amidakuji

フィボナッチ数列が登場しがち。

問題

D - Number of Amidakuji

解法

こういうのはdpが有効である。 $dp_{i,j}$ を位置 $i$ までで $j$ に行くようなあみだくじの数とおく。 $dp_{i,j}$ の遷移先は $dp_{i+1,j},dp_{i+1,j+1},dp_{i+1.j-1}$ のいずれかである。あとはそれぞれの遷移先について，そこに遷移するような位置 $(i+1)$ での横線の置き方の数がわかればよく，これはbit全探索することで $O(2^W)$ でできる。本番でここが思いつかなかった。悲しいね。

ところで，次のような事実がある。

縦棒が $W$ 本のあみだくじのある位置での横線の置き方の数は，フィボナッチ数列の第 $i$ 項を $F_i$ とすると， $F_W$ に等しい。フィボナッチ数列とは， $F_0=1,F_1=1,F_n=F_{n-1}+F_{n-2} (n\geqq 2)$ で定義される数列である。

証明
$W$ に関する帰納法で示す。左から順に縦棒に $1,2,\cdots W-2,W-1,W$ と番号をつけることにしよう。 $W=0,1$ のときはそれぞれ $1$ 通りである。 $W-2,W-1$ での成立を仮定して， $W$ のときの横棒の置き方の数を求めよう。縦棒 $W$ と縦棒 $W-1$ の間に横棒を置かないとき，横棒の置き方は $1$ から $W-1$ までの横棒の置き方に等しく， $F_{W-1}$ 通りある。縦棒 $W$ と縦棒 $W-1$ の間に横棒を置くとき，横棒の置き方は $1$ から $W-2$ までの横棒の置き方に等しく(縦棒 $W-1$ と縦棒 $W-2$ の間には横棒が置けないから)， $F_{W-2}$ 通りある。よって， $W$ のときの横棒の置き方の数は $F_{W-1}+F_{W-2}=F_W$ 通りである。

すると，bit全探索などする必要がないことがわかる。例えば， $dp_{i,j}$ から $dp_{i+1,j-1}$ への遷移を考えよう。このような遷移が起きる条件は

$j$ と $j-1$ の間に横棒がある
$j-1$ と $j-2$ の間に横棒がない
$j$ と $j-1$ の間に横棒がない

の3つである。これらの条件を満たすような位置 $i+1$ での横棒の置き方は，「縦棒 $1$ から縦棒 $j-2$ までの横棒の置き方」と「縦棒 $j$ から縦棒 $W$ までの横棒の置き方」の積であるから， $F_{j-2}\times F_{W-j}$ 通りある。つまり，遷移が $O(1)$ で可能であることがわかる。他の遷移も同様にしてできる(コード参照)。天才だ。

提出

Submission #3543308 - AtCoder Beginner Contest 113

フィボナッチ数列が現れるのは面白いが，bit全探索で解けなかったのは情けなかった。