rng問題
埋めてます
面白かった問題を順次追加していきます
ネタバレしてるので注意です
ColorfulCards (SRM495 d1e/d2m)
できるだけaなことをする+できるだけaでないことをする(貪欲) をして同じ結果なら1通り
CarrotJumping (SRM478 d1e/d2m)
かなりアドホックなeasy.実はどちらの操作も同様な関数の合成で書ける.
PotatoGame (SRM472 d1e/d2m)
難しすぎる.数論.実験すれば瞬殺だし答えがわかれば証明も簡単.
RabbitNumbering (SRM463 d1e/d2m)
選べる集合が単調増加になってる典型DP
ところでRabbitNumberって問題もあるんだね,紛らわしい
BrightLamps (TCO14_3A e)
連続するk個をひっくり返す→a~とa+1~をやってaとa+kのみを反転
わからなければちゃんと定式化すれば解ける
MysticAndCandies (SRM608 d1e)
これも定式化すればわかる けどオススメ
ScoringSystems (TCO13_final e)
個人的にはそんなにむずくないけどおもしろい.こうするしかない,という感じのことをする.
FruitTrees (TCO13_2B e)
よく考えると3つのgcdがどうちゃらみたいな話では全く無く,aの基準からどれだけずれているか を全探索すればいいだけ.aとbの周期はLCMなのででかいのではと思ってしまうがよく考えるとまたcとgcdをとるのでなんの問題もないのだった.
Chromatic Number (TCO12_3A e)
次数が2以下制限はサイクルと直線だけうまくやれればいい. 今回はそれの補グラフ.
2/18追記
YetAnotherCardGame (TCO15_2C e)
難しいと思います
TheProgrammingContestDivOne (SRM502d1m)
ものたちを選んでいくんだけど順序が重要で,しかしxもyも使うならxを先に使うべき,みたいなのが他何を使ったかによらず決まる という時にソートしてからDPする典型テク.
ThreePoints (TCO12_2C m)
別立てで記事書いたけど,条件を逆にするだけじゃなくて緩めるみたいな発想はなるほどなって感じ
KiwiJuice (SRM478d1m)
注ぐ系はまあこどふぇのアレが重要だけど,大きさが一緒ならこんな感じのこともできるよっていう.満タンや空は意味のない物体になります.
BigO (SRM608d1m)
昔めっちゃ感動した.今考えると当たり前だよなあって感じ(解法わかってるんだからそれはそうなんだけど)
PuyoPuyo (SRM484d1m)
適当なDPで解けるんだけど,めっちゃ綺麗なDPがあって,dp[x]=全消しに必要なぷよの個数.よく考えると常に正しい色は一つでそれ以外だとL-1増えますよね(dp[0]だけはつねにdp[1]に遷移)
DengklekMessage (SRM526d1h)
これは良問.空文字列に,文字列集合からランダムに取ってこられた文字列を足す みたいなのを何回もやって目的の文字列tが出てくる回数の期待値を求めるんだけど,それには今の文字列のsuffixがtのprefixとx文字一致してる確率 が求まればよく,これの遷移行列を考える.よく考えると例の確率には直前のx個くらいの文字列しか関係ないので,遷移行列は冪等で,x乗以降は計算しなくても良くなる.
CucumberWatering (TCO12_2A m)
式を立てても全くわからなかったけどグラフを書いたらわかった
LongSeat (TCO15_2C m)
なにこれは・・・
わけがわからない問題はとりあえず定式化しましょうということがよくわかる問題.並べる→不等式→牛.
ModuloCounters (TCO13_wild m)
これは良問.01列を足してく気持ちになる.差分取る系(南京錠のやつみたいな)かと思ったけどそうではなく,今回は足せる列がわかりやすい形なのですぐわかる.やっぱちゃんと式の形で書くのが重要.(もうこれ当たり前すぎるな)
EllysChessboard (SRM577d1m)
Manhattanなので回転させ,x,yが大きいとこと小さいとこから考えていく というのは典型(ex.NYC2015 空港)
ScotlandYard (TCO13_2B m)
考察が面白い.(特にグラフから)グラフを新しく作ってそこでなにかするみたいなのは結構あるよね.最長経路はYahoo知恵袋で調べましょう.(トポソ)
あとはだいたいd1hですね・・・（◞‸◟）
TreePuzzle (TCO14_2A h)
めっちゃ頑張って考察して木DPするとO(N)
O(N^3)が賢すぎる・・・
木上で赤い点をどかしながら黒い点を動かすんだけど,赤い点がいる場所を辺だと思う.辺だと思うと,木がちょうど2つに分断されるので勝ち.点だと遷移方法がさっぱりだけどこれだとうまくいく.天才かよ
GameOfLifeDivOne
今やってるんですけど、むーりぃー → やるだけ
StrangeElevator
どういう形してるか考えると、再帰的な定義がしたくなって、それに従って式を立てると解けます
NumberMagic
これかなり難しいと思うけど、とりあえずにぶたんして、違う方向から考えると解ける(K個ずつ、はとてもじゃないけど無理そうなので、とりあえずできるだけ小さくしてみる、自由度がかなり高いので均せそう という発想)
FrozenStandings
- 1する人の集合全体の集合(2^N要素)を、順位表が同じという同値類で割ったものの類の個数を求める問題.とりあえずpair(x[i],-i)でソート. 順位表が同じ⇔任意の二人の大小関係が一緒(そ) で、大小関係の内変わりうる部分ってのは元々xが負けててこいつが+1してyがそのままだとxがyを抜かす というような状況.xを固定するとこのようなyはxの次から連続する区間になっている.
なので、N頂点のグラフがある.上述のようなx,yの組に有向辺を張る.頂点を2食で塗り分ける(黒:+1,白:+0), 黒→白 のときだけ辺が光る. 辺の光り方は何通りあるでしょう という問題に言い換えられる.
どういうときに同一視が起こるか考える.要素xを固定する. xに辺を生やしている区間を[l,x),xから辺が生えている区間を(x,r)とおく.xが黒だったとすると、(x,r)の白黒によってxから生える辺が光るかどうかはすべて異なる.
xが白のときはxから生える辺は全て光らないので、これだけでは[x,r)全黒と区別がつかない.それでもxの左にちゃんと黒があればそこによってxの白黒で光り方が変わるので区別できる.
結局、[l..x)白,[x..r)黒 となっている状態だと[l..x]白,(x..r)黒 としても順位表は変わらないことがわかる. なので、頂点のsubsetが与えられたときにxを選んでいって上述の操作をできるだけ施すことを考える.同じ同値類の中を渡り歩くことに注意.
上のようなものがない状態のことをvalidと呼ぶ.まず、有限回でvalidになって終わる(黒が減るので).
次に、異なるvalidな状態は異なる順位表を生む.
このことから、各同値類の代表元としてちょうどひとつvalidな盤面が存在することがわかる. よってvalidな盤面の数を答えれば良い.
これはただの禁止文字列で、包除する. 各禁止文字列s_xが[白][黒]となっていて、s_xかつs_yを満たすにはs_xとs_yの範囲が異なることが必要になる.なのでもう白黒は忘れて良くて、左からdp.
