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)。
