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)。
