2019/05 11-20日 日記

diary

11(土)
  • AOJ 1620 論理式圧縮機
    validな式を全列挙する．a,b,c,dの入力値は$2^4$通りあり，それぞれの結果は0,1の2通りである．
    これをキーにして，同じキーにおける式の長さの最小値を持てば良い．キーは$2^{16}$通りなので配列でOK.
    submission

全方位木DPが必要な問題に出会ったので，全方位木DPを覚えた．
通常の木DPでは根を決めてそれぞれの部分木についての問題を解いていた．
全方位木DPでは全ての頂点を根にして問題を解く．
ポイントは，根を隣接した頂点に移動させた際に考慮すべきは移動元に方向の部分木の値の変更のみ，という部分．
実装については逆元がなくても良いが，左側と右側からの半群を満たす累積Xみたいなのを持つ実装をしないといけない．少し面倒．(一般化可能だが全部の問題を解けるかは分からない)
そうでない場合は差分を計算するだけで良い．modがある時はできそうだがゼロ除算もあるので困る．
どちらでも実装できた方が良いと思う．
snukeさんの記事：次数の降順でみるとなんと$O(N)$でできる．
ei1333さんの記事(辺ベース：f1()は頂点と (頂点+辺) のマージ．
f2()は頂点とそこに生える辺のマージのことを示している．

12(日)

全方位木DPの練習をした．

  • EDPC V subtree
    根を黒く塗るとする． 下の頂点も全部黒の値であるとして持ち上げてくる． 更に下の頂点は白でも良いので，部分木の子からは(全部黒)+1すればよい．
    部分木どうしのマージは積． 逆元なしでいける加算のみの全方位木DPを書く．(書いた．) ところで最終的にほしい値だけのラッパーを書くと最適化されてメモリと実行時間がちょっと減る． 自分の他のsubmissionで最も効いた最適化は入出力…(は?)
    submission

  • AOJ GRL 5 A
    tree-treeはtop2のマージ． tree-edgeは足せばいいように思うが，top2それぞれに値を足すとtop2マージのときに嘘(存在しない辺を渡すこと)になるので，top2(a.first+e.cost, 0)とする．
    submission

  • AOJ 1596 Traffic Tree
    最遠点までの距離が知りたい． tree-treeはmaxをとる．
    tree-edgeは加算．
    submission

  • NJPC2017 E 限界集落
    最遠点までの距離と，反転されている辺の個数が知りたい．
    前者は既知とする．(上で解いた)
    辺の個数のtree-treeは加算．
    辺の個数のtree-edgeも加算．
    辺を張る際にrev=1とrev=0の辺を張るみたいにしてやれば良い．
    submission

  • S8PC 4 D Driving on a Tree
    そろそろ思うこととして，普通の木DPの演算だけ定義できれば良い．
    ある頂点を根としたときに，その子の数で期待値の和を割れば良い．
    tree-tree：期待値と子の個数を足すだけ．
    tree-edge：持ち上げるときに子の数は1としたい．持ち上げる際に期待値をつくる．つまりE/childs + 1.0(ただし0除算に注意)
    submission

もうちょっと重い問題じゃないとダメそう．

13(月)

  • ARC097 F Monochrome Cat
    葉を白だけにしても問題ない． 周回してくるコストは$2*(N-1) + \sum isW(v) \ xor \ isdegodd(v)$
    パスを選択してそこは往復しないとすると，$\sum isB(v) \ xor \ isdegodd(v)$ 減ると共に， $pathlen-\sum isW(v) \ xor \ isdegodd(v)$だけ増えることになる． これらは対等なので結局$2*isW(v) \ xor \ isdegodd(v)$のパスの値を最大化して取り除けば良い． これは頂点属性の木の直径なので実装をする．

  • 全方位木DP編 謎．なんかできた．たぶんどこかで間違っている．(直径だからなんとかなっている節がある)
    tree-tree：直径なのでtop2をマージ
    tree-edge：パスの長さなので+1．
    tree-v：頂点属性．最大値に+1か-1を加算する．この頂点のパスを消すと全体えの影響は±1となるため．
    全方位木DPをして，頂点にあるtop2のうち最大を引けば良い．(どうしてtop2+top1+costじゃないのか…)
    直径だから端に答えがあるはずでまあ良いのだろうか…
    結局0/2の頂点の最長パスなんですけどね．
    submission

14(火)
  • ARC 103 Distance Sums
    全方位必要なし
    距離が一番小さいは重心っぽそう．
    重さの昇順か降順で決めたい．
    葉から決めないと選び方がたくさんあるので葉からやる．つまり降順．
    今いる頂点の親を決めたくて，定義Dと同じdを準備して，隣接する頂点では$d(i) = d(j)+sub(j)-sub(i)$であるから， $d(j) = d(i) +2*sub(i)-N$．
    親がこの値なら良いので実際に作ればよい．
    最後に根(最小の値)が正しい値をもつかを確認すれば良い．
    隣接関係を見るみたいなのができるようになってきた気がする．
    submission
15(水)
16(木)
17(金)
18(土)

GCJ 2019 R2に参加．
競技プログラミングをせずにシャツを得た 何
去年の反省を活かして

  • smallは全部目を通す
  • インタラクティブはtesttool側をいじってデバッグしたりヒントを得る

というのを心がけた．

  • Pottery Lottery
    100⁄20 = 5枚よりも多い枚数が投票されるツボは答えになりにくいということがわかる．
    適当にいくつかのツボに5or6枚ぐらい入れてそのツボが答えにならないようにする．残ったツボのうち最小の枚数以外のツボを貪欲に増やせば90%は超える．
    全部のツボに100をいれると95%は超える．
    これいる?

  • New Elements: Part 2
    smallは与えられた組が昇順になる$(x, y)$が求まりさいすれば検証できる．
    雑な評価をすると200*200ぐらい見ればOK．(198らしい)
    largeは本番には解けなかった．結局したいのは隣接する関係から得られるx,yの一次不等式をみたす(x, y)があるかを判定したい． 格子点のうちxが最小のものを求めたい．
    なんか<|みたいな領域に含まれるものを探せばよく，Stern-Brocot木をみていくやつを書けば良い．(初めて書いた)
    どうして間に合うのかはよくわかっていない…

  • New Elements: Part1
    雑にプロットしすぎてsmallすら解けなかった．
    少し考えると(x, y)の組を決定する際にxとyの比だけが重要であることが分かる． 不等式をプロットし直すと与えられた点を順に通過する負の直線に対して順序はどれだけ存在するか？という問になるので負の直線の種類数+1が答え．
    赤/橙の人はこれの解説を「はい」としている人が多かったのでド典型っぽい．反省．

今年はラッキーパンチ感が否めなくて去年みたいなDP，フロー，全探索みたいなセットでもシャツをゲットできるようにしたい．
シャツ1000人に対して100人ぐらいの日本人が毎年シャツを得ているっぽい．日本人多いね．

19(日)
20(月)
Share Comments
̃Gg[͂ĂȃubN}[Nɒlj
comments powered by Disqus