裏紙

ほぼ競プロ、たまに日記

2018/6 solved(1)

6/1

6/2

6/3

長さが短い方から注目して消していくことを考えると、残ってる中で一番短いのを消すことを考えるときには、矩形の左側はそれを含むように取れる必要がある。あとは、それを上下にどれくらい伸ばせるかをチェックして、削除を実行するというのをシミュレーションする(submission)。

もし答えがあるなら結構小さめのところで見つかるだろうというあたりをつけて、回数を1,2,3,...と決め打ちしながらゲームのシミュレーションをした。ただ、1つ注意しないと行けない点が、xが答えになるかを調べる探索のときに、もしそれ以前にゴールできる選択肢があたえられたとしたらゴールしてしまっていいというところである(そこの終端条件を勘違いしてWAした)(あと、はじめはステップ数と到達可能性だけ考えりゃいいだろうと思ってたけど、場所に応じて3つの中から最適に相手が選んでくるということを考慮しないといけない)(submission)。

Bubble Cup X - Finals [Online Mirror] Virtual

全方位木DPバグらせすぎて辛かった。あと、木上でのMoは要復習。

6/4

緑のA+B点をAとBに分解して考えられれば、赤と青を独立に考えてしまうことができる(submission)。

必ず毎回左右にふるのが良さそうとはなんとなく思った、あとその振る回数は任意で、いらないのはその途中に適当に置くことができるとも思ったけど、右側と左側で別々に貪欲にとっても最適な場合は大丈夫という発送には至れなかった...解説がわかりやすかった(submission)。

それぞれ、条件ごとに禁止されるペアに辺をはると二部グラフになっている。すると、2つの条件で、二部グラフを二種類作ると、各点は4種類のどれかに分けることができる。鳩の巣原理から、4*n2個の点を4種類に分けるので、どれか1種類は少なくともn2個以上の点が属するので、そのグループの点からn2個選べば良い(submission)。

6/5

6/6

6/7

左右に速度差が無いときは直進し、速度差があるときはある点を中心とした円軌道を描くように動く。その中心点は、速度の正負が同じ時はその速度比の外分点になり、異なるときは内分点を中心とした回転になる。外分点の求め方とか、ある点を中心にしたときの回転とか調べながら実装したけど、これはcomplexのおかげでシンプルにかけるので知っておけてよかった(submission)。

奇閉路がないということは、グラフが二部であるということと同値なので、もともとのグラフが二部グラフでなければ-1になる。もし二部になっていれば、二部のそれぞれの頂点の個数ができるだけバランス良くなるように配置することで二部グラフに生やせる辺の個数はより多くすることができるので、バランスよく配置することを考える。連結成分ごとに、左右の差がどれくらいあるかをまず数えておく。そして、それを普通にdpしようとするとO(N^2)になってしまうので、改善を考えると、差が大きいものは個数が少ないということに注目して、差の大きさが\sqrt{N}より大きい方と小さい方でそれぞれ別のdpを考える。大きい方は個数が少ないので、1個ずつ分配していく普通のdpをして、小さい方は種類数が\sqrt{N}で抑えられていることを考慮して、個数制限つきナップサック問題っぽいdpをする。最後にその2つの結果を合わせて、一番バランスのいい場所を探す(submission)。

6/8

6/9

線を引く場所はO(n)通りあるのでそれを全部試す。そのために、毎回凸包を取って面積を計算しているのでは遅いので、上側凸包と下側凸包を途中まで作りながらその都度面積を計算していく。それを左側と右側についてやっておく。これだけ見ると考察はシンプルだが、実装にめちゃくちゃ時間かけてしまった...(submission)。

最終的にa個とb個の連結成分に分かれるとき、張れる辺の数は V(V-1)/2 - E - ab となる。この辺の数をTaroは奇数にしたくて、Hanakoは偶数にしたい。つまり、abの偶奇が重要になってくるので、連結成分の大きさが偶数のものと奇数のものがそれぞれいくつあるかを持って探索する(submission)。

ゲームのルール的に、スタックには交互にA,Bのカードが積まれることがわかるので、スタックの一番下にあるカードと、デッキの一番上にあるカードのindexがわかっていればスタック内の状態がどうなっているかを復元することができるので、あとは各プレイヤーがカードを出す/パスをするの2択のどちらがいいかをDFSによって探索する。状態がO(n^4)、パスしたときのスタックの復元にO(n)かかるので、全体としてはO(n^5)で計算できる(submission)。

長方形区間に対して、Grundy数を再帰的にDPで計算する。状態数と遷移を考慮すると、計算量はO( (HW)^3)になる(submission)。

6/10

2016-2017 ACM-ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred) Virtual

ペアごとに、発表する順序によって何回入れ替わりが起こるかを考えると、まず、得る得点dの正負が違うときは、区間がクロスしていれば順序に関係なく1回の入れ替わりが起きる。正負の向きが同じ時は、どちらかがもう片方を内包するときは順序に関係なく1回の入れ替わりが起き、平行移動して被る感じになってるときは適切に選べば最大で2回の入れ替わりを発生させることができる。この適切に選ぶというのは、全体で見るとすべてのペアに対して起こすようにできるので(DAGっぽい順番でやればいい)、これらの和が答えになる(submission)。

6/11

答えを二分探索する。OKかどうかの判定はシミュレーションによって求める。この判定だが、1日のどこかのタイミングでタンクが満タンになってれば良いが、それは2日ぶんシミュレーションして、2日連続で満タンになるタイミングがあればOKとなる(2日チェックすれば、それ以降もそこを基準にして1日を回せるはず)。途中で空にならないように注意(submission)。

すべての周期のLCMを取って、それについて考えれば最大値が求めるが、すべての周期のLCMを取るのは厳しい。そこで、半分全列挙っぽいことを考え、互いに素な2つのグループに分ければ、それぞれの部分での最大値を見つけて足すことで元の問題に対する答えとすることができる。ということで、いい感じに互いに素な2つのグループに分けたい。というわけで、2を含みうる素因数と、そうでない素因数に分けることにする(具体的には、13,17,19,23だけ別にする)。そうすると、各グループごとにLCMは100000以下で抑えられるので、1周期すべてをチェックすることができ、答えが得られる(submission)。

Codeforces Round #487 (Div. 2)

久々に出た。B落とすとかひどすぎる、、

6/12

各nameについて、1回の操作で得られる文字列を列挙しておく(だいたい1000通り)。そうすると、2回での操作で到達可能という判定は、この中のいずれかの中間生成物を介して生成されるはずなので、mapやsetなどを使ってチェックすることができる(submission)。

はじめ、DFSで更新しようと思ったが、閉路に対処しきれないので、ベルマンフォードっぽく更新していくことにした。dp[i]=魔女iを作るために必要なグリーフシードの数の最小値とすると、あるルールによって魔女iを作るために必要な個数の最小値は、その元となる魔女のdp値を参照して、それが大きい方から順に作っていき(作ったものをキープしておく必要があるので)、その中での最大値をdp更新の対象とする(submission)。

6/13

まず、ルールを有向グラフの関係で表す。その関係が得られたら、各頂点ペアについて、同水準かどうかを判定するのは、O(|V|)でできるので、全体でO(|V|^3)でできる。その判定できた部分に対して有効辺を張って、Warshall-Floydすることで2つが同等以上の関係かどうかが分かる(submission)。

構文規則から、>が括弧のやつか、シフトであるかどうかは実は簡単に分かる。(数字や、Sの直前にある>>は、シフトで確定する)。それが分かってしまえば、空白は邪魔でしかないので空白を全部詰めてから、構文解析をしていく。制約的に、O(|S|)でやることが要求されている(ように見える)ので、気をつけて実装する。exprを評価するとき、どの>>を採用するかだが、同じ深さにある今注目する区間の中での一番右のを採用すると良い。その際に一番右を判定するための引数が実装のRRという変数になっている(submission)。

星は5本の線分で定義されるので、星同士の距離は線分と線分の距離のminによって計算できる。あとはWarshall-Floydしておわり(submission)。

構文解析をして、木を構成してからマージする解を書いたが、超久しぶりにポインタによる二分木の実装をかいたら無限にバグらせた(ポインタができなさすぎる)(submission)。

まず、グリッドから木構造を得て、あとは、各ブロックについて、部分木全体に対して重心を求めて、条件判定をする(submission)。

6/14

平行移動させる方向が9通りで、深さ3のDFSをバックトラックしながらシミュレーションすれば良い。ただただ実装を頑張る(submission)。

バネに乗ったときの期待値をxと固定すると、各マスからゴールまでの期待値をBFSで計算することができる。すると、その結果から実際にバネに乗ったときの期待値yが計算できる。それとの大小関係を見ることで、xを二分探索することができ、本当にバネに乗ったときの期待値を求めることができる。最後にその期待値を利用して再度計算し、答えを求める。精度がdoubleだと足りないのでlong doubleで実装した(submission)。

6/15

ルールがいろいろあってとにかく読むのがめんどくさい。ただ、大筋の流れとしては、まずモーラ単位で入力されたstringをsplitし、各モーラに対して母音を含む場合にそれが無声化されるかをチェックする。ただし、母音が連続して無声化されることがないので、前の母音が無声化されたかどうかのフラグを持っておく(submission)。