AtCoder Regular Contest

ARC064E 考えたこと 円がつながっている部分は，connected component にしてしまって良い．つながっている部分はコスト 0 で移動できるから． 次に，connected component 同士の距離を求めるが，これは connected component に入っている中心同士の距離から求まる． 結局，connected component を使ったところで，各 \(i, j \in N\) に対して中心 \(P_{i}, P{j}\) の距離を求めることになる， 逆に，各 \(i, j \in N\) に対して中心 \(P_{i}, P{j}\) の距離を求めていれば…

ARC045 問題概要 解法 Tree の Root を固定して 0 とする． コストは xor で考える． \(cost[a][b] = cost[0][a] \oplus cost[0][b]\) となるので，0 から DFS をして cost を求めれば十分． 答えの集計:個数を数えるとき， \(a \in N\) を全探索して \(b \in N\) であって \(cost[0][a] \oplus cost[0][b] = x\) となるものを探す． よって， \(|arccost_{c}|\) を求めておく． \(cost[0][a] \neq cost[0][b]\) のとき，\…

やりました atcoder.jp

atcoder.jp・参考 AtCoder Regular Contest 106 B – Values を解いた記録 – Manuel1024の引きこもルーム・説明 Union-Findを使って実装した。操作によって連結成分毎の合計は変わらないことので、もし変わっていればNoになる。 atcoderで新しく使えるようになったac-library-python/atcoder at master · not522/ac-library-python · GitHubを使って実装した。 from atcoder import dsu n,m=map(int,input().split()) a=…

まえがき 競技プログラミング振り返り三回目となります。 時間内には解けませんでしたが、なんとかA問のみ解けたので振り返ります。 A問(A - Echo) 問題はこちら→A - Ekiden Race復路が一番早い可能性がある人数を出力するものです。 問題文で説明されていない、3つ目のテストケースを用いて解説を行います。 往路 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 復路 往復 13 2 7 1 5 9 3 4 12 10 15 6 8 14 20 16 19 18 11 17 順位にを表に直すとこのようになります。 往路の順位と往復…

・問題： atcoder.jp・参考： Submission #16162979 - AtCoder Regular Contest 005 AtCoder ARC 005 C - 器物損壊！高橋君 (0-1 BFS) (水色) - けんちょんの競プロ精進記録・0-1BFS： 01-BFSのちょっと丁寧な解説 - ARMERIA・ダイクストラ法： グラフ理論⑤(ダイクストラのアルゴリズム) - YouTube・0-1BFSを使う。壁の有無で0，1を重さとしてBFSするものをいう。ダイクストラ法の重さが0，1になったもので、0のときはdequeの左から入れて1のときは右から入れる。こうすると0の…

ARC133C \(\equiv\)は\(mod\ K\)とする． 必要条件や，上限の見積もりを考える． 判定問題最大の前に，簡単のため判定問題を考える． 行列において掛かれた値の和は， 行方向と列方向それぞれで集計すれば， \(\sum_{i \in H} A_{i} \equiv \sum_{j \in W} B_{j}\) が分かるので，これが必要条件． これは十分条件でもある． 実際，左上の行列を\(0\)で埋めておいて， 一番下の行と一番右の列で帳尻を合わせることを考えると， 一意に決まる． 一番右下のマスの埋め方に問題がないことは， \(\sum_{i \in H} A_{i} \…