naoya_t@hatenablog

いわゆるチラシノウラであります

AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019

1/12(土) 21:00-23:00
3完357位…Cで適当に投げて2ペナ食らったのが痛い
パフォ1777でレート微増(1702→1710)

A - Bulletin Board (100)

はい
→AC
https://atcoder.jp/contests/aising2019/submissions/3983521

C - Alternating Path (300)

UnionFindでくっつけて
各黒から同じ島に白がいくつあるか見て足して、
→TLE
おいO(N^4)ループ
同じ島の黒と白の数を掛け合わせて
→WA
掛け合わせてってintじゃ足りない。long longで
→AC
https://atcoder.jp/contests/aising2019/submissions/3986752
カジュアルに投げすぎるの良くなかった

D - Nearest Card Game (500)

大きい方からn個は高橋くん、その次のn個は青木くん、あとは高橋青木高橋青木…になるのかな
nを求めるのに二分探索を二重に回して
間に合わず
→終了55秒後に投げたやつはTLE+WA2
ローカルで最悪ケースを作って試したら15秒以上かかる

ちょっと書き直してみる

「青木くんが位置xから近い順にn個取るときどこからどこまでになるか」を考えていたのだけれど、
「高橋くんにとっての(=大きい方から)n番目が、青木くんにとっての(位置xから近い順に)何番目にあるか」を考えて、青木くんが取れる位置がどこまでかを二分探索で求めてみる。

「高橋くんのn番目」は座標が分かっている(a[N-n])ので、それが位置xから近い順に何番目に該当するかは比較的容易に求まる。(xを中心に点対称の位置に数があればそこから、なければupper_bound()か何かで求めた位置から「高橋くんのn番目」までに幾つ数があるか (inclusive) がその値で、与えられたx,nに対し高々O(\log N)で求まる。
高橋くんに先取されないぎりぎりのラインを二分探索で求めることでO(Q(\log N)^2)でこの問題を解くことができました。
→AC
https://atcoder.jp/contests/aising2019/submissions/3996550
実装力というより、筋の良い考え方ができるかが鍵だった気がする。

解説読んだ

同じことしてる

E - Attack to a Tree (600)

見てない