WSLのpipenvの中のtkinterで作ったアプリで日本語入力
pipenvはあまり関係なさそう。
だいたい以下の記事で解決した。
astherier.com
自分用メモ
タイトルにあるようなキーワードで検索したが、記事が少し古めのものが多く(2023/10現在に対し2020,2021あたり、WSL2やWSLgが出る前後?)、今なら不要な設定もしている気がする。
おそらくだが、上記記事の最初のフォントの設定は不要。
自分の環境では、特に設定せずともゴシックとかのフォントが表示されていた。
確認コマンド
fc-list
ロケールの変更、Mozcのインストール、fcitx-config-gtk3での設定は必要そう。
ただ、fcitx-config-gtk3の入力メソッドの追加(+)で表示される中に日本語キーボードっぽいものがあったので、もしかしたらMozcも不要?
と思い試したが、Mozcを追加しないと日本語入力できなかったのでよくわからない。
形式的冪級数、ケイリーの公式、Prüfer コード
難しかったけど解説ACしたら何かわかったような気がしたのでメモ。
解法の考え方
N頂点ラベル付き木は、各要素が1~Nで長さN-2の配列に1対1対応させることができる。(Prüfer コード。これを使うと、N頂点ラベル付き木の個数が $N^{N-2}$ 個であることがわかる(ケイリーの公式)。)
上記方法で対応させた配列における、各数字の登場回数(の集合)が、元の木の次数-1(の集合)と対応する
逆に木の次数の集合${d_i}$を固定したとき、それに対応する木の種類数が、$\frac{(N-2)!}{\prod_{i} (d_i-1)!}$となる
次数の集合は、グラフが木であることから、総和が$2N-2$となる必要がある
次数の和の部分を仮の変数xに対する指数として考える。$\frac{x^{d_i}}{(d_i-1)!}$という項を掛け合わせると、係数(に定数$(N-2)!$をかけたりしたもの)が種類数、xの指数が次数の和、に対応する。
この掛け算の結果において、xの指数が2N-2になっていれば木の条件を満たす。
そこで、各s_iに対応する項を持つ関数 $f= \sum_{s\in S} \frac{x^{s}}{(s-1)!} $(母関数)を考えて、これを十分な数かけ合わせたのち、$x^{2N-2}$の係数を見てやることで答えがわかる。
元の式にある(N-2)!を忘れずに。
https://atcoder.jp/contests/abc303/submissions/44151410
マークダウンの数式の書き方忘れたので後で書く
(追記) 調べたら出たけど思ったより面倒だった。
最小カットは最大フロー
良く忘れるのでメモ(使わないとどっちが最小か忘れる)
使った問題(解説AC)
Submission #41137764 - Denso Create Programming Contest 2022(AtCoder Beginner Contest 239)
学んだこと
頂点のカット(頂点を消す、到達不可にする)は最小カットで考えにくいので、1頂点を入る/出る用の2頂点に分割して考える。
AtCoderLibraryでmf_graph.flow(start, goal)した後に、mf_graph.min_cut(start)をすると、最小カットした後の集合(start側の頂点がtrue)が得られる
min_cutは
”長さnのvectorを返す。i 番目の要素には、頂点 s から i へ残余グラフで到達可能なとき、またその時のみ true を返す。flow(s, t)をflow_limitなしでちょうど一回呼んだ後に呼ぶと、返り値は s, t 間のmincutに対応します。”
らしいけど、これでなんでmincutに対応するのかちゃんとわかってない(イメージ的にはわかる)ので、これも後で勉強。
ゲームの勝ち負けの問題
どうも苦手意識があるので、典型的な解法やテクニックをまとめることにする。
問題を解いたら適宜追加する。未来の自分、よろしく。
動的計画法
dp[盤面] = その盤面からスタートした時に勝つ/負ける
として、勝ち負けが自明な状態(決着がついたときとか)から、貰うDPで計算する感じ。
まねっこ
先に全部取ったら勝ち的なゲームで、後手が先手と同じ行動をとり続けることができれば、最後の1個を後手が取って勝つことができる。
という性質を使って場合分け的に解く感じ。
Nim
各山の個数のxorを取った値を使うと、その値の遷移が勝ち負け状態の遷移と対応している、というやつ。
(どうやって思いついたんだ…)
以下の性質から上手く機能することが何となくわかる。
・xorが0の状態からは正の状態にしか遷移できない
・xorが正の状態からは必ず0の状態に遷移できる
・すべての山が0のときはxorが0で負けの状態
Grandy数
ある盤面のGrandy数={その盤面から遷移できる盤面のGrandy数}に含まれない最小の非負整数
という値を考えると、これがNimのxorの値と同じように機能する。らしい。
問題例
・ F - Interval Game 2 / Submission #40164729 - AtCoder Beginner Contest 206(Sponsored by Panasonic)
オイラーツアー Euler Tour
部分木に対するクエリとかを効率的に行いたいときに便利。
ABC294Gで学んだ。
atcoder.jp
やり方
根からdfsしたときに、辺(あるいは頂点)を通った順に記録しておく。
ついでに問題に必要な情報も同じ順番で記録しておく。
こうすると任意の部分木について、その辺(頂点)ごとの情報が連続部分列となるため、セグ木(segment tree)などで効率的にクエリを実行できる。
オイラーツアーで検索すると、少なくない人が「辺について記録した方が良い」と言っていた。
直感的な良さは今のところわかっていないが、頭の良い人が言うならたぶんそうなので、慣れるまでこの形で使ってみる。
二乗の木DP
ABC_287_FでTLEしまくった学びをメモ
F - Components
このdpを
jがスパース(?)になりうるからmapのほうがお得やろ、って浅はかな考えにはまって惜しいことをした。
確かにvectorでできるならそのほうが速い、はず。
というか二乗の木DPを知らなかったのが良くないので、まだまだ学びが足りていない。。。
二乗の木DPはこちらに詳しく書かれている(後でちゃんと読む)
snuke.hatenablog.com