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 コード

atcoder.jp

難しかったけど解説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

マークダウンの数式の書き方忘れたので後で書く

(追記) 調べたら出たけど思ったより面倒だった。

63rabbits.hatenablog.com

Qiitaの数式チートシート - Qiita

最小カットは最大フロー

良く忘れるのでメモ(使わないとどっちが最小か忘れる)

使った問題(解説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を> で書いていたらTLEして、
> で、dp[i][j] のjのループ回す範囲を上限(部分木の頂点数)超えないように適切に管理して書いたらACした。

jがスパース(?)になりうるからmapのほうがお得やろ、って浅はかな考えにはまって惜しいことをした。
確かにvectorでできるならそのほうが速い、はず。

というか二乗の木DPを知らなかったのが良くないので、まだまだ学びが足りていない。。。

二乗の木DPはこちらに詳しく書かれている(後でちゃんと読む)
snuke.hatenablog.com