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時間経ってから,マラソンの定番である山登り法を試していないことに気付く。これはあかん。
山登り法とは,端的には以下のような方法である。

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

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

  1. 初期盤面を「周りは壁,その他は空白マス」と定める。
  2. 現在の盤面からあるマスを乱択で選び,別の種類のマスに置き換えてみる(これも乱択)。その後,実際にコマンドに従ってN体のロボットを動かし,得点を計算する。
  3. その得点が現在の盤面より良かった場合は,マスの変更を採用する。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卒だったら本戦オープン行けてたらしい。残念!

ABC113-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に関する帰納法で示す。左から順に縦棒に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}への遷移を考えよう。このような遷移が起きる条件は

  1. jj-1の間に横棒がある
  2. j-1j-2の間に横棒がない
  3. jj-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全探索で解けなかったのは情けなかった。

QUPC2018-E:Treeone

最近よく見るやつ。

問題概要

長さNの数列\{A_i\}が与えられる。その数列の連続する部分列であって,総和が0であるものの個数を数列のたぴさと呼ぶ。数列のうち1つの値を自由に変えられるとき,あり得るたぴさの最小値を求めよ。
E - Treeone

解法

「数列の連続する部分列であって,総和が0であるものの個数」と聞いたら,累積和\{S_i\}を考えるのが定石である。その個数は,S_i=S_jとなる(i,j) (i\leqq j)の組の個数に等しい。つまりは,ある条件を満たす区間の数である。このうち,A_kの値を一つだけ変えて,どれだけそういう区間を減らせるかということを考えよう。答えは

  • 「元の数列のたぴさ」から「A_kを変えることで減らせる区間の数の最大値」を引いたもの

である。「元の数列のたぴさ」の効率的な計算については,A - Zero-Sum Rangesがそのものなので参照していただきたい。
A_kの値をうまく変えることによって,i\leqq k \leqq jを満たす区間(i,j)については,条件を満たさないようにできる。例えば,A_kを5000兆とかにすれば,もともと和が0だった区間の和が5000兆くらいになる。また,A_kを5000兆に変えたことによって,和が0でなかったの区間の和が0になることもない。kを含む区間については5000兆という数字がでかすぎて和が0になりようがないし,kを含まない区間A_kが5000兆になったところで何の影響もない。よって,各kについて,「i\leqq k \leqq jを満たす区間(i,j)であって,S_i=S_jなるものの個数」が効率的に求まればよい。
これにはimos法と呼ばれるものを使う(imos法を知らない方は調べてください)。各iについて,「iから始まる条件をみたす区間の数」足し算し,「iで終わる条件をみたす区間の数」を引き算する。その後,順に累積和を取っていけば,各kに対して,「kを含む条件をみたす区間の数」がわかる。また

  • iから始まる条件をみたす区間の数」は「i\leqq jであって,S_i=S_jをみたすものの個数」に等しい
  • iで終わる条件をみたす区間の数」は「j\leqq iであって,S_j=S_iをみたすものの個数」に等しい

よって,各S_iの値が全部でいくつあるかを調べておき,iが小さい順に上の計算をしてけばよい(詳細はコードを見た方がわかると思う)。実装上注意すべきは,単にS_i=0となるような場合(つまり,A_1+\cdots +A_i=0となる場合)を数えるために,S_0=0から計算を行うところである。

提出

https://beta.atcoder.jp/contests/qupc2018/submissions/3441083

  • S_iがどんな値かわからないため,mapを用いている
  • i\leqq jであって,S_i=S_jをみたすものの個数」や「j\leqq iであって,S_j=S_iをみたすものの個数」は適当に引き算すれば求まるので,直接調べる必要はない


方針はすぐだったが,変なところでバグらせて足を引っ張ってしまった。反省。

QUPC2018-D:Novelist

きれいに解けるので好き。

問題

D - Novelist

考察過程

王都から都市へ移動する依頼をタイプM,都市から王都へ移動する依頼をタイプLとする。
最初は各依頼を頂点として,ある依頼を終えた後,実行可能な依頼について有向辺を張って,最長パスを調べるということを考えていたのだが,これでは辺がO(ML)本あるためTLEする。考え直し。
よく考える。タイプMの依頼を終えた後,Treeone君はある都市nにいる。次には(可能なものが存在すれば)タイプLの依頼を選ぶことになるが,都市nから出発する依頼のうち,現在時刻より後で,最も出発日が早いものを選ぶのが最適になる。できるだけ早く王都に戻った方が,多くの依頼を達成できるかもしれないからである。つまり,あるタイプMの依頼をやると決めた後,タイプLの依頼を終えて王都に戻ってくる日が一意に定まる。
それならば,以下のようにすればよい。

  • タイプMの各依頼に対して,その依頼の開始日と,王都に帰ってくる日を両端とした区間を作る(ただし,王都に帰ってこれない場合は作らないでおく)。
  • これらの区間について,区間スケジューリング問題を解く。その解\times 2を答えに加算する。
  • 区間スケジューリング問題の最適解の終了日を記録しておく。このとき王都にいるので,タイプMの依頼のうち,まだ達成できるものがあれば答えに1を加算する。もう王都には戻ってこれないので,これでTreeone君の仕事は終わりである。

区間スケジューリング問題を知らない方は調べてください(すいません)。

提出

https://beta.atcoder.jp/contests/qupc2018/submissions/3438077

  • タイプLの依頼は,出発する都市ごとにvectorで管理した。
  • あるタイプMの依頼に対する最適なタイプLの依頼を探すのに二部探索をしている。
  • もうちょっときれいに書けそう。


今思えば,「できるだけ早く王都に戻った方が,多くの依頼を達成できるかもしれない」という考え方はまさに区間スケジューリング問題を示唆するものであった。良問だと思う。

QUPC2018-C:Ito Campus

慣れているとなんてことない問題だが,ちゃんと書いてみる。

解説

@から距離X以内のマスは安全でないなので,そのようなマスを調べて安全でないマークをつけてから,安全なマスだけでSからGへの最短距離を調べればよい。安全でないマスを調べるのも,SからGへの最短距離を調べるのも,幅優先探索(以下bfs)すればよいのだが,前者については注意が必要という問題である。
例えば,「@を見つけたら,そこからbfsで距離X以内のマスに安全でないマークをつける」ということをすると,毎回のbfsにO(X)かかり,@がいっぱいあると計算量がO(XHW)となり,TLEする。
では,「安全でないマークをつけたマスは壁'#'にしてしまう」というアイデアはどうか。これならば,同じマスを2度以上探索しないのでTLEは回避できる。しかし,これではWAを踏んでしまう。例えば,X=3として,以下のような状況を考えてみよう。外側の壁は省略してある。
f:id:sigma1113:20181020185553p:plain
ここで,(1,1)にある@から探索をすると,以下のようになる。
f:id:sigma1113:20181020185655p:plain
これで,(3,1)からあるマスを探索しようとしても,イノシシは壁を通れないので,ここで安全でないマスを調べるパートが終了する。そうすると,SからGまでは距離4で行けることになるのだが,実際はGは安全でないマスであるため,WAである。

そこで,次のようなbfsをする。最初に@であるようなマスと残りの距離(x,y,d)をqueueに入れてしまう。そこからは素直に安全でないマスを調べていくだけである。異なる点は最初だけだが,これでうまくいく。
うまくいくことを確認しよう。最初に@であるようなマスをqueueに入れておくと,以下のことが成り立つ。

  • すべての壁以外のマスに(x,y)ついて,(x,y,d)がqueueに入るとき,d(x,y)について最適な値である。つまり,d(x,y)から最も近い@から探索したときに得られる残りの距離である。

なぜなら,このbfsは「ある@からの距離が1のマスすべて」→「ある@からの距離が2のマスすべて」→...→「ある@からの距離がXのマスすべて」という順で探索が進むからである。また,どのマスも高々1回しか探索されないので,計算量もO(HW)で済む。

提出

https://beta.atcoder.jp/contests/qupc2018/submissions/3439882
実装上の変なところ(?)は以下。

  • 安全でないマスを調べる際には,queueに入れるときにマス(x,y)2000\times x+yで管理している。y\leq 1000なので,2000で割ったときの商とあまりでマス(x,y)を復元できる。こんなことをした理由は,pair< int, pair< int,int> > と書きたくなかったからなのだが,いい方法あったら教えてください。
  • とか言いつつ,2回目のbfsではマス(x,y)をそのまま管理してる。何も他に情報がいらなければこう書くのが個人的には楽なためそうしている。


こういう探索の始点が複数あるbfsは割とよく見る。

AGC028-B: Removing Blocks

数え上げ力の不足。

問題概要

1からNまでの番号がついたブロックが横にならんでおり,ブロックiには重さA_iがある。ここからN回ブロックを取り除くのだが,ブロックiを取り除くコストはブロックiと連結な(自身も含む)ブロックの重みの総和である。取り除く順番はN!通りあるが,それらのコストの総和を求めよ。

問題リンク:

B - Removing Blocks

解法

この手の問題は,「A_iが何回加算されるか?」ということを考えるのが定石である(そこまではわかる,という人が多かったと思う)。特にこの場合は,「ブロックjを取り除いたときにA_iが加算されるのは何回か?」ということを考えればよい。各jについてこれを足し合わせれば「A_iが何回加算されるか?」という問いの答えがわかる(ここまではよかった)。

では,「ブロックjを取り除いたときにA_iが加算されるのは何回か?」という問いを考えよう。簡単のため,j\leq iとする。公式解説では確率を用いているが(これはこれで賢い),実は確率を持ち出さなくても十分である。ブロックjを取り除いたときにA_iが加算されるためには,ブロックjを取り除くまでに,ブロックjからブロックiまでが取り除かれなければよい。そのような順列はいくつあるかを考える。
i-j+1=kとおこう。これらjからik個の数の並べ方のうち,jが一番最初になるのはもちろん(k-1)!通りである。これを1からNの順列に埋め込むことを考える。埋め込む位置の選び方は,N箇所からk箇所選ぶ場合の数なので,{}_N \mathrm{C} _k通りである。jからi以外の数字の並べ方は任意でよいので,(N-k)!通りある。以上より,「ブロックjを取り除いたときにA_iが加算されるのは何回か?」という問いの答えは,(k-1)! \times {}_N \mathrm{C} _k \times (N-k)! = \frac{N!}{k}とわかった。
i \lt jのときも同様に考えて同じ表式を得る。あとは,\frac{1}{k}の累積和を事前に計算すれば,「A_iが何回加算されるか?」という問いにO(1)で答えることができる。よって,全体でO(N)で計算ができる。

提出


Submission #3403177 - AtCoder Grand Contest 028


これが解けなかったのは悲しい。

AGC027-C ABland-Yard

初AGC2完記念(今更?)&初900AC記念&初黄パフォ記念。

問題概要

N頂点M辺のグラフがある(単純とも連結とも限らない)。各頂点にはAまたはBと書かれている。好きな頂点を始点とし,好きな回数隣接する頂点の移動をしたときに,訪れた頂点に書いてある文字を訪問順に並べることでAとBからなる文字列を作る。このとき,AとBからなる任意の文字列を作ることができるか判定せよ。
C - ABland Yard

考察過程

まず,問題の条件を次のように言い換えた。

与えられたグラフの連結な部分グラフHであって「Hの任意の頂点について,Aと書かれた頂点にもBと書かれた頂点にも移動できる」ようなものが存在する。

もとのグラフはGとして,Gの頂点のうちAにもBにも移動できるものを良い頂点,できないものを悪い頂点と呼ぶことにしよう。Gのうち連結な良い頂点の集合を探せばいいのだから,Gの各頂点が良いか悪いかを判定して,良い頂点の連結成分(大きさ2以上)があるかを判定すればいいと思ったのだが,サンプルさえ通らず考え直す。

よく考えると,目標は上のような部分グラフHがあるか判定することであったから,一番最初の時点で悪い頂点はHを構成する頂点になり得ない。だから,悪い頂点はないものと考えてよい。

さらによく考えると,悪い頂点をないものと考えたことによって,最初は良かったはずの頂点が悪くなっていしまう可能性があることに気付く。悪は伝搬するのである。この伝搬を素直に見ていって,すべての頂点が悪くなったらNo,良い頂点が生き残ればYesっぽいということがわかった。

そうすると,これをシミュレートする方法を考えればよい。頂点vの,隣接する頂点でAが書かれているものの数をa_v,Bが書かれているものの数をb_vとする。a_v,b_vの一方が0であればvは悪い頂点である。これはBFSでできる。
まとめると

  1. 最初に,すべての頂点vについてa_v,b_vを数えて,この時点で悪い時点をqueueに入れる。
  2. queueから頂点vを取り出し,隣接する頂点にvが悪いことを伝える。つまりvに書かれた文字がAなら,vに隣接する頂点uについて,a_uを1減らす。Bの場合も同様である。
  3. 2によって悪くなった頂点があればqueueに入れる。
  4. 2~3をqueueが空になるまで繰り返す。
  5. 悪くなった頂点の数をカウントし,N個ならNo,そうでないならYesである。

計算量はO(N+M)であり,間に合う。実はコンテスト中はTLEするかもと思っていた。

提出

コンテスト中に出したものは試行錯誤の残骸が多く汚いので,整理したものを貼る。実装は重くないと思う。
Submission #3206813 - AtCoder Grand Contest 027

雑談

  • うまく頂点を増やして辺を張って閉路検出という方法もあるらしいが,それよりは比較的自然に出てくる解法だと(個人的には)思う(自分で思いついた方を自然に思うに決まっている)。閉路検出が書けるか怪しいため,後でやってみる。
  • パフォは2143でレートが100くらい上がった。嬉しい。最近の精進の結果が少し出たかもしれない。今解説を見ても天才だな...と思うってしまう問題でも,そのうち自然だなあと思えるようになってくるのかもしれない。
  • この回のAGCはBが100人程度しか正解していないという恐ろしい回だった。Bを10分くらい考えて無理そうと思い,(その時点での正解者数を勘案して)Cに振ったのは正解だった。