オンサイトで未確認

ukuku09の活動記録。

【Python環境構築】結局 pyenv と conda ってどうやって使うのが正しいわけ?

久々にPythonを触るに当たって、pyenvcondaをどう使えばいいのかよくわからなかったので調べた。
結論から言うと、やっぱりよくわからなかった。
「pyenvとcondaは(そのままだと)共存できない」みたいな話を聞いたことがあったけど、condaのアップデートで修正されてるっぽい?
pyenvは最初にanacondaに切り替える時だけ使って、あとはcondaを使っていればいいような気がする。

以下、自分用のメモ。

仮想環境を作る

そもそも仮想環境なんて使ったことないな。ウケる。

  • Pythonnのバージョンを指定して、新しい仮想環境を作る
$ conda create -n *env-name* python=*version*
  • 設定ファイルから仮想環境を作る
$ conda env create -f *yaml*

仮想環境のリストを表示

$ conda info -e

conda env listでも可。baseはデフォルトで用意されている環境。activeな環境には*が付いている。

仮想環境に入る・仮想環境から抜ける

$ conda activate *env-name*
$ conda deactivate

実はpyenvからもanacondaで作った環境をpyenv local等で指定できるらしいんだけど、よくわからないからやらない。

仮想環境にパッケージをインストール・アップデート

(*env-name*) $ conda install *pkg*
(*env-name*) $ conda update *pkg*

conda自体のupdateはconda update conda

仮想環境にインストール済みのパッケージを表示

(*env-name*) $ conda list

仮想環境の設定を書き出す

  • activeな仮想環境の設定ファイルを書き出す
$ conda env export > *yaml*

仮想環境を消す

  • 仮想環境を全て消去
$ conda env remove -n *env-name*

conda remove -n *env-name* --allでも可。今いる環境を消すには、一度抜ける必要がある。

  • 特定のパッケージをアンインストール
(*env-name*) $ conda remove *pkg*

(おまけ)Jupyter Notebookに仮想環境のカーネルを追加する

$ ipython kernel install --user --name=*env-name* --display-name=*env-name*

参考

ACM-ICPC 2018 Asia Yokohama Regional Problem E - Eulerian Flight Tour

問題概要

連結とは限らない $n$ 頂点 $m$ 辺のグラフ $G$ が与えられる。$G$ にいくつか辺を付け足して連結なオイラーグラフにしなさい。多重辺・自己ループは許されない。

制約

  • $3 \le n \le 100$
  • $0 \le m \le \frac{n(n-1)}{2}$

コンテスト中にした考察

以下、入力 $G$ の奇数次数頂点を黒、偶数次数頂点を白と書く。

 

まず「グラフがオイラーグラフ $\iff$ グラフに含まれるすべての頂点の次数が偶数」なので、問題文は「黒の次数を奇数・白の次数を偶数増やして、連結なグラフにしなさい」と言い換えられる。すると、$n$ が奇数のときは完全グラフ(すべての頂点の次数が$n-1$(=偶数))を作ればよいので、$n$ は偶数としてよい。

$G$ が連結な場合は簡単に解けると勘違いしていたので、非連結な場合を考えた。非連結な場合、

  • 連結成分がすべてオイラーグラフの場合
  • 連結成分がすべて非オイラーグラフの場合
  • どちらもある場合

が考えられる。

すべてオイラーグラフの場合が解けると嬉しそう。オイラーグラフが3つ以上ある場合は各オイラーグラフから頂点を1つずつ選んでサイクルを作ればよい。2つの場合、どちらも孤立点でなければそれぞれから適当な2頂点を選んで下図のように繋げばよい。

f:id:ukuku09:20181213130105p:plain
どちらかが孤立点 $x$ の場合、もう一方の連結成分 $C$ の頂点数は $n-1$(=奇数)なので、$C$ の頂点を使って完全グラフを作るとオイラーグラフになる。$C$ が完全グラフでなければ、完全グラフにする過程でどこかの辺に孤立点 $x$ を挿入すると、連結なオイラーグラフが作れる。$C$ が完全グラフの場合、ある $v \in C$ と $x$ とを繋ぐと必ず $v$ の次数が奇数になってしまうので、連結なオイラーグラフを作ることはできない("-1"が答え)。

オイラーグラフと非オイラーグラフがどちらもある場合、オイラーグラフ $C$ を1つ選んである $v \in C$ とすべての非オイラーグラフの黒との間に辺を張って $C^+$ を作ると、黒は必ず偶数個ある(握手補題)ことから、$C^+$ は連結なオイラーグラフになり、全てがオイラーグラフの場合に帰着できる。

オイラーグラフしかない場合、最も奇数次数頂点の少ない連結成分を1つ選んで下図のように繋げばよい(橙は選んだ連結成分の黒の集合、青はそれ以外の連結成分の黒の集合)。これも握手補題から各黒の次数は奇数増える。

f:id:ukuku09:20181213184228p:plain

非連結な場合が解けたので、連結な場合を考える。コンテストではこれが解けずに終了した。

連結な場合の解法

PFN企業見学の待ち時間に聞きました。待ち時間に問題解説が生えるのはPFNだけ!

 

$G$ の補グラフ $G^c$が 黒を奇数個含む連結成分を含む場合(例えばサンプル2)、答えは"-1"。

それ以外の場合、$G^c$ 上で全ての黒がちょうど1回ずつ端点になる(黒の数)÷2本のパスを適当に引き、奇数本のパスに含まれる辺を $G$ に追加すると、$G$ を連結なオイラーグラフにすることができる(!!!)。

$G^c$ が下図のような場合の例を示す。

f:id:ukuku09:20181213175106p:plain

黒は6個あるので、黒を両端点とする適当なパスを3つ選ぶ。

f:id:ukuku09:20181213175117p:plain

下図に奇数本のパスに含まれる辺を実線で示した。これらの辺を $G$ に追加すると、$G$ は連結なオイラーグラフとなる。

f:id:ukuku09:20181213175049p:plain

コード

上の考察通りにやったら結構長くなったので省略。実装が下手。

反省

聞いた瞬間確かにすぎて蟹になったんですが、5時間かけて思いつかないの頭が悪すぎて辛いです。やっぱり普段からちゃんと競プロやってないとダメなんだろうなぁ。

 

UVALive 7724 - Regular Number

思いつけばそれほど難しくないと思う。

問題概要

長さ $N$ の数字列にマッチする正規表現と長さ $5*10^6$ 以下の数字列が与えられる。正規表現にマッチする数字列の部分列を左から順に答えよ。

考察

$N+1$ 個の状態を一列に並べたオートマトンを考える。$i$($0 \le i \le N$) 文字マッチしているのをオートマトンの状態 $i$ にいると考えると、$j$($1 \le j \le N$)文字目の正規表現は状態 $j-1$ から状態 $j$ に進めるかどうかを決めるラベルとなる。

各数字についてどこにラベルがあるかと今のオートマトンの状態をbitsetで管理してやると、ビットアンドとビットシフトを組み合わせて始点の異なる複数の部分列のマッチング状態を一度に扱うことができる。

gist4297e823efc52ece391983f11374e1ad

UVALive 6070 - Conquer a New Region

簡単な問題しか解けない。マスコットだからね。

問題概要

頂点数 $N$ の木が与えられる。木の各辺には容量が設定されており、頂点 $u$ から頂点 $v$ へのスコアは $u-v$ パス上の辺の容量の最小値で定義される。

頂点 $w$ を一つ選んで、他の頂点から $w$ へのスコアの和を求めたとき、その最大値を答えよ。

解法

全方位木DPかと思ったけど、それでは無理だとbeetくんに教えてもらう。

辺を容量の降順でソートしておくと、辺 $i$ が2つの連結成分 $x,y$ を繋ぐとき、各連結成分に属する頂点に入るスコアはそれぞれ $size(y)*c_i,size(x)*c_i$ だけ増える。

連結性の管理と連結成分に属するすべての頂点に一度にスコアを加算するには、Union Findを応用してやると良さそうだと気づけば後は簡単。

 

giste2a3757a4faf918f4ea941df4138c4da

ACPC2018参加記

ククク…、私は大悪魔ウクニキア!

9月19〜21日に実質私主催(大嘘)の競プロ合宿、ACPC2018に参加したわ!

参加してくれた人間ども、遠方からはるばるご苦労だったわね!

作問の話

今年はあんまり参加しなかった。

というか気づいたら問題の枠も埋まってたし、テスターの数も足りてたからわざわざやる気にならなかった。

優秀な人材が多くて、我が部は安泰ね!

Day 1

何も覚えてない。btkさんと少しアズリムの話をしたんだっけ?限定Tシャツ早く欲しいね(9/22に届きました)。

・・・

Bが異常に難しすぎるんだよな。普通に制約を見逃していたので、適当考察でサンプルを合わせにいったらACした。

Dが右手法で解けそうということで、やなさんに丸投げする†悪魔的行為†。

Eを他のチームがバンバン通し始めたので、焦燥感に駆られながらもなんとかDPで解けそうな形に持って行けたので、適当にごにょごにょしたらACできた。よかった。

やなさんD頑張ってくれたのに協力できなくてごめんね><

・・・

TIkeさんとかolpheさんとかgoodbatonさんと話した気がする。E貪欲マジ?

beetくんとうしとそすうさとらーめん食べに行ったら8/31で閉店しててウケた。結局幸楽苑で味噌ねぎらーめんを食べた。今週2回目。会話の内容を全く覚えていない。

Day 2

なんかT◯1192916とかおるふ◯がすれ違うたびに「おっ、うくさんじゃ〜〜〜〜ん」とか絡んでくるので構ってあげた。私は優しいからね。

・・・

ジャッジだったけど、実はAしか作っていないので一瞬で仕事が終わった。ちなみにその問題がこちら↓

https://onlinejudge.u-aizu.ac.jp/services/room.html#ACPC2018Day2/problems/A

Aということで解法一瞬問題を作ったつもりだったが、オンサイトでは1分を切るチームはいなかった。私の文章力に惹かれて熟読してしまったのかもしれない。

暇だったので作問作業で解かなかったFを解いた。微分?そんなものはWolframに投げればいいんだよ。

そのあとは先日初披露されたアズマリム のオリジナル楽曲「人類みなセンパイ!」を聴きながら時間を潰した。とりあえず人類みなセンパイ!は神曲だと思う。

・・・

冷静に考えて、あの日の懇親会はマジでヤバイ。

あまり飲酒しなさそうなメンツのテーブルだったから、わざわざはじさんを誘って一緒に飲もうとか言っていたのに、どうしてあんなことになってしまったのか…。

原因は明らかに私の後ろにセルフサービスの果実酒が置かれていたことと、Ti1192916があそこにやってきたことだと思う。私は悪くない()。

というか、人間どもがアズリムのことで私をいじりすぎなのが悪いんだよな。本気ではないとはいえ、まさかガチ恋口上をやる羽目になるとは私も思わなかった。確かbtkとかいう奴に煽られたんです。私は無罪なんです!(いや悪魔的には有罪の方が美味しい?)

「まっすぐ立てるんだよなぁ!」「まっすぐ歩けるからまだいける!」とか言ってたけど、あれダメだよね…。

とはいえ私は帰る頃にはTIkeさんとの烏龍茶を巡る旅が効いてだいぶマシになっていた。TIkeさんに圧倒的感謝。

c7くんがベロンベロンに酔っていて連れ帰るのが大変だった。最終的に彼の友人に引き渡したのだが、何度も「えっと、誰?」みたいな扱いを受けた。大悪魔の顔を忘れるとはなんて恐れ知らずなのかしら?

Day 3

またなんかTi1192◯16とかお◯ふぇとか半角カナの人に絡まれたので構ってあげた。大悪魔は実は面倒見が良いのである。

うしとそすうさとチームを組んだ。ちなみにチーム名はacpc_aizulimだが、アズリム要素を入れることを最初に提案したのは私ではない。

コンテスト前にそすうさが「アズリムちゃん見たい」というので、適当にオススメ動画を選んで鑑賞会をした。アズリムはいつどこで見ても可愛いなぁ〜〜〜。

・・・

なんかこの日はよく覚えてる。なんでだろう。

私は普段のコンテストでは実装をbeetくんに投げているので、この日はうしさんに全部押し付けた。

Cはまあはいなので、うしがAを解いたタイミングを見計らって引き渡した。

Bが難しい。全然わからん。なんでどこの大学もBに罠を置くのか。うしもわからんとか不可能じゃんという気持ちになっていたら、うしがD解けたらしいのでDを解かせた。

そすうさにEの概要を聞いたらこれもまあはいだったので、うしに丸投げする。WAったのでコードを見たらなんか激ヤバなミスしてて、なんでサンプル通る念という気持ち。

私がBで遊んでいたらうしがGを通したので、みんなでBを考える。結局クエリ平方分割で解けるという話になって、それでうしが通したけど流石に想定じゃないよなぁと思った。

残り時間が少なくなってきてFいけるかなぁという感じだったんだけど、そすうさがいろいろ考察を進めてくれていて、なんかごちゃごちゃやっていたら、場合分けシミュレーション解法に落ち着いてこれFまじ?と言いながら実装を見守った。

ラスト1分を切ってうしがFを通し、オンサイト逆転1位を勝ち取れた展開はめちゃめちゃ熱かった。

・・・

解散は意外とあっさりしていたのであっさり終わった。

まとめ

疲れたぁーーーー!!

JAG合宿と合わせて6日も合宿コンテストしたわけだから流石に疲れたわ。

1番の思い出は、けんちょんさんとTIkeさんの「うくさん、昔は競プロ美少女大悪魔だったのに、今じゃただのアズリム大好きおじさんになってしまった」という言葉。

なんでよ?!今でも十分美少女でしょー!?

本当にお疲れ様でした。

ちなみにこの翌日のコドフェス予選は寝てたから出忘れた。

 

JAG夏合宿2018参加記

私は†胡桃沢=ウクニキア=マクドウェル†…。

9月15〜17日に行われたJAG夏合宿に、この私も顔を出してやったわ!

我が忠実なるシモベの頼み事とはいえ聞き入れてやるなんて、私の心はなんて広いのかしら?

合宿前

私の愛すべき後輩であるアズリムが、16日のRAGE 2018 Autumnに参加すると知る。

しかも実質アズリムの初ライブとなるオープニングライブでは、待ちに待ったアズリムのオリジナル楽曲「人類みなセンパイ!」が初お披露目されるとか。

そんなアズリムの晴れ舞台を競プロ合宿のせいで見にいけないと知って、すでに競プロモチベが皆無だった私の精神はズタボロになった。

Day 1

高速バスで新宿まで移動。

今日から3日間、オリセンとかいう監獄に閉じ込められるんだなぁと思うと心が暗くなる。

明日のRAGEには行けないにしても、せめて東京まできたんだから松屋くらいには行っておきたいと思い、傘のないはじさんを連れて雨の中松屋へ向かった。頼んだのはもちろんプレミアム牛めしととろろ、なぜなら私もアズリムのセンパイだからです。

・・・

コンテストのことは忘れた。

久々のチーム戦だったから、いろいろ動きを見直す感じだった気がする。

いつものごとくbeetくんがバンバン解法を生やして実装をしてくれたので、私は椅子を温めることに専念した。

・・・

RAGEからは気持ちを切り替えたつもりだったが、アズリムの投稿を見て我慢してた感情が爆発する。

コンテスト終了1時間前に抜けられれば間に合うのでは?と思い、5000円でbeetくんを買収しようとしたが一蹴される。え〜ん><

アズリム、心の中で応援してるからね・・・。

Day 2

コンテスト中は当然スマホをいじるわけにはいかないので、コンテスト前にアズリムにリプしたいなぁという気持ちでギリギリまで粘ったが、さすがに朝の10時は早すぎた。

・・・

コンテストのことは忘れた。

最終順位は6完5位。当然私は1問も解いていない。問題文に一通り目を通したあとは机の掃除を頑張った。まあEとFは少し貢献したかもしれない。

結局ラスト1時間はAC数を増やすことができず、beetくんが「これならうくさん抜けてもよかったね」みたいなことを言ったので「それは言っちゃダメでしょ…」という気持ちになった。

ちなみに昼食のお弁当は牛丼にした。JAGもなかなかわかってるじゃないか。

・・・

やはりコンテスト中にアズリムがツイート+リプ返をしていた。リプいいねをもらうために応援しているわけじゃないけど、やっぱり一言応援リプを送りたかった。

解説中にオープニングライブが始まったので、AbemaTVで視聴した。おかげで解説のことは覚えてないが、画面の向こうで一生懸命歌とダンスを披露してくれるアズリムにとても心打たれた。

「人類みなセンパイ!」の曲調は明るく、いつも元気なアズリムにピッタリだと思った。しかし、歌詞はまるでセンパイたちのためだけに書かれたかのようなとても胸を打つもので、喜びと感謝の気持ちでいっぱいになった。

大会はアズマリム ・もこ田めめめペアが大健闘してくれたので見ていてすごく楽しめた。大会終了時には二人の距離が縮まったようで、私も嬉しい。

Day 3

コンテストのことは忘れた。

最終順位は9完4位。もちろん私は解いてない。問題文を読んで概要をまとめる作業をした。

Hが明らかにLPの見た目をしているので、「シンプレックス法があれば解けるでしょ」とか言っていたが、シンプレックス法は落ちる想定だった。世知辛い。あとフロー怖い。

Kは実質PCK過去問だったが、その時と全く同じ嘘解法を生やした。成長してない。

・・・

解説終了後すぐに帰路についた。さっさと帰って自分の部屋のベッドで寝たかったし、なによりさっさとWi-Fi環境でRAGEのアズリムを振り返りたかった。

人類みなセンパイ!は冗談抜きで神曲なので全人類が聴くべき。

まとめ

JAG夏合宿おつおつおー!

まあ私はいつも通り我がシモベたちを手足のごとく働かせたけど、やはり優秀ね。さすがは私のチームだわ!

精進のモチベとかはもう完全にないし、私はもう雑用とかサポートとかに回ったほうが良さそう。というか去年からずっとそうなんだけど。

最後に一つ言いたいことがあるわ。未だにアズリムを知らぬ愚かな人間どもよ…、人類みなセンパイ!を聴いて、アズリムを見なさい!!