Backtrack

CODE FESTIVAL 2017 qual C,F: Three Gluttons

https://code-festival-2017-qualc.contest.atcoder.jp/tasks/code_festival_2017_qualc_f解説と完全に同じことしたけどそれでも結構バグらせた。頑張って問題を変形していくと、解説の2つめの四角で囲ってあるような問題に落とし込めます。 ここからが難し…

SRM 641

https://community.topcoder.com/stat?c=round_overview&er=5&rd=16084Easy 原点と2つの頂点がつくる角度a,b,cについて、 a+b+c=2*π,a よって2つ頂点を決めれば最後の頂点は2*π-a-b 本当はx軸からの角度でsortして解くのが正しくて、そうすればO(N^2)になり…

AGC017C: Snuke and Spells

http://agc017.contest.atcoder.jp/tasks/agc017_c解説を見るとこんなうまいやり方があったのかぁ…となるんですが、それをどうやって思いつけるようになるかが重要だと思います。 僕はこう考えたらしっくりきました。まず魔法をかける前、ボールがどうなって…

AtCoder Regular Contest 072E: Alice in linear land

http://arc072.contest.atcoder.jp/tasks/arc072_c類題解いていたのでイケた。 i回目から行動を始めてたどり着くことが出来なかった座標の集合を考えて、その集合のうち目的地からの距離が最も小さいものだけを持っておけばよい。 これは行動を逆から見るこ…

AtCoder Grand Contest 016E: Poor Turkeys

単調減少してから単調増加するPathがキーになることは分かったけど…ループがどうなるかよくわからなくなった。http://agc016.contest.atcoder.jp/tasks/agc016_eまずある一つの頂点xに注目する。操作を後ろから見て、i番目の人の操作が終わった際、何が生き…