Quiz https://atcoder.jp/contests/arc047/tasks/arc047_b Submit https://atcoder.jp/contests/arc047/submissions/4230646 Note editorialのように候補点4つを求める 最後にマンハッタン距離が等しいことを確認してprint 候補の4つともチェックは通ってい…

Quiz https://atcoder.jp/contests/arc045/tasks/arc045_c Submit https://atcoder.jp/contests/arc045/submissions/4227512 解法 任意の点からdfsしてxorを求めれば、xからyまで辿ったときのxor和はx -> root -> y から一瞬で求まる 任意の点からdfsしてxor…

Quiz https://atcoder.jp/contests/arc045/tasks/arc045_b Submit https://atcoder.jp/contests/arc045/submissions/4225127 Note Bにしては難しい？ 解き方はeditorialの通り 範囲の判定にフラグと累積和を使うのは汎用性がありそう その範囲を削っても大丈…

Quiz https://atcoder.jp/contests/arc042/tasks/arc042_b Submit https://atcoder.jp/contests/arc042/submissions/4201752 Note (追記：この記事には考慮漏れがあります） 各線分と点の距離を求めればいい 複素平面上で考える editorialの通り、c2 - c1か…

Quiz https://atcoder.jp/contests/arc040/tasks/arc040_b Submit https://atcoder.jp/contests/arc040/submissions/4193926 Other's Submit https://atcoder.jp/contests/arc040/submissions/3967511 Note 長々と書いてしまった うまく書けなかった時は通っ…

Quiz https://atcoder.jp/contests/arc034/tasks/arc034_3 Submit https://atcoder.jp/contests/arc034/submissions/4190481 解法 A! / B! を素因数分解して「指数部＋１」の積が答え 素因数分解したリストを返す関数を書いた やはりsqrtで打ち切らないとTLE

Quiz https://atcoder.jp/contests/arc031/tasks/arc031_3 Submit https://atcoder.jp/contests/arc031/submissions/4187330 解法 editorial参照 上記メモはSegment木だが、実際は実装が楽に済むBinary Indexed Tree (BIT) で解く 感想 BITはSegment木より対…

Quiz https://atcoder.jp/contests/arc025/tasks/arc025_3 Submit https://atcoder.jp/contests/arc025/submissions/4186238 解き方と計算量 ゴールを固定する ゴールから各ノードまでの距離をDijkstraで求める O( (N+M)logN ) 距離をソート O(NlogN) (a) 亀…

Quiz https://atcoder.jp/contests/arc025/tasks/arc025_2 Submit https://atcoder.jp/contests/arc025/submissions/4184320 Note どちらかの色の値を反転しておく 矩形和＝０なら濃度が同じ 二次元累積和で、矩形和をO(1)で求まるようにしておく 検索用ワー…

Quiz https://atcoder.jp/contests/qupc2018/tasks/qupc2018_e Submit https://atcoder.jp/contests/qupc2018/submissions/4183484 定義 入力A (配列) 累積和Ac (配列) 部分和が0になる個数 Za (配列) 解法 累積和を求める 累積和の中に同じ数が出現したら、…

Quiz https://atcoder.jp/contests/qupc2018/tasks/qupc2018_d Submit https://atcoder.jp/contests/qupc2018/submissions/4181446 Note 行きで出発したら一番速い便で帰ってくればいい 出発日と帰宅日の組を作ったら（下図ピンクの線）、もう都市の情報は忘…

Quiz https://atcoder.jp/contests/arc023/tasks/arc023_3 Submit https://atcoder.jp/contests/arc023/submissions/4174678 補足 いつものフェルマーの小定理と逆元 ・・・と思ったらnCrのnが109まである。階乗を求めるだけでもTLEになるだろう ポイントはr…

Quiz https://atcoder.jp/contests/arc022/tasks/arc022_3 Submit https://atcoder.jp/contests/arc022/submissions/4172969 補足 グラフ内の一番長いパスを求める（木の直径） それは「どこか１つの点から1番遠い点Vを求める」「Vから一番遠い点Wを求める」…

Quiz https://atcoder.jp/contests/arc030/tasks/arc030_1 Submit https://atcoder.jp/contests/arc030/submissions/4152101 補足 editorialとは別の解法で通ったので書いておく 頂点数 N-K になったとき、K個の連結成分ができている N-Kは少なくともK以上で…

Quiz https://atcoder.jp/contests/arc029/tasks/arc029_3 Submit https://atcoder.jp/contests/arc029/submissions/4151767 補足 editorialの通りに捉え直すことで最小全域木の問題となる クラスカル法を使うのは私は2回目かな。同じグループかどうかをUnio…

Quiz https://atcoder.jp/contests/arc028/tasks/arc028_3 Submit https://atcoder.jp/contests/arc028/submissions/4150128 補足 子供の数を葉の側から根に向けて求めていく たとえばノード1を消したとき、その子たちの連結数はそれぞれ求まる それらの和か…

https://codeforces.com/blog/entry/53457 いくつか解いてから実装する コンテキストスイッチには慣れている 潜在意識でより良い解が浮かぶこともある leaderboardに情報を流さないことを意図していない ただ、leaderboardで他者が短い時間で解いている問題…