裏紙

ほぼ競プロ、たまに日記

CF 847 L - Berland SU Computer Network

問題

Problem - L - Codeforces

問題概要

n台のルータがあり、何台かはコードで繋がれており、ネットワークを構成している。ルータの構造は木である。次のような情報が与えられるので、元のネットワークの構造を復元せよ:

それぞれのコードppと直接繋がっているルータiに対して、pを通じてiと反対側にあるルータが何であるかが与えられる(つまり、iから見た時のそれぞれの部分木の情報が分かる)。

妥当な復元が存在しない時は-1と答えよ。

  •  2 \le n \le 1000
  • 各リストについて、要素数n-1個でdistinct、i個目のリストにiは入っていない

イデア

まず、-1になる状況を考える。与えられるリストの形式から、どれを繋いでいるかは分からないまでも辺の個数を見ることが出来る。それを見て、2(n-1)個になっていなければおかしい。

辺の個数が妥当だと確認できたところで、復元をはじめていく。復元の方法としては、O(n^2)で全点対に対して注目をして、「その2点間(a,b)に実際に辺がある ⇒ aから見た時にbを含んでいる集合のsize + bから見た時にaを含んでいる集合のsize がnに一致する」ということに注目して、辺を復元していき、最終的にそれが木になっているかを確認すればよい。

実装(C++)

続きを読む

2018/1 solved(1)

一昨年やってたのを復活させます。去年は「これあんまり意味ないかもなあ、もっとちゃんと解説書く問題を増やしたほうがいいでしょ」と思ったが、辞めた結果そもそも解説書く問題が減った(ダメ)。他人に読んでもらうことは特に意識せず書きます。

1/1

行きと帰りを同時に探索する。行きは普通に探索(突き当たったら右か左を選ぶ)。帰りは、行きと同時に探索するために後ろ向きに探索する。曲がる条件は、曲がる直線に目の前に壁があることなのでそれに注意しながらあとはBFSを頑張る(submission)。

nm \le 250に注目すると、短辺が15以下であることが確定する。この時、左上から順にガードを置いていくかどうかを決めていくことを考えると、縦方向に監視が効いているかどうかをビットマスクによって管理しながらDPで数え上げることが出来る。他に状態としてもつ必要があるのは、監視の効いていないセルがこれまで幾つか(0/1)、現在注目しているセルに左からの監視は効いているか(0/1)の4つの状態を考えながら数え上げることが出来る(submisson)。

連続して現れる文字は1つに縮約出来る。すると、○✗が交互に現れる文字列になるが、この時に1つ石を置くことでまた縮約が発生すると文字列の長さが1短くなっていくので最終的に1文字になる(その文字が勝ち)。よって、隣り合う部分を見て切り替わっている回数を見ると、このゲームの勝敗がわかる(submission)。

1/2

教授たちを区間の開始位置でソートしておけば、 dp[i][j] := i番目の教授まで決めた、1~jまでの区間はカバー済みの時に必要な教授の数 としてdpを計算していくことで求めることが出来る(submission)。

相手AIの出す手はこちらの手には依存しないので、こちら側が安定して点を取るにはランダムに頼るのが良さそう。負け以外の時は前回と同じ手を出し、負けたときだけ手を変えるようにした(submission)。

1/3

同じグループになるとしたら、その点を基準にして上下左右にそれぞれRだけ伸ばした、一辺の大きさが2Rの正方形の中に入っていると言い換えることが出来る(3R以上の距離があれば、この中に同時に入ることは絶対に無い)。よって、x座標でソートして平面走査、y座標の値をsetで管理しながらUnionFindで管理していく。小数のままだと誤差が発生するので整数の範囲で管理できるようにしてから処理するのがバグらせないために大事(submission)。

?を全てaで埋めた場合が辞書順で一番後ろになり得て、zで埋めた場合が辞書順で一番前になりえる(submission)。

dp[i][j][k] := i番目の建物まで高さ決定、j個の色が見えている、その中で一番高いものkの時の、コストの最小値を計算する。i,jの部分は15以下、kの部分もそれに準じる物しか発生しないので種類としては多くならない。mapで管理した(submission)。

1/4

4の倍数の数、そうではないが2で割り切れる数、奇数の3つにグループ分けして、それらの個数の関係に注目する(submission)。

渦巻状に順番に配置していけば必ず連結に出来る(submission)。

a_iに対して、a_i -1 , a_i , a_i +1の3つの値が作れるのでそれをmapで数え、最大を答える(submission)。

1/5

i番目の要素がswapされる必要があるかどうかという0/1配列を作ると、1が連続する区間ごとに最低でも必要なswapの回数が決まってくる(区間の長さを2で割って切り上げる)。それの和を取れば良い(submission)。

2人組を優先的に使う貪欲(submission)。

うるう年を含めて3年ぶんの日付パターンを用意しておけばチェックしきれる(submission)。

答えは、1,2,...,nの和が偶数の時は0、奇数の時は1に出来る。それは、和をsとすれば、s/2を超えないようにn個の数字を大きい方から貪欲に取っていくことで実現出来る(submission)。

奇数長の閉路があると、必ずどこかで破綻するので、奇数長の閉路があってはならないことが分かる。そうすると、構築できるグラフは二部グラフであり、二部グラフに生やす辺の個数を出来るだけ最大化したい、となると頂点数をできるだけ均等に分けると良いことになる。そうすると、辺数の上界が定まり、下界は連結である条件(n-1以上)によって、不可能判定が出来るようになる。あとは、最初のn-1本で連結にして、残りを二部グラフに埋めていけばよい(submission)。

リストの先頭に0を足しておくと、全ての隣接箇所の差の絶対値が1になっているかで判定できる(submission)。

mapで数えて、keyとvalueを逆にしてソートし、答えを出す(submission)。

頂点ベースではなく、辺に注目して、その端点から生えている辺を全探索し、パスが有るかを判定する(submission)。

駅に辿りつくのにネックになるのは、max{t[i]+3*(n-i)}であることが分かるので、この値を区間addができるSegtreeで管理する(submission)。

1/6

XORの性質を考えれば、AB = C なら AC = B になる。

3個以上の山が1つでもあればBが調整できてしまうので、無条件にBが勝てそう。そうすると、1個の山と2個の山がいくつあるかが重要になる。2個の山が2つ以上あってもBが調整できてしまう。2個の山が1つ以下なら、1つずつ取っていくという状況に持ち込めてそこで初めてAに勝機がある(submission)。

1/7

グラフを構築して一筆書できるかチェックする。連結性のチェックをした後に、次数が奇数の頂点の個数を数えて、0か2なら一筆書できる(submission)。

1/8

1/9

mod tex:10^8+7に気づかず時間溶かしまくった。左回りと右回りが同じ距離の場合があるので、その時は2倍になる(上下も同様)。

最短でi( \gt 0)歩でたどり着けるグリッドは4i個あるので、その歩数を歩ける兵士が何人いるかを見て、それ以上いたら4iで抑える。nの制約から、これをチェックするのは125までで良く、それ以降は必ず被り無く歩くことが出来る。

1/10

数は結構大きくなってもいいということに注目すると、n!を用意してしまえばn!+iはiで割れることが分かる。

treapがあればできるという気がしたので、treap実装の練習をした(submission)。

1/11

1/12

imulan.hatenablog.jp

パスカルの三角形のn段目は、nのビットの立っている個数の2乗のぶんだけ奇数の項が存在する。それは二項係数などを考えてみると分かる(https://www.math.hmc.edu/funfacts/ffiles/30001.4-5.shtml)。

1/13

まず、末尾にいくつまで9を付けることが許されるかをチェックする。その後は、19...9,29...9, ... , 99...9を作れる組み合わせがそれぞれ何通りあるかを計算すればよい(submission)。

第4回 ドワンゴからの挑戦状 予選に参加

ABCの3完。CのDPは自分が速く書けるタイプのやつだと思ってたのに1時間もかけたのは良くない。

1/14

どのタスクは処理したかをフラグにもつbitDPをする。遷移の仕方が自分では書いたこと無いタイプだった(submission)。

setで{区間の長さ,開始位置}を管理すると、次のターンで取り除く区間がlogで求めることが出来る。また、双方向リストのかたちで隣接関係を管理しておけば、区間を削除した後の左の区間と右の区間を連結させるのも簡単にできる。そのとき、それらの区間が同じ数字なら区間を合成することになるが、それも容易に出来る(submission)。

1/15

文字種類ごとに、その文字が現れるindexをsetで管理すると、削除のクエリに対して全体を通してO(nlogn)で処理することが出来る。問題は、与えられるクエリの区間が初期状態のどの区間に該当するかだが、これはまだ残っている文字の位置をsegtreeで管理すれば、二分探索によって見つけることが出来る(submission)。

Codechef January Challenge 2018に参加

自明なとこまでしか解けなかった...要復習。

1/16

yukicoder No.584 - 赤、緑、青の色塗り

問題

No.584 赤、緑、青の色塗り - yukicoder

問題概要

一直線にNマスが並んでいる。各マスを赤、緑、青いずれかの色で塗ることが出来る。塗らないマスがあっても良い。マスを塗る条件として、

  • 同じ色は隣接してはいけない
  • 異なる色であれば連続する2マスを塗ってもよい
  • 連続する3以上のマスを塗ることは出来ない

がある。赤、緑、青の色で塗らなければならないマスがちょうどR,G,B個ある時、マスの塗り方は何通りあるか、10^9 + 7で割った余りを答えよ。

  •  1 \le N \le 3000
  •  0 \le R,G,B \le 3000

イデア

色が入ったマスの塊としては、1個と2個の2種類しかありえない。2個の塊をi個作るとすると、1個の塊は、色をぬるマスの個数はR+G+B個なのでR+G+B-2i (=O)個になる。

さらに、2個の塊には、色の組み合わせとしてrg,gb,brの3通りがある。2個の塊のために、赤をj個使うことにすると、gbの塊はi-j個必要になる。また、残った赤(R-j個)は1個の塊に必ず使うことになる。

この時点で、緑はG-(i-j)個、青はB-(i-j)個残っている。まだ色が決まっていない枠には、この2色のどちらかしか入る余地が無いので、それが何通りあるかを求める事ができる。

以上より、ijを全探索して全ての組み合わせが求められる(O(N^2))。細かい組み合わせの計算方法はコード参照。

実装(C++)

続きを読む