Loading [MathJax]/jax/output/CommonHTML/jax.js

目次

AtCoder Beginner Contest 204 D,E,F問題メモ

AtCoder Beginner Contest 204

████←#ABC204

D - Cooking

D - Cooking

問題

解法

全ての料理を作る時間の総計は 105 程度なので、以下のナップサックDPが作れる。

全料理の総計 Ti の半分以上で、半分になるべく近い、可能な所要時間を求めればよい。

このように、可能/不可能の0/1を保持するナップサックDPは、 Pythonなど多倍長演算が使える言語なら、整数のbitで計算すると実装も楽だし高速に動作する。

Python3

E - Rush Hour 2

E - Rush Hour 2

2が作られたのなら映画と同じく3までいきたいね。

問題

解法

辺のコストが時間で変化する最短経路探索は、FIFO制約が満たされているかを確認する。
つまり、都市 i に最短 t で到達可能としてそこから都市 j に移動するにあたり、 「都市 i に、t より後に到達した方が、都市 j に早く着ける、ということが絶対にない」状態でないと、 Dijkstraなどの効率的なアルゴリズムは使えない。

今回の場合、すぐに出発してしまうとそういうことがあり得るが、 各都市では好きなだけ待てるので、「待つ部分も含めて辺のコストとする」ことで 上手くFIFO制約を満たせるようにグラフを作り替えられる。

頂点を (,) の組でもって、各都市から「すぐ出発する」「1分待つ」の2つに遷移するようなDijkstraでも 正しい答えは求まるには求まるが、頂点数が多くなりすぎてこの方法ではTLEしてしまう。

もう少し高速に、最適な待機時間を求める必要がある。

都市 i に時刻 t に着いたとき、何分待てば良いか?を考える。(説明上、時刻1単位を[分]とする)

待機時間を a として、Dit+a>Dit+a+1 であり続ける限り、 つまり1分待つと所要時間が1分以上縮まる限り、待った方が良い。

しかし、どこかの a を境に、それから1分追加で待っても所要時間が変わらなくなりはじめるポイントがある。

そして一度そのような時間になったら、その後は1分待っても床関数   の部分はたかだか1分しか短くならず、待ち時間を含めると得することはあり得なくなる。
そうなったら即座に出発した方がよい。

その境目は、およそ Di の近傍となる。(Editorialによると、Di1 がちょうどいいらしい)

■ t と 所要時間の可変部分 は、およそ反比例の関係
D = 24
     →所要時間の可変部分 = D/(t+1)
↓t   1                      24
通 0  oooooooooooooooooooooooo
行 1  oooooooooooo
開 2  oooooooo
始 3  oooooo
時 4  oooo
間 5  oooo
   6  ooo
   7  ooo
   8  oo
   9  oo
   :

到達時刻 tDi1 より前ならそこまで待ち、後なら即座に出発すればよい。

最適な待ち時間を求めるにあたり Di 近くが良いという性質がわからなくても、 待ち時間を含めた所要時間 Dt+1 は(広義)下に凸の形状をしているので三分探索でも求めることができる。

一般に三分探索は、隣り合う評価値が同じ値になり得る場合、どちらに答えがあるか判断できないので使えない。

しかし今回の場合、最適な待機時間は床関数を外して Ci+Dit+1 で考えた場合と変わらないし、 これなら同じ値にならないので、これで評価すると求めることができる。

Python3

F - Hanjo 2

F - Hanjo 2

問題

解法

なんかPASTで出そうな実装重めな典型問題という印象。

ある列の敷き詰め方は、「1列前にどんな敷き詰め方をしたか」だけで決定できる。(2列以上前の状態は関係ない)

その情報は 2H 通りのbitフラグで持つことができ、H が小さいのでこれは高々 64 通りとなる。

i 列目の状態がたとえば 101110 のとき、次の列の敷き詰め方は、以下のようになる。

              (一例)
  i-1 i        i i+1
0  ■□        <>  1       ■: 何でも良いので畳が敷かれたマス(=1)
1  ■■        ■^  1       □: 畳が敷かれていないマス(=0)
1  ■■   →   ■v  1       <>: 全畳を横に配置
1  ■■        ■◇  1       ^: 全畳を縦に配置
0  ■□        <>  1       v
1  ■■        ■□  0       ◇: 半畳を配置

'0'が連続していたらそこに縦にも敷けるのだが、 そうすると状態を重複して数えてしまうため、あくまで'0'は「必ず全畳を横に敷く行」と決めると上手くいく。

これを、64通りの各敷き詰め方につき、どれからどれへ遷移できるか、事前に求めておく。

例えば上記の例では、'101110' の状態から '011111' の状態へは、 図で示された一例に加えて「縦に敷いた全畳 と 半畳 を入れ替えたもの」「半畳だけを3つ敷いたもの」があり得るため、Table[101110][011111]=3 となる。

答えはこの遷移を W 回繰り返したものなのだが、W は非常に大きいため、そのままやるとTLE。

遷移が毎回同じことを生かし、行列累乗で計算する。

2H×2H の行列積の計算には1回 (2H)3 かかる。
行列積は約 log2W 回求めればよいので、全体で O(8HlogW) となる。

制約の最大値を代入して、約 107 となり、間に合うことがわかる。

Tableの作り方

事前計算Tableの作り方は、まぁいろいろな構築方法があると思うが、再帰関数などでかぶり無く数え上げるのがわかりやすいかと思う。

「前の行が s で、今の行を i1 行目まで決めていて、決まっている行の状態が t のときの処理をする関数」を f(s,t,i) とすると、

みたいなことをすると求まる。

Python3

Hanjoってローマ字で書かれるとキミノミヤさんが思い浮かぶ。