2016/12 solved(2)
12/17
Wikipediaの画像ながめて、正方形の周上に移動できるのかーってなったときに、最大のdの内側に入ってるなら2回でどこでもいけるのではという事に気づいてからは場合分けで一瞬だった...
左から順に見て、右から順に見て、何人避難できるかを最大更新していく。
クラスカル法でMSTを構成していき、使った辺のうちの中央値を答えればいい。
とりあえず1日1枚以上は食べるとすると、N日以内に食べ終わる。なので、dp[i][j] = i日目までに合計j枚食べる方法の順列の個数をで計算できる。あとは、その正の枚数食べるところがi日あったら、残りのD-i日は0枚ということになり、それをどこに入れていくかは重複組合せによって計算出来る。
まず何桁の数字の位置で来るのかを計算し、その分をnから引いておく。更に、そこから桁数dが決まるとn/dだけ進めれば直前にたどり着けるので、あとはstringのくっつけてsubstrで出した。
12/18
トポロジカルソートしてから、その順番に辺を見ていって最大値更新をしていくDPを先頭からと、後ろからとやっておけばよい。トポロジカルソートはDFSによってで出来る。
まず、1からxまでのFizzBuzz stringの長さがs未満になる限界のxを二分探索によって探すことが出来る。そして、そこからstringを構成してsubstrすればいい。
二部マッチングで解いた。b[i]とr[j]の間に辺をはれるかどうかの判定は、事前に約数列挙をしておけばO(約数の個数)でできる。
dp[i] = i番目の要素が終端になるときの単調増加部分列を考えたときに、合計の荷物の重さの最大値とすると、で更新していくことが出来る。これはSegtreeを利用して、xの小さい順に更新していくようにすることで
で実現出来る。
12/19
隣接しているスライム同士に辺を張り、連結している個数を調べる。連結が1つだけならn-1が答えになり、2つ以上ある時は壁に寄せることになるので四方のどの壁に寄せるのが良いかを4通り試した。
コストが大きい方から柱を作っていく。閉路ができてしまってはいけないが、できてしまうかどうかはUnion-Findによって検知することが出来るので、結局出来上がるのは木の形になる。
暗い部屋に人がいるかの状態を表すbitDPでBFSで解いた。
12/20
8!通り試す。その際に、回転して同じ状態になりうる24通りを試して、その順列の中で一番小さいもので正規化しておいて種類をカウントすると楽。
BFSすると、根からの距離と訪れる頂点の順番が分かる。それとLCAを利用して、全体の移動にかかる距離を高速に計算出来る。
12/21
(最後に訪れた店,今までに訪れた店の集合)を状態に持ちbitDPをする。この遷移のための準備として、スタート地点と、各店をスタート地点としてダイクストラで最短距離を求めておき、各頂点間の最短距離を予め計算しておく。
取りうる値が0~255までなので、変数に関して全探索をしてその変数を含む計算結果がどのように取りうる値を変化させるかを計算することができる。除算のときに、変数が0を取りうるならerrorを返す。
12/22
答えにたどり着く方法が1通りのみと決まっているので、その都度行ける3通りを試して行き止まりになったらやめる単純な枝刈りで十分間に合う。
12/23
まずy座標の種類を列挙してソートしておき、平面走査でx座標が小さい順に見ていく。xが窓枠の左に来るとして、最大値を返すsegtreeで、i番目にy_iを枠の下側に来るようにした時の輝きの合計を保存するようにしておく。このような形にすると、区間に対するaddが必要になることが分かるので、いわゆるStarrySkyTreeを実装した。
12/24
Xmas Contest 2016 昼の部に参加
友達と一緒にゆるい感じでやった。ら、Aしかできなかった...Cずっと考えてたけど、から落ちず、辛かった。
12/25
使ってはいけない辺をsetで保存しておく。そして、まだ訪問していない頂点をsetで管理し、スタート地点からBFSしてまだ訪問してない頂点のsetに全探索して、行けるところは行ってsetから取り除くということをすると辺を張るのに失敗するのが回なので間に合うという、結構シンプルな考え方だった...グラフの直径を求めたりしようとしたけど、木じゃないとそういうのは厳しいっぽいし見当違いだった。
12/26
座標圧縮して、その区間ごとに何匹の魚がいるかを調べる。区間は個になり、区間ごとの判定は線形にできるので全体として
で間に合う。
どのカードを取り除くかを全探索してシミュレーションすれば良い。
距離ごとにシミュレーションしていく。確定する場合は2人と出て両方にいることが分かる時と、1人出るが片方は範囲外になっていている位置が確定するときがある。
100以下の素数を列挙すると25個ある。ただ、合成数かどうかを判定できればいいので50以下の素数を用意しとけば十分。ただ、その素数ごとに聞いていくだけだと9のように1種類しか素因数を持たないものの判定ができないで気をつける。
12/27
に対して
を満たす最大の整数
とすると、次に選ぶキューブの大きさは
か
のどちらかが最適であることがわかる(Editorialより)。そして、実験してみると最大でも個数の最大値は18なので、普通に再帰で全探索しても間に合う。
部分文字列にした時にどの文字列だったかわからなくなってしまうパターンを考えてみると、同じ文字の間が全部詰まってしまって 1つになるパターンなので、s[i]とs[j]の距離がK以下で同じ文字のところがあれば不定の例を作れる。それ以外はOK。
Aを何個使うかを全探索することにすると、それに応じて最適なBの配置の方法が決まる。そうして作られたもののうち、長さがN以下になるものがあればそれを答えればよい。
12/28
答えを二分探索していく。そして、高さmの建物が立てられるかの判定は、長さNの配列を用意しておけば簡単に判定できる。
まず、現れる順番は無視していいので、ソートしておく。そして、1つの基準点を作り、その値を動かさないようにしてその前後の値をconsecutiveになるように調節する全探索をすればいい。これで、で実現できる。
まず、滞在の終わりが早い順にソートしておき、前から順番に見ていく。i番目の人がまだspecial promotionの人と繋がっていない時、その人は繋がないといけないが、このときに最も選ぶべきものは「i番目の人をカバーできて、かつ滞在の終わりが遅い人」なので、後ろから見ていって見つかった人をspecial promotionする人に選ぶという貪欲で客の数に対して
でできる。
- [SRM 644 Div1 Easy - OkonomiyakiParty]
(Unrated回なのか、リンクがなかった)(はじめにそれを確認しておいて問題を選ぶべきと言う感じがある(これ何回やれば気が済むんだ))
お好み焼きのサイズでソートしておく。そうして、番目と
番目のサイズの差が
以下ならその間から
個を選ぶことにする。その組み合わせは、2次元配列を用意して事前に用意しておくことで全体は
で実現できる。
12/29
はじめに、それぞれの町を始点としたBFSをして、到達可能な範囲を調べておく()。そして、到達可能な町にはコスト
の有向辺を張る。すると、辺の個数は
個になるので、ダイクストラで間に合う。
Oの位置を基準に全探索する。Jの個数を前から累積和で持っておき、Iの個数を後ろからの累積和で持っておき、Jを先頭に置く場合・Iを最後尾に置く場合・Oを置く位置の全探索でで出来る。
dp[r][s][j] = r行目,s番目の石にいて、一行飛ばしのジャンプの回数がj回の時の最小コストを更新していくDP。行が増える方向にしか遷移しないので結構シンプル。
座標圧縮して個のグリッドに分ける。そして、BFSなどで連結成分の個数をカウントすれば良い。
dp[i][j] = 最後に切った位置i,今の合計の長さjのときにかかるコストの最小値を更新していく。愚直にやるとだが、遷移を上手く保存してまとめるようにすると1つオーダーを落とせる。
12/30
まずはショッピングモールからの距離をダイクストラで求めておく。その次に、辺を1つずつ見ていく。そのときに、辺の両端のダイクストラした最短距離の情報を見ながらどの位置に置くのが最適なのかは簡単な1次方程式を立てることで求めることが出来るので、その最大値を更新していけば良い。これで、全体でとなる。
まず、ダイクストラして始点からの距離を求めておく。すると、Xとして選ぶのはこのいずれかの頂点までの距離にするのが最適なのは明らか(中途半端な値にする意味がない)ので、Xとして選ぶ値は通りある。これを全探索していく。そのときに残る道の長さの合計がどれくらいになるのかというのは、まず、頂点をスタート地点からの距離順でソートしておくと、その道が撤去されるタイミングは端点のうち距離が大きい方がX以内になるタイミングなので、辺をこの端点のmaxをkeyにしてソートしておくと尺取的に
で計算していくことが出来る。
まず、全体で重さが1になると仮定して、各場所にいくらの錘が来るのかを分数で表して計算する。その伝播の方法は、トポロジカルソートで簡単にできる。そのあとで、錘を全部整数に直すために錘の分母のLCMを取って計算してやれば良い。
dp[i][j][IO] = 次に使えるのがsのi文字目,tのj文字目で末尾の文字がI/Oのときに作れる列車の長さの最大値を更新していく。
2周分の累積和をとっておき、1個目の切り込み位置を全探索する。そして、2個目はsum/3あたりに、3個目はsum*2/3あたりをlower_boundで見つけてチェックする。
まず普通にシミュレーションしておく。そして、そのシミュレーションの最中に、各辺でどれとどれを入れ替えているのかを保存しておく。その辺だけを除いた時、そのシャッフルが無効になってその2つの行き着く先が変わるので、横の棒を全探索してスコアを最小化する。
桁DPをする。(B以下の条件に合う数の個数) - (A以下の条件に合う数の個数) + (Aが条件に合うか)で求めた。
CF Good Bye 2016に参加
ABDの3完。Cはケアレスミスで落としてしまったっぽい...本当に反省。気持ちよく2016を締められなかった...
12/31
本当に僅かなミスだった...(ずっとdiv2にいたときでも、最後の1回の後にDiv1に上がりうることを考慮していなかった)
読み終わる時間を最小化したいというのが前提にあることに留意すると、読むのにかかる合計時間のうち、一番時間のかかる本が半分以上を占めているとどうしてもその2倍の時間読み切るのにかかってしまう。また、そうでなければ1人は1番時間のかかる本から読み始め、2,3,4,...と読み、もう1人は2番目に時間のかかる本から読み始めて、3,4,5,...と読んでいけば、nまで読み終わった後に1番時間のかかる本は読み終わっていることになっているのでそれを読むという方針を取ることで、隙間なく時間を詰めることが出来る。なので、この場合はちょうど読む合計+書く合計になる。
ただ、読むのにかかる合計時間のうち、一番時間のかかる本が半分以上を占めている時は、1人がその本を読んでいる間に、もう1人はそれ以外の本を全部読んでも時間を持て余すことになる。その空いている時間に書けるぶんの感想文を書いておくのを、最大時間を求めるためにDPする(dp[i][j] = iまで読んで、時間jぶんの感想文を書けるか)。jが大きくなりそうに見えるが、このDPをするにあたり、そもそも余る時間は一番時間のかかる本以下なので1000以下ということになり、間に合う。
それぞれのLPG stationからダイクストラする。
トポロジカルソートする。
CF 733 F - Drivers Dissatisfaction
問題
問題概要
個の町と、それらを双方向に結ぶ道が
本ある。それぞれの道に対して、ドライバーの不満度
がある。
この不満度を下げるために、その道に対してコストが
かかる(つまり、ある道の不満度を
だけ低下させるためには
だけかかるわけである)。そして、この不満度は0や負にもなりうる。
さて、この本の道の中から
本を選んで、
main roadsとすることにした。このmain roadsの選び方として、「どの町から他のどの町にも移動可能」でなければならない。
今、予算がある。この予算を使って(使い切る必要はない)、不満度を下げてから
main roadsとして本の道を選ぶことを考える。そのときに選んだ
本の道の合計の不満度を最小にしたい。
その最小値と、main roadとしてどの道を選んだかと、不満度を下げた後のその道の不満度を答えよ。
アイデア
まず、main roadsの定義からこれによって構成されるものは木であるということなのでMSTを構成したいということが分かる。そして、不満度は負でもかまわないということから、予算の使い方としては本の道が決まってしまえばその中で
が最小の道に全ての予算をかけるのが最適なのが分かる。
この考察から、予算をつぎ込む辺を全探索することを考える。そして、それで減らしきった後に毎回MSTを初めから構成しているのではかかってしまうので間に合わない。
そこで、とりあえずを無視し、Kruskal法を使って、
を基準にしたMSTを構成しておく。そして、予算をつぎ込む辺を全探索するにあたって、このMSTに新たに辺を1つ追加するような感じになる。すると、MSTに閉路ができるので、その閉路の中で最大の
を持つ辺を取り除ければ良いことになる。それは、新たに追加しようとしている辺が
と
を結ぶならそのLCAまでの間で最大の
を持つ辺を見つけられればいいことになる。それはLCAを構成するのと同じ要領で、
でその辺を見つけられる。
実装大変すぎる...こどふぉって実装重めの問題が多い気がする。LCAのいい練習になった。
