2018/4 solved(1)
4/1
dp[i] := iがsubsetの中で最大になるような適切な選び方は何通りあるかを計算する。このとき、文字列でソートされた順でiを処理していくと、i未満の部分のdpの和を取ることでdp[i]の値を得ることが出来るので、部分和を高速に取れるセグ木やBITなどを使ってこのdpを高速化出来る(submission)。
4/2
GCJ 2018 Practice Sessionに参加
今年からコード実行になったらしい。ルール的にはhackのないこどふぉに近いのか...?smallを確実に取りに行ってからlargeをやるとペナルティが付くのか？
位置と方向を決めると、そこにたどり着くまでコマンドを使う回数の最小値を計算する。なぜ最小値で良いかというと、向きが同じでそれ以上のものは、その場で実行するだけで辿りつけるからである(submission)。
4/3
4/4
各頂点について、その部分木が深さiの頂点をいくつもつかを上に持ち上げならDFSしたいが、陽に配列を持って処理しようとするとかかってしまう。そこで、適当なbaseとmodを複数用意して、この配列を多項式と見なしてローリングハッシュと同じ要領でこの配列をハッシュとして扱うと、上に持ち上げる時はbaseをかけて1をたすだけで上への伝播を完了できる。それを一通り求めたら、mapでそれぞれのハッシュ値が何回現れるかを数えればよい(submission)。
4/5
それぞれの人が知っているリストを作って、contributeが低い順にsalaryを決定していく。問題の条件を愚直に適用すると条件が個になって間に合わないが、小さい方から処理することで最低限のsalaryを更新していきながら更新できる。問題文をよく読んでなくて、この構成の仕方だと片方向しか満たせてないので、UFを使いながらもう片方の条件をみたすように合わせていく(具体的には、contibutionが同じで、条件に引っかかる時はどちらかのmaxに合わせないといけない)(submission)。
分離できる直線があったとして、それをがちゃがちゃ動かすとかならず黒い点1つと白い点1つを通るようにできるので、そのような2点を通る直線のみを考える。直線を弾いた時に複数の点が乗っているとめんどくさいが、ちょっとずらせば大丈夫かどうかは、直線上の点を順番に見ていった時に綺麗に2つに分かれていればちょっと回転すると分離直線を作ることが出来てOKとなる。幾何ライブラリを使おうと思ったが、誤差が怖いので、今回は自前で実装した(submission)。
4/6
4/7
各bitについて、0と分かっている/1と分かっている/どちらかわからないの3状態をもつのbitDPをする。この情報を基に、最悪の場合が最小になるような行動を選ぶので、次に聞く箇所を全探索し、その結果がどちらであったかのmaxを取るという遷移になっている。現段階の状態で、何個にまで絞り込めているかのcheckを、ビット演算子をつかって
かからないように実装した(submission)。
4/8
GCJ 2018 Qualificationに参加
全完してた。smallとlargeで本質的に違う問題を解かせる辺りに、GCJを感じた。本番の時はちゃんとサーバー動くようになってるといいが...
NWERC 2014 Virtual
8完だった。途中で実装詰まってなければもう1問狙えたかもしれない。
問題を言い換えると、四角い枠の中に個のbike stationがあり、枠の上にも無限個個のbike stationがあると見なしてよい。そうすると最適を考える上で取るべきルートは2点を直接結ぶ / 1点を選んで1回壁を経由 / 最初から最後まで だけで良い。また、反射の場所は、三分探索によって綺麗に見つけることが出来る(単なる反射ではないことに注意)。それを全方向に試せば良い(submission)。
4/9
4/10
差が1より大きい移動があれば、それが縦の移動であることが分かるので幅が確定する。まずその幅に矛盾が無いことを確認したら、もう一度最初から最後までの移動に矛盾が無いかをチェックする(幅を決定する段階では差が1の移動を無視したが、行をまたいで右端と左端の値になっている可能性があるため)。
sとtからそれぞれBFSで距離を求めておくと、新しい道(i,j)を1つ追加するとなった時に、新たな経路の長さは(sからiへの経路)+1+(jからtへの経路)となるのでそれが元の最短経路とり短くならないかをチェックすれば、最短経路を損なう道になるかどうかがチェックできる(submission)。
答えを二分探索することにすると、左から順番に何人配置すべきかが決まっていくので、その合計がkを超えるかどうかで可能かを判定する(submission)。
温度をTに保ったまま、(Tに近い方から順に)熱い水と冷たい水を同時に加えていくことを考えると、どちらかの水が尽きて、これ以上追加できない状態になる。ということは、追加する水の量は温度でソートした時にどちらかは使い切っているはずで、それに合わせてもう片方を調節しているというかたちになっているはずである。それがどっち側になるかは、仮に全部の水をフルで入れた時に温度がTより高いか低いかで判断できる。あとは、適切な位置を見つけて、その蛇口で出す量だけ二部グラフすれば良い(submission)。
4/11
4/12
2つの多角形で囲まれるサーキットを、最短で一周するのにかかる距離を求めるというシンプルな問題だが、かなり実装に気を使う。基本的には、外側を無視すると内側の多角形の凸包のルートが最短であるが、そのルートが外側の多角形の外を走るルートはダメなので、そこは、外側から凸包を押し戻すようなルートになることがイメージできる。すると、考えられる最短ルートは、内側と外側の多角形の頂点を結んでいくようなルートになり、かつ内側の凸包上の点は必ず通っている。この情報をもとに、内側の凸包上の点をチェックポイントにしながら一周していく。が、気をつけないと一周してくれずに逆走して一周した気になってゴールしてしまうので、ゴールラインを引いてそれをまたぐ線が引かないとか、counterclockwiseになるように辺をつくるとか、そういう注意が必要になってくる(submission)。
区間の開始時間になる時計を10個の中から決め打ちして、針の割り当て方が6通り、回転が60通りある。この開始時間で、他のそれぞれの時計に対して開始時間以上で最小の時間になる針の割り当て・回転を全探索で見つければよい。気をつけて実装するだけ(submission)。
訪れる順番はDFSの形なので、与えられるメモは正の値においてはDFS木上の辺を表し、負なら後退辺を表わしていることになる。各部屋からドアがいくつあるかが与えられるので、その部屋を訪れきるタイミングもチェックして今いる場所に注意しながらDFSを再現すればグラフを復元出来る(submission)。
4/13
基本的に鏡の位置でクロスするようなレーザーのルートは最適ではなくてもっと少ない枚数で実現できそうなのでそれは考慮しないことにして、(座標,向き,typePの使用枚数) = typeQの使用枚数のminを持ちながらBFSする。ただしスタートの向きが決まっているので、スタートを北側に通過するような光は作れないことに注意(submission)。
tの開始地点を全探索する。その固定された位置に対して、elementを組み合わせて一致させることができるかをbitDPによって計算する。ただ、そのbitDPの中で文字列の一致判定などをやると重いので、それを前処理にしてからbitDP内は簡潔にする(submission)。
球体の大きさも考慮に入れて、球体同士の距離を表す関数を作ると、中心感の距離パートも半径の元帥パートも単調増加なので、関数が凸であることが分かり、関数の最小値が見つかる。その最小値が負なら衝突するので、衝突するタイミングを求めておき、あとはそのタイミングが早い順に衝突を処理すればよい(submission)。
何回バウンドをさせるかを全探索する。そうすると、放物線が全て同じ形なので、打ち出す角度を二分探索で見つけることが出来る。物理の式の変形がめんどい(submission)。
4/14
dp[何回移動したか][使用したポーションのマスク]でbitDPをする。マスクの遷移については、小さい方から処理すれば次にどのポーションを使うかだけ考えれば良い(複数個を同時に使う場合でも順に伝播してくれる)(submission)。
dfsしながら、部分木を処理するのに必要なコストを帰ってくる必要があるときとない時のフラグをもちながら計算する。2乗が間に合うので、全方位木dpにしなくても各頂点を根にして試せば良い(submission)。
Helvetic Coding Contest 2018 online mirror
チームで参加。初めて2次元ロリハを書いた。
4/15
Bubble Cup 9 - Finals [Online Mirror] Virtual
週末バチャに人が少なかったので、適当に選んでチームでバチャしたけど面白かった。Bの解説があってなかったからTutorialのコメント欄見て復習したい。
segmentを移動しきれるかの判定を考えると、初め一直線に抜けることを考えると区間が全部1ならまずOKになる。そこから、折り返しを加えていくことを考えると、折り返しというのは隣り合う2要素にそれぞれ+1することに該当する。ということで、区間がOKかを判定したい場合には、区間を左から貪欲に1にしていって全部1にできるかを判定すればいい。このときに左から順に1にしていくことを考えると、必要な回数はが
回、
が
回、
が
回...というように交互に+と-が現れる形になっている。これらが区間内で負になってる箇所がなく、かつ
の位置の必要回数が0になっていることが判定の条件になる。あとはこの階差を交互に持つものをセグ木に乗せれば、判定クエリは処理できるので、区間addはこの階差のどこに実際に何が足されるのかを注意して足す場所に気をつける。indexの偶奇でセグ木を別に持つと区間addに落とし込める。かなりおもしろかった(submission)。
