ABC009 - D問題: 漸化式 (ビット行列解法)
ちょっと昔の話だけど書いとく。
今回はABC009のD問題: "漸化式" をビット行列として解いた話 (Python)
D: 漸化式 - AtCoder Beginner Contest 009 | AtCoder
続きを読むXmas Contest 2016 昼の部 に参加した
12/24に行われていたXmas Contest 2016の昼の部に参加した。
参加しようとしてたら、ちゃっく(@chakku_000)にチーム組みを誘われたので、ロ技研部室に集まって参加した。
xmascon16noon.contest.atcoder.jp
続きを読むPythonのマルチターゲット代入の評価順序
竸プロで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について調べてみた。
続きを読む