hogloidのブログ

へなちょこ

解いたものリスト

個人的良問リスト - hogloidのブログ ←4年ぶりに戻ってきました

今回は、主観的面白さでoを0個〜3個つけています。 ☆は自力では解けなかった問題です。 月間更新予定。2017年1月は簡単めのSRMばかりやってたので簡単めのSRMばっかりです。

個人的備忘録のおまけ程度で書いてるのと、あまり真面目に書くとコストが高くなって疲れるので、荒い書き方になっています。おかしな点・分からない点があれば直接訊いてください。

markdown記法を使ったら一部数式が意図しない解釈をされているみたいです(後で直します、あとで…

nothing

529H: 式を適当に変形すると、B,S,#{Big Airport}を固定したらNの上限と下限が求まる形になるからそうやって求める。#{Big Airport}は小さい範囲で動かす(他はかなり自由なので別に求める)
534H: 同じ場所は二度swapしない、とかの考察を進めていくと、欲しい文字を持ってくる&書き換えで済む。 別解多し。o
549H: 全探索してフロー流す。たぶん全探索は色々あるけど、315通り辺の張り方試す(辺を加えながら閉路が生じないかチェック)→辺ごとに高さが1違うかチェック→それが取り方の数の制約を満たしてるかDPでチェック→フロー流せるかチェック をした
550H: (maxCost-(必ず必要な操作のコスト))/33回まで操作できる、としてよい。(s[i]=t[i], s[i]=t[i]+1, s[i]=t[i]+2)(等号はmod3)となる桁の数の3つ組を状態とする遷移が行列で書ける。状態の数は78個ぐらい。あとは、s=tとなる状態を何回訪れたか数えるよう1つ行を加える。
581H: ふつうのbrute-force. 一番上の列を3w通り試して残りは自明に操作が決まるのでそれがvalidか確認し、validなもののminを取る。当時はflipをbit高速化しないと通らない?かも(今やって1.8sec)なので
586H: なんか貪欲っぽく行ける気もする…が収拾つかなくなったのでDP。dp[何番目の文字列まで決めたか][未使用文字][もう使わない文字]:=最小値 みたいにする。遷移で、新たに使う文字、ここでやめにする文字、ここで始めここでやめる文字の数を試す。L_iのうち26以上の数で挟まれたところは消しておき、26以上のiを高々2つにしておくと、「ここで始めここでやめる文字」を非ゼロにするのはその二つのiだけでいいので計算量がよくなる。(C4
(N+C)) オーダーが高次多項式のときありがちだけどあまり何も考えなくても通るっぽい…(実際それで大丈夫そうな気もする)
615H: 簡単すぎィ! 列をつくれるかどうか⇔Rの数-Gの数がどのprefixも0以上M以下、RGの数が2Mの倍数なのでindex,R-G,R+G mod 2M でDP
640H: N2通りの差の素因数を調べればいいが、そのままやるとTLEするので、104.5までの素数についてはその素数でのmodでソートしてmodが同じものの間に素因数を追加、104.5よりでかい素数は1つしか持ち得ないので、それまでの素因数で割っていき1にならなかったらそれが残り。
634H: 2点を結ぶ直線とそれをepsずらしたような分け方のみ考えればいい。1点を原点に固定して、最初は(Y<0 || (Y=0 && X<0))とそれ以外に分けて、ぐるぐる回しながら入れたり出したりする。原点を入れるか入れないかの2通り回せばいい。
645H: 包除原理して、2回できない集合Sを固定する。Sの各元について、2回できないことを決めたので、0回か1回、これをbitDPにして求めていく。DPは[i日使う][1回乗った集合はT]:=通り数、ただし通り数にはS以外のものを遊んだ?回数をカウントする。カウントの仕方はSの部分集合全部についてS以外の部分集合のとり方がいくつあるかを愚直に数える。O(4N*N)
646H: 二分探索して、何位に入るか決め打ち、それより上のチーム・自分以下のチームはすべて勝つことにして、Win/Lose/Drawがいくつあるか求める。 W>=L+(D&1)が必要条件で、加えて自分自身と戦ってしまわないといけないもの除かなければいけないが、W-Lについてはその心配はない(自チームは必ず勝つためそこで組み換えできる) W-D,W-Dも同様。D-Dのみが問題で、2回とも引き分けるチームがありDがその2つだけのときがNG。WLはDDに変えると得になるケースがあるが、↑の理由の通り全部試す必要はなくて2,3個変えればいい 悪問ではないけど嘘じゃないと確信するのが大変で解法自体は思いつきやすく微妙…
679H: 簡単すぎィ!

o

530H: ふつうのDP.よくある、動かすときに決めないで後回しにしておくやつ。 o
532H: ふつうのDP.rowがsimilar⇔ソートした時に一致、なので、ソートした状態で左から決めていく。N行が今のところ同じ、あとM列ある、色はK色使える、色0を今までL個連続して取っている、というキーがあればDPできる。(最後のは同じ色での塗り分けの区別を同一視するため) o
540H: 10=25 で、mod 2に対する答えとmod 5に対する答えを掛け算すればいい。これで見通しが良くなるのであとは前処理(右端が同じ制約を二つに分割、を繰り返す)をしてDPするだけ。 o ☆
559H: たぶん二分探索が楽。[-PI,PI]の数直線上に、どこからどこまでが覆われるかを置いてくやつ。円と円の交点を求めるライブラリがあればヨシ。 o
578H: 切断する辺を決め、rec(v,p1,u,p2):=(p1-v)のv側の部分木、(p2-u)のu側の部分木についての最大値 としてメモ化再帰。毎ステップでは最大重みマッチングする(=>最小費用流に落とす) 負辺だろうが構わず解くライブラリ使ったらその定数倍で落ちた…(できるなら変形したほうがきっと早い)(適当に自明な高速化をしたら通った) o
584H: 最小有向全域木。頭によぎれば帰着は簡単 reachability,loop とかの確認を怠ってはいけない(戒め)けどどうせサンプルにある o
591H: 上からDPしていく。(点とその上1行分にA,Bを到達させることができるかが状態) 斜めに埋めようとしてしまいやたら面倒になったorz o
604H: 無限に置けるかは、ある微小なベクトルがあってその分だけずらしても重ならないようなものがあるかと同値。どちらかが端点でない交点があったらだめ、ある点に3つ以上別の角度から伸びていたらだめ、そうでない場合はなす角とその逆側だけOKなので、共通部分があるか判定する。 o
613H: 行の左右は独立。左の列から順にDPで埋めていく。状態は[i:何列目][i列を含むleftの行のうち、チェッカーおいたのはいくつか][i列を含むrightの行のうち、チェッカーおいたのはいくつか] o
614H: 初期位置が0,0の代わりにゴールを0,0にする。連立方程式を解きたいが、(NM)3かけるとダメなので、グリッドの周縁部だけそれらの間の確率遷移を求め、期待値を求める。初期位置から周縁に行き着く確率を求め、掛け合わせる。 o
617H: それぞれ独立に、Lex.smallestのgreedyに沿って考える。あるprefixがOKかどうかは、それからある文字の埋め方が存在し編集距離をK以下にできる&&それからどう埋めてもK未満である、ということはない 編集距離はDPで o
631H: クエリーの平方分割して、出てくるu,vだけマークする。それ以外の頂点はスキップし、その間の辺の最大値を持つようにする。クエリーに対し、vから登るときにスキップしたグラフを使えばO(B) 前処理もO(N)でできる o
633H: 素因数ごとに考える。ある2数について指数のでかいのはいくつ、小さいのはいくつ、という条件がたくさんつく。これを、ある2数の指数はhoge以下・2数のうち片方の指数はhoge という条件に分解して、1つ目でNGならNG。1つ目はOKだったら、それぞれの数に上限か下限のどっちかを与えるのがよい。辺ごとに、片方を上限にしたら片方を下限にしないといけない(上限と下限が一致する場合を除く)ので、2SATにして解く。 o
635H: 少ないのから順にA,B,C,Dとして、左からA/Bだけ置いてく。dp[Aをいくつ使ったか][Bをいくつ使ったか][A/Bの間または端のうちnon-emptyなものはいくつか]:=通り数 でDPして、最後は適当に求める。 o
642H: prob[i回spinした][場所0のスコア]:=確率、exp[i回spinした][場所0のスコア][K]:=場所Kのスコアの期待値 として求めていく o
653H: 0,1,2に対しRock,Paper,Scissor(R,P,C)をそれぞれいくつ割り当てるかになる。3
3の行列にしてみると、それぞれの列・行に対して値をいくつかに割り当てて、要素は列と行の値の和になるかどうかが必要十分.これはO(m2)で全探索できる(m:最小のカードの数) なんか合わなかったから必要条件集めてO(m3)で候補を全部あげてそれぞれ可能か確認する方針でも通った o
666H: 区間としてカウントするのは、入っていてかつ他の小さい区間に入っていないもののみとしてよい。すべての区間について、[いくつ左に1が続いてるか][今までの1の数の偶奇]の状態組についてこれをこれに移すのがいくらあるか求める。行列累乗とかを使う。 o
668H: DP.一番内側でないカッコは1回しか通れないことに注目。(∵内側のカッコを出るとき値が0で、同じ動作を繰り返してしまう) dp[残り長さ][今の値]:=残りの長さで値を0にする文字列の数 として求めていく。+,-は普通に入れる。は同時に挿入して、長さ・その中で値をいくつ変化させるかを試す。1回で0にならない場合、その中身にがあってはいけないという制約がつく。全体の答えは、↑のDPで最後が0にならない版(同じように解ける) Nまでの約数の和はO(NlogN) なので、 O(N3logN) o
670H: 1~9を互いに区別して部分集合に分ける方法は20000通りぐらい、そのうち細分になっている関係は1.6e6ぐらいなので、まずこれを全列挙する。あとは、ある分け方についてその分け方またはその細分になっているものは、ある辺集合を使わないということと同値なので、その辺集合を先に掃き出す掃き出し法を使えば簡単に求まる。その後、細分の関係を用いて、ちょうど分け方があるものになる通り数を求める。分け方にid付けるとき、mapでやるとTLEするので、trie木を使った。O(へんなの) どうやら200002かけても細分か否かをbit演算でやれば通るっぽい?:angry: o
674H: コスパのいい方を80個以上使ってなかったらそっちに寄せての要領で、最低使用量を決めて残りの重さ803をDPする。O(N4) 2べき分解→小さいのから詰めてく、というやり方でもできる。前者は境界が面倒なのでこちらのほうが楽? o
707H: 動かす⇔コスト-1の辺をたどる にして最小費用流 o
517H: 可能判定は後ろから埋められるところを埋めていけばいい。最小化は、埋められるところが1つでも見つかれば、それを埋める場合について再帰的に解く。それ埋めない場合、逆側の(列/行)は残ってる全てをその色で塗らなければいけなくなる。こう決めたとき可能かどうか・最小値を求る。 o

oo

537H: 最小費用流に言い換えると、最小流量1、コスト全て負のグラフ、source,sinkは無しで費用を最小化する問題になる。 そのままでも少し強いライブラリがあると解ける。逆に、全て辺を流した状態からどれを消すか考えると、費用が正のsourceやsinkのあるふつうの最小費用流になる(どっちも同じことだが) source,sinkにこだわっると前者が見えない(見えなかった) oo ☆
555H: i番目にheadをおいた状態から始めるとすると、何回かそこで完成するチャンスがあるかもしれないが、一番後のものだけ考えればいい(後のものはそれまでの可能な初期値を全て可能とするため)。iについて自由に数を決められるところのbitmaskを持つ。次に、包除原理する。ここで、goalと全く同じ置き方だけは除外して考える。すなわち、Σ(Sの元)番目にheadをおいた状態から始めてすべて可能となる初期状態の数(-1)|S|-1の総和を求めればいいのだが、Sの元から始めたときすべて可能になる部分はbitmaskのandを取って1だったところなので、codeが影響する長さに制限される。逆にこれが長いと、外にはみ出ない制約から有向な初期位置自体が減るので、うまくやると218182とかになる oo
567H: 山をn-1,n-2,…,0と置いてく。全ての列で見える山が見えない限り、置く候補は高々2つ(2つずらそうとすると端が動いてしまう).全ての列で見える山があるとき、素直に全部試す。状態として、マップ全体じゃなくてそれぞれの列の最高地点の配列を持つと、これで自然と状態数2n+nnになる。 oo
576H: |S|で場合分け。ある長さLについて、indexの差がLの倍数のときそれは同じ文字でないといけない。あるマスとあるマスが同じ文字でないとけない、という条件で、片方からもう片方が導けないようなものが二つあるとき、そのGCDは2000以下。(∵縦にa,b違うとき、a
bマス下の行で二つは高々長さ2000で同時に出てきてしまうため)。よって|S|<=のときは全部試す、それ以外については同じでなければいけないという関係ごとに全部見る、どの関係にも属さないものは2|S|-n*m (実装が結構たいへん)(最初に候補を全列挙したほうが楽らしい) oo
580H: 下からDPを埋めてく。i行目に初めて到達して、それがj列目のとき、以後のコストは「min{行内の任意の経路} max{経路の途中で初めて通る列} そこで降りたときのコスト」(maxが成り立つよう壁を張れるし、ある経路に対しそれよりコストを掛けさせることは不可能) これを用い、さらにDPする。列内でくねくね動くことはありうる。(状態は、左、右、行内の移動でのそれまでのコスト、今左端か右端か 3番目の数が9502になるのでは?→ならない。同じ行の初めのDPのコストの差は高々450なので(∵初めに横移動すればいい)、ここで675+450以上掛けるぐらいなら列内を左右に舐めたほうがいい。) oo
588H: Bobが勝つ⇔ある頂点で、そこから伸びる部分木の高さが3以上のものが3つ以上あるところに、BobがAliceより2ターン早くたどり着けるものがある 確かに、思いつけばそれはそう。AliceがBobの方向へ向かっていく感じの解法でもできるが、場合分けが結構大変。 oo
593H: ふつうのDP.dp[i]:=i文字目までの文字列での組み合わせの数、とすると、最後のw..wo…oを全部試すとO(N2)になる。最後の付け加え方について、Sでのwを含むかどうかで場合分け。含むものは、i以前の最後のwとその前後のoから、区間が決まる。含まないものは、逆にdp[i]を求めたときにどこまで可能か次のw,oの場所からすぐわかるので、別に足す。 oo
596H: n = k (mod divisor) ごとに考える。はじめてn
(n-1)…(n-k2) = 0 (mod divisor)となるkを求めておけば、条件を満たすnがどこ以上か分かる。divisorを素因数分解して、うまいこと合成するとできる。 oo
597H: 1列のRG,GB,BRを0,1,2とし、0,1,2をX,Y,Z個置く問題として考える。0で隔てられた残りの部分で奇数個のものがi個となるような置き方を数え、残りの1,2をどう埋めるかの数を掛け、足し合わせる。(奇数個残したいところは0に(1or2)を、偶数個残したいところは0に(1or2)を2個くっつけて組み合わせを取る感じ。左右は場合分けしないといけない。長さ0の場合1,2の埋め方が1通り、他の偶数は2通り) oo
603H: C[i]:=Σmin(a[j],b[i-j]) でC[i]最大の値を求めたい。a[i]>=M,b[j]>=Mとなる(i,j)の組については前通り試し、そうでないものをFFTで数える。min … がk以上となるようなものがCにどれぐらい寄与するかは、 A[i]:=(a[i]>=k?1:0) B[i]:=(b[i]>=k?1:0) という2つの数列をたたみこめば求まるので、合計でO(N4/3(logN)2/3)で求まる。 oo
605H: こんなのどうせでかいのor小さいのから見るに決まってる…かと思いきや、編集後も残りの要素は連続するし順序が保存されるので、左から埋めていくとうまくいく。P[i]がどこまで広がれるか(それより小さい要素のある範囲)を求めて、どこまで埋めたか、次使う数はどれか、何回操作したかでDP oo ☆
608H: 縦軸を時間、横軸を位置としてグラフぽいものを描く。あるA,Bについて、左の壁に接するなら、それより初期位置を左にずらしても最終位置は同じ。右も同様。B+Aを固定し、両方の壁にぶつからない範囲、右につぶれる範囲、左に潰れる範囲に分けて計算。(整理してから実装しないと実装が躍動して大変なことになった…) oo
610H: XY独立。後ろからDPしていくことを考える。利得のかわりに逃す利得の最小値を考える。毎ステップ、ある点を中心にV状に足して、その後小さい値を近くに均していく感じになるが、この形は常に谷状・下に凸になる(帰納的に示せる) DPテーブルをグラフとして見たときの折れ線の傾きが変わるところを全部配列で持って、V状に足すのと谷をでかくする操作をする 谷底の高さがどれだけ上がったかを毎回足し、和が逃す利得 oo
705H: 行列にスイッチのベクトルを掛けて出てくるベクトルのうち1になる要素を最大化したい。行交換・列交換はしてもOK。列の足し算もしてもOK(スイッチの付け方にある変換が施されるがその変換は全単射なので) これを使い掃きだした形が下三角になるよう掃き出し法みたいなことをすると、N個のスイッチのうちいくつかは使っても使わなくても関係ないものになる。残りの有効なスイッチの数をL個とする。L<=27なら全探索。L>27のとき、L個のライトはある1つのスイッチを押すかどうかだけで点くかどうか決まるので、それ以外のM-L個について、いくつかスイッチを押すか押さないか決めたときに点くかどうかを持つbitDP。 oo ☆
705M: これすき ある2つの箱の中身が何回かの(同じfunctional graphとは限らない)操作を経て同じ箱の中身になるかどうか予め求めておく。初期状態から、併合できる箱の中身はどんどん併合してしまう。もう併合できなくなったら答え。(なぜこれでいいかというと、どんな状態も初期状態のsubsetなので最適解にたどり着ける) ☆ oo
625H: まず、DPで[i人おいたとき][j個のクラスターになっている]というものを、クラスター内の順序が同じものはすべて同じとみなして数え上げる。最後に、jこのクラスターを適当にテーブルに配置する。クラスターの個数が同じなら、どんな人数の割り当ての違いがあっても配置の数は同じになるため。 oo
627H: フロー。それぞれのセルに縦か横を割り当て、S側が横にするセル、T側が縦にするセルとする。敵を倒せない割り当て方について、敵のスコアだけカットが生じるような辺を張り、答えから引く。タワーから見てより遠くでよりスコアの小さい敵は攻撃しない。これで単調になる。横のタワーから見て、ある敵までのどこかで縦のセルがあった場合-(敵のスコア)としたいので、横のタワーの頂点から流量(敵のスコア)の辺を新しく作った頂点に張り、その頂点からinfの辺を敵までのセル全てに張る。縦については流れが逆 oo
629H: 結局 PI_{k=1}^N (x+k) でのxKの係数を求めたくなる。これはNについての2K次以下の多項式なので(∵Kについての漸化式がべき乗の和とかを使ってかける)、N<=2KぐらいまでをDPで求め、多項式補完する(多項式を求めるんじゃなくて、直接そこにNを代入したほうが楽) oo ☆
654H: s0-s1のパスではじめに使う頂点で場合分けしようとすると、その点の両隣のパスの辺でグラフを分けたとしても同じ置き方ができる。パスの長さが偶数のときはこれでよし。奇数のとき、s1をパスの中で最も早く使わなければいけない、という条件がつくが、これは単にs0のみでおけるということ。 O(N2) oo
657H: (a,b),(b,c)に辺があり(c,a)にも辺があるならa,b,cは横か縦に揃えて、(c,a)になければ(a,b,c)で横・縦別に置く。これが構成できるかO(N3)で確認。確認したら、1つ辺を決めると残りは全部決まるので、置いてく。連結成分ごとに独立なのでDP。孤立点のみは横に置こうが縦に置こうが同じなので別処理 oo
664H: dp[マージソートのどの区間に対応するか][何回比較するか][与えられたやつの対応する部分列とのLCPの長さ][LCPの次の値が小さいか大きいか(実際は、小さい/それより後ろはdont careのほうがいいかも)]:=通り数 でDP。メモ化再帰のほうが楽なきがするけどそれにしても大変。O(N5logN)な気がする(実際ははやい) oo
669H: 下の桁から埋めるDPをするが、重複が出ないよう、[Miを1を使いつつ1,M,…,Mjまでの和で作る通り数]を求め、Miずつ使う最小のコインで場合分けて足していく。この通り数もまたDPで計算する。Mi=M
M^{i-1}なので、同じようにMiずつ使う最小のコインで場合分けて足す。 oo ☆
671H: 上から埋めてくのは間に合わないが、斜めに埋めてくとWH2min(W,H)の状態でbitDPできる oo ☆

ooo

525H: 自己同型を求める問題であること、その上で角柱であることが分かればGoal。発想度高し ooo
526H: 1つ文字列を加えることで、i文字目までマッチしている確率ベクトルを変化させるような操作を考える。この操作は500回以上やっても500回やったのと同じ(500回以上前に付けた文字列は 「i文字目までマッチしている」に影響しないから) ooo
545H: ビットごとに制約がついているものとみなし、包除原理を使う。つまり、Σ(Sの元の桁の制約をすべて満たさない個数)(-1)^|S| を全てのSについて求める。集合Sを固定する。(Sの元の桁が全て1の要素の数)はR/Bを自由に決めていい。Sの元の桁の制約を破らなければいけないため、その桁が0の要素はR/Bの片方に寄せる。どちらに寄せるか2^|S|通りあるが、このうちi桁目とj桁目がどちらも0のAの要素があると、自由度が1減る。こんな感じの連結成分の個数を数えればいい。22020*20使うとTLEするので、探索にして毎ステップの計算がO(桁)になるようにする。 ooo
577H: それぞれのセルに、左右で塗るか上下で塗るかを割り当てることにすると、そのコストは (隣り合うセルで左右の塗りが異なる組+上下に塗るが上下にもうセルがない辺+左右に塗るが左右にもうセルがない辺)/2となる。(始点と終点を両方数えていることになるため) これはフローに変形できる。隣り合うセルの間に辺を、上下にセルのない辺にはSから辺を、左右…はTに辺を貼る。(最小カットを考えると理解しやすい) ooo
587H: ある辺の張り方が3彩色可能⇔ある長さWの文字列Sが存在し、全ての行について、その行の文字列がSかSのflip(NZ交換) NZのボードをグラフにしたとき、内部で次数が奇数の点があってはいけないことを考えると確かにこれが必要になる(もっと自然な導き方あるのかな…) あとはグラフをbitmaskとかで作りdfs、辞書順greedy ooo
590H: 始点からの最短経路長は、辺で結ばれたものの絶対値が1以下で、0以外は正ならなんでもOK.i番目の頂点への最短経路長がk以下かどうか、という頂点をそれぞれ作り、最小カットを求めればいい。(S側が正しくない述語、T側が正しい述語ととらえると、(i,k) -> (i,k+1)には(want[i]-k+1)2の辺を、さらに辺でつながった(i,j)には(i,k+1)->(j,k)にINFの辺を張ればよい) ooo
KUPC_K_Xor回廊: 綺麗な上汎用性が高そう。今更解いた。 ooo
667H: 順列が作るサイクルに注目する。両側にあるサイクル2つは対消滅できる。(サイズn,mとする。0-0,n-1-m-1,0-i(0<i<m-1),i-0(0<i<n-1),0-m-1,n-1-0の順でswapすれば綺麗に消える) これを使えば同じ側にあるサイクル2つも対消滅できる。サイクル1つは、i-0(0<=i<n),0-0とswapすれば消える。 ooo
518H: 分割統治を考えてみると、O(L2logK)でできる(行列を持つ必要はなくて、なぜならどの行も1行目にxorで入れ替えたものだから) 実は2つの間の(indexをxor、中身を掛け算)の畳み込みはO(NlogN)でできる。X=(A|B),Y=(C|D)とすると、Z=X$Y=(((A+B)$(B+D)+(A-B)$(C-D))/2,*1/2)でできる($は↑の演算) 合計でO(L log L logK) ooo

*1:A+B)$(B+D)-(A-B)$(C-D