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しようとするとになってしまうので、改善を考えると、差が大きいものは個数が少ないということに注目して、差の大きさが
より大きい方と小さい方でそれぞれ別のdpを考える。大きい方は個数が少ないので、1個ずつ分配していく普通のdpをして、小さい方は種類数が
で抑えられていることを考慮して、個数制限つきナップサック問題っぽいdpをする。最後にその2つの結果を合わせて、一番バランスのいい場所を探す(submission)。
6/8
6/9
線を引く場所は通りあるのでそれを全部試す。そのために、毎回凸包を取って面積を計算しているのでは遅いので、上側凸包と下側凸包を途中まで作りながらその都度面積を計算していく。それを左側と右側についてやっておく。これだけ見ると考察はシンプルだが、実装にめちゃくちゃ時間かけてしまった...(submission)。
最終的にa個とb個の連結成分に分かれるとき、張れる辺の数は V(V-1)/2 - E - ab となる。この辺の数をTaroは奇数にしたくて、Hanakoは偶数にしたい。つまり、abの偶奇が重要になってくるので、連結成分の大きさが偶数のものと奇数のものがそれぞれいくつあるかを持って探索する(submission)。
ゲームのルール的に、スタックには交互にA,Bのカードが積まれることがわかるので、スタックの一番下にあるカードと、デッキの一番上にあるカードのindexがわかっていればスタック内の状態がどうなっているかを復元することができるので、あとは各プレイヤーがカードを出す/パスをするの2択のどちらがいいかをDFSによって探索する。状態が、パスしたときのスタックの復元に
かかるので、全体としては
で計算できる(submission)。
長方形区間に対して、Grundy数を再帰的にDPで計算する。状態数と遷移を考慮すると、計算量はになる(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
まず、ルールを有向グラフの関係で表す。その関係が得られたら、各頂点ペアについて、同水準かどうかを判定するのは、でできるので、全体で
でできる。その判定できた部分に対して有効辺を張って、Warshall-Floydすることで2つが同等以上の関係かどうかが分かる(submission)。
構文規則から、>が括弧のやつか、シフトであるかどうかは実は簡単に分かる。(数字や、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)。
2018/5 solved(2)
5/17
今3体がどこにいるかをkeyにしてBFS/DPをする。一見間に合わなさそうに見えるが、壁が多いのでなんだかんだ探索範囲は狭くなる。(submission)。
5/18
区間に対して、再帰的に計算を呼び出して結果を得ることにする。区間に演算子@がないときに返すべき値は自明で、点になる。演算子があるときは、どの演算子を呼ぶべきかということになるが、左結合なので、括弧でネストされていないものの中で一番右のものを採用すればよいことになる。ネストされていないものが無い時は、全体がネストされているので、左端と右端を1つずつ狭める。そして、その左側と右側について再帰的に計算する。途中で、その区間の結果がPointかLineかも保存しておき、それぞれの型にあった演算をする必要がある(submission)。
5/19
GCJ 2018 Round 2に参加
AbCでなんとかTシャツ獲得。Bも本当は解けたはずだった(WAだと思ったらMLEで、intをshortにしたら通った...)
5/20
SWERC 2016 Virtual
A通したかった...あと、Iは完全に読み落としで解けない問題になってた(けど、あの英文はダメでしょと思う(掃き出し法で解ける))。
5/21
幾何。原点からの距離だけ考えると、到達できる領域は1つの区間になる。それを順番に見ていって到達可能かチェックした後、可能なら目標の座標はそのままで、ムリな時はできるだけ近づけるような位置を目標に定める。そこから逆に辿っていって、アームの位置を復元する。位置は、円と円の交点を使って復元した(submission)。
5/22
問題文の設定がまどろっこしいが、噛み砕くと非終端記号がループしないので、全ての非終端記号の文法は終端記号のみで表すことができるようになる。そうすれば、あとは今何文字目で、それぞれの文字を何回使ったかを情報としてもつDPをすればよいことになる。ただ、よく考えると今何文字目かと言う情報はそれぞれの文字の情報から復元できるので必要ない。また、非終端記号を復元した時にめちゃくちゃ長くなってしまう可能性があり、MLEが発生しうるのでこのDPを計算し始める前にそれぞれの非終端記号が何文字になるかを前計算して答えが0になる場合は除いておく(submission)。
5/23
5/24
左上と右上を区間として持ち、区間DPっぽく処理していく。宝石を拾う時の遷移先は、制約から同じアルファベットがたかだか10個までしかないことが保証されているので、十分に速く動作する(submission)。
関係性を表したグラフについて、各頂点の次数が2以下であるという制約から、それぞれの連結成分の形状が一直線か輪っかのみに絞られるので、DPで(i個目まで決めた、j個採用した、直前を採用したか、最初を採用したか)という状態をもつことで各連結成分についてx個選ぶ時の最大値を計算できる。それを順番に連結成分をみながら、答えの方のDPをその都度更新していく。ひとつひとつやることは割とすぐ見えたが、実装はだいぶ時間かかった...(submission)。
5/25
違う記号には違う文字しか割り当てられないので、あまりにも文字の種類数が多いと破綻する。よって、文字の割り当て方を8!通り試してよい。-が演算子なのか、マイナスなのかの区別が難しいので、気をつける必要がある。(...*-10とか...+---101とかの-はマイナスと見なす必要がある。)このあたりの構文解析の分配の仕方に十分気をつける必要がある(submission)。
方針としては各モチベーションに何人いるかをSegtreeで情報を持ちながら、クエリを処理していく。新しく加わる時、その人が上から何番目になるかはその人よりモチベーションが高い人が何人いるかに等しいので、簡単に和を取ることで求められる。そうすると、新しく加わる人の状態が決まる。そして、その人の状態とクエリ前後での人数変化に応じて、既にいる人の誰かが働き始め/休み始める。そのときに、ちょうど上からx番目の人の名前を知りたいが、それはmotivationごとにpbdsでk番目にアクセスできるsetを用意しておくと簡単に実現できる。同様のことを削除の場合についても考えれば良い(submission)。
全探索+構文解析。()の中が数字だけになってしまうのを避けるために自分で1つ要素を定義すると構文解析をがしやすくなる。括弧の対応で構文解析がエラーしないように注意する(submission)。
5/26
5/27
2017-2018 ACM-ICPC Southeastern European Regional Programming Contest (SEERC 2017) Virtual
5/28
5/29
音楽がループすることを読み落としていて、はじめ違う問題を解いていた。12通りの調について、始めと終わりのループ部分について全通り試す。その間は、調を自由に変えながら1つの区間をできるだけ長くなるように貪欲する。そのための前計算として、i番目をスタート地点としたときにどこまで伸ばせるかを12*Nで計算しているのだが、Nが大きすぎてこれがこどふぉ上だとかなり厳しいTLになるので、頑張るしか無い(submission)。(そもそも107行の文字列を読ませる時点でいかれてる。)
コインを置くことができる場所は部分木の集合として表すことができ、それらはサイズによって管理すると、最適な置き方をする(できるだけコインのサイズに近い部分木で、自分よりも大きい部分木に置く)ということを考えると、部分木のサイズの区間で管理することができて、それらの区間が被るような置き方は発生しない。よって、setで区間を管理して、1つのコインに対して起きる操作は1つの区間を2つに分けることに等しくなるので、で計算できる。当時ミラーで解いたときもできたが、その時よりだいぶコードが綺麗にかけたので多少は成長を感じる(submission)。
立方体の連結関係をグラフで表すと、制約から1つの連結成分の形は直線か円形になることがわかる。グラフの辺には重み(その2つの立方体をつなぐ表面積)を付けておき、連結するk個を取ったときにどれくらい減少するかを計算してminをとる(submission)。
5/30
壁にぶつかるまでを毎回シミュレーションする。壁までの距離は少なくとも1はあるので、10000回でループは終了するはず。どのボールと最初にぶつかるかは、円と直線の交点を利用してスタートに一番近い点を選ぶsubmission。
棒の連結関係などをチェックすることで、2と5以外は簡単に区別することができる。2と5の判定だが、自分の実装は平行な3本の線を見つけ、切片でソート→対応する位置に棒があるかチェックして2か5を判別ということをやった。ただ2点を通る直線の式が間違っててバグらせまくった(反省)(submission)。
5/31
まず、面積からそれぞれの円の半径を決めることができる。その円同士がどれくらいの共通部分を持つかは中心間の距離に依存するので、できるだけ遠い位置に配置してそこから近づけたりする方針を取る。できるだけ遠ざけて置くのは長方形の対角線上(正確には円の大きさを考慮しないといけないので対角線ではないが)であるから、大きい方の円を左隅に固定して、そこから小さい方の円との距離を二分探索で動かしながら位置を見つける(submission)。
ひたすら実装。まず、針の間隔が等しくなるパターンが6種類あるので、それぞれについて満たすべき条件を手もとで計算する。それぞれについて有理数を使いながら答えを更新していく。やることはこれだけだけど、めっちゃ疲れた(submission)。
