日々ｄｒｄｒする人のメモ

今日も明日もｄｒｄｒ

Pythonのマルチターゲット代入の評価順序

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

続きを読む

Deep Q-Network (DQN)について簡単に勉強してみた

MachineLearning Algorithm

機会があったので、少し気になってたDeep Q-Network (DQN)について数日で勉強してみた。
既にいろんなところでまとめられてN番煎じだけど、自分なりに整理するために強化学習やDQNについて簡単にまとめておく。

続きを読む

ACM-ICPC 2016 国内予選に出た話

ProCon ACM-ICPC

今回チームとして誘われて、ちゃっく君(@chakku_000)といしづ君(@ish_774)と一緒にICPCの国内予選に出ていた。結果は3完、97位だった。

ACM-ICPC 2016 Asia Tsukuba Regional | 国際大学対抗プログラミングコンテスト2016アジア地区つくば大会

続きを読む