CODE FESTIVAL 2016 Final E - Cookies
問題
E: Cookies - CODE FESTIVAL 2016 Final (Parallel) | AtCoder
問題概要
はじめ、1秒に1枚のクッキーを焼くことが出来る。そして、クッキーを全て食べつくすという行動を取ることが出来る。枚数に関わらず、これには秒かかる(食べている間はクッキーを焼くことは出来ない)。しかし、直前にクッキーが
枚溜まっていたら、食べた後は1秒に
枚のクッキーを焼くことができるようになる。
枚のクッキーを用意したいと思う時、それに必要な時間の最小値を求めよ。
は整数
アイデア
まず、クッキーを食べる間隔についてだが、クッキーを食べてから次にクッキーを食べるまでに最低でも2秒はクッキーを焼かないと最適にはなりえない。なぜなら、今の生産効率がだとして、1秒だけクッキーを焼いて食べてもその後の生産効率は
のままであり、食べる時間
だけ無駄になるからである。
そうすると、最短でクッキーを食べ続ける行動をとっても生産効率は2倍ずつ上がっていく。なので、生産効率がに到達するまでにクッキーを食べる回数は
回ということになり、これ以上の回数クッキーを食べることに意味はない。
クッキーを食べる回数を回に決め打ちして、そのときに
枚作るための時間の最小値を求めていく。
回食べるときに、そのクッキーを焼く間隔を
秒とすると、かかる時間は
で、焼くことのできるクッキーの枚数は
枚である。
焼けるクッキーの枚数についてなぜこうなるのかというと、順番にシミュレーションしていけばこうなることが分かる。はじめは枚/s焼けて、
秒後に食べるので
枚/s焼けるようになる。次は
枚/s焼けて、
秒後に食べるので
枚/s焼けるようになる。...
これを繰り返していくと、最終的な状態は上で述べたようになっている。
クッキーの枚数の条件を満たしつつ、かかる時間
を最小化したい。初項は一定なので、実質
を最小化したい問題になった。
この時、積をできるだけ大きくするにはそれぞれの項の差が1以下になるようにするのが最適になっている。としたときに、
であるから、これが正しいことが分かった。
の最大値を二分探索し、それを
とすると、
のような形になるので、
の項の個数を全探索して、最小値を更新していけば良い。オーバーフローには気をつける(
以上になった瞬間に打ち切ってしまえば良い)。
実装(C++)
続きを読む2016/11 solved(2)
11/16
segtreeを使って最大得点のチームを管理。
愚直にシミュレーション。香りが届くかどうかの判定は、距離チェックと角度チェックをそれぞれすればよい。
シミュレーションすればいいのだが、残っているプレイヤーの管理に注意しないとTLEする。リスト構造を使うことで、プレイヤーの順番回しをで出来る。
問題文の図もヒントになるが、有向グラフの閉路検出をすればいい。
(何日目,疲労度,複数回ライブ行った日の数)を保存しながらDP(遷移が難しかったのでメモ化再帰でかいた)。
人の位置、幽霊の位置、幽霊の行動パターンを保存してBFS。
リーダーのindexをsetで管理する。すると各クエリに対して、ADD,REMOVEはで出来る。残りの
CHECKは、リーダーの人数をとするとそのリーダーのグループに入ることが出来る人のindexが二分探索で探すことができ、
人以下にできるかどうかを二分探索していくことが出来る。スコアの幅を
とすると、
で実現できる。
DFSで書こうとすると、木にダメージは入らないが経験値だけ得られるような道具があるときに無限ループが発生してしまうので、(残り耐久、経験値)の組でBFSして求めた。
最初は両方集合の状態を保存してDPしようとしていたが、片方は順番を無視することが出来て、片方は順番に前から、もう片方を使った集合を保存してDPを進めていける。
11/17
サイコロの向きを正規化して種類を数える。上面の色を固定し、側面の色は長さ4の配列として見たときに辞書順最小になるように回転しておくと、底の色との組で何通りあるかが楽に求まる。
各頂点の状態を(まだ使ってない、使ってる最中、使い終わった)に拡張してBFS。
二部マッチングを作り、最大安定集合を求める。
2次元のBIT上でimos法をやる。
dp[mask][now] = すでに訪れた頂点mask,現在位置nowのときの最小コスト を保存しておいてBFSする。既に訪れた頂点集合を保存しておけば、その道を通るときにコストPで通れるかRで通れるかが決まる(すでにcに訪れていれば、そこで払っておいたことにすればいい)。
11/18
11/19
とりあえず最大値が二分探索できるのはすぐ気づいた。でもそっからどうやって和を最大化しようかなあと思ったけど、最終的にはyukiさんの方の和を最大化するという方針で解説と同じ感じのDPをした(submission)。
成績の得点がたかだか15600点なので、スコアをkeyにしてそれぞれ何人いるかを保存しながら和のSegtreeで順位管理ができそうだなーとおもってやってみたけど、同じ得点の扱いをどうするか悩んで、setを15600個作ってlastACを管理しつつ、今のクエリの人が何番目にACしたか分かればさっきのSegTreeと合わせて順位出せるね、ってなったけど普通のsetに何番目かを効率よく探せる方法がなく、どうしようと悩んで調べてみたらどうやらtreeというg++拡張があるらしい(参考)と知ったので、見よう見まねで使って見たらできた(submission)。ただ、解説にある通り、大小関係は(score,lastAC)のペアによって定まり、クエリが個しかないので、このペアの種類も
個しかないから先に全部読みながらあり得るペアを列挙してindexingしておいてから和のSegTreeなりBITなり使えばいいじゃん...ってなって賢さを感じた。
11/20
11/21
[はじめ、凸包を取って頂点数を個にしぼる。
でいけると思ってたけどTLEしてしまったので、Caliperを
回して最大の面積を求めるので
にできた。
-SRM 302 Div1 Hard - JoinedString
蟻本の練習問題として載っているこの問題を考えていたら類題として見つけた。POJのメモリ制約が厳しすぎて自分のイメージしていた解法がMLEしたりしたけどDiv1 Hardに同じ問題があってしかもこの難易度だったらもうこっちはとりあえず良いか...ってなった。経路復元をもっと効率良く出来るみたいなんだが、理解できず...
11/22
半分全列挙。
似たような問題をこどふぉでやったことあったような気がした。iとi+1の遷移を考えるときに(iのマスの個数)*(i+1のマスの個数)の値で場合分けをする。これがw*h以下なら全パターンの移動を試せば良い。ただ、それ以上になると多すぎて遷移を書ききれないのでBFSにする。
シミュレーションするだけだけど、同期ズレがないように気をつける必要がある。
アルファベットを頂点として、しりとりに使われる各単語を辺として頂点間に張り、全ての辺1度だけを通るような閉路を考える(=オイラー閉路と言われている)。この確認方法はまず全ての頂点が連結であることを確認できれば、全ての頂点で入次数と出次数が一致していれば良い。
11/23
ケーキ屋に訪れたbit、0からの最短距離で拡張した頂点でBFSすると思ってたけど無限にWAを出して悩んでたけど、stringを頂点番号に変換するところをバグらせているだけだった...
11/24
m以上の値が奇数個あるか偶数個あるかを二分探索する。
各行、または各列は単調なので、どちらかを固定すると各行列に対してm以下の値が何個あるかを二分探索できる。さらにこのmも二分探索が出来る。
11/25
クエリを先読みして逆に見ながら復元する。
11/26
文字の個数を数えて、奇数長になるときと偶数長になるときで回文になる条件が違うのに気をつけて組み合わせを数える。
ソートして1番目と2番目が一致するかチェック。
11/27
11/28
決勝本番中の後半にずっと考えてた問題。全体が強連結成分になっていけなきゃいけないので、最後に訪れた頂点から出る辺がある&&1に入ってくる辺があればいいかなあとかおもってたDPを書いていたけど、これじゃあうまくいかないパターンあることに終了10分前くらいに気づいて死んだ。
全ての町を3グループに分ける: (1.町1と強連結成分をなす 2.訪問済みだが町1と強連結成分をなしてはいない 3.未訪問の町)。このように分けると、dp[i][j][k] = i日目,訪れた頂点数j,町1と強連結成分をなす町の個数k の組み合わせの個数というものを考えると、ここからの遷移は先程のグループ1,2,3,のいずれかの遷移になるので全体ででこのDPが計算でき、答えは
dp[m][n][n]になり、十分間に合う(submission)。
