コンテスト中に解けなかったけど、解説に載ってた解法以外で解けたのでメモ
D: Xor Sum - AtCoder Regular Contest 066 | AtCoder
続きを読む竸プロでPython使ってたら変なミスしたので書いた
ARC065のD問題 - "連結 / Connectivity"をコンテスト中解いてたときのミス
D: 連結 / Connectivity - AtCoder Regular Contest 065 | AtCoder
解法は数分読んだら方針ついたので、UnionFindを2つ使って実装して提出。
その結果WAくらった。サンプルケースだけ通っている状態(死)。
Submission #1018502 - AtCoder Regular Contest 065 | AtCoder
ぱっと見て実装何もミスってないし、何かケース見落としているのかなーって考えても思いつかなかった(実際解法としては合ってて見落としはなかった)ので諦めって感じだった。
その後、以下のように4行目を修正して提出したらACだった。
Submission #1022086 - AtCoder Regular Contest 065 | AtCoder
原因はマルチターゲット代入の式(root関数内の"x = parent[x] = root(parent[x])")の評価順序だった。
C++的な考え方で書いてたのがダメだった。
今回は、改めてマルチターゲット代入*1について調べてみた。
続きを読む12/3に行われたDDCC2016本戦の参加記です。
https://japan.discovery.com/ddcc/japan.discovery.com