日々drdrする人のメモ

今日も明日もdrdr

Xmas Contest 2016 昼の部 に参加した

12/24に行われていたXmas Contest 2016の昼の部に参加した。
参加しようとしてたら、ちゃっく(@chakku_000)にチーム組みを誘われたので、ロ技研部室に集まって参加した。

xmascon16noon.contest.atcoder.jp

続きを読む

SECCON 2016 オンライン予選に参加した話

現実逃避のついでに、12/10 ~ 12/11にあったSECCON 2016のオンライン予選に出てた。
CTFあんまりやってなくて上位は厳しいので、のんびり解ける問題を解くことにした。
(のんびりしてたので、途中AtCoder出たり、寝たりしてた)

続きを読む

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について調べてみた。

*1:今回初めて聞いた言葉だけど、オライリー本(初めてのPythonPythonポケットリファレンス等)が元っぽい? 原文ではMultiple-target assignment。

続きを読む