アルファベット文字列Sよりも辞書順で小さい回文のパターン数計算
今年に入って基本的なアルゴリズムの勉強としてatcoderのコンテストにチャレンジしている。勉強ついでのアウトプットとしてこちらの問題についてメモ。
https://atcoder.jp/contests/abc242/tasks/abc242_e
問題自体は、アルファベットのみの文字列Sに対し特定の文字列と比べて辞書順で小さい回文のパターン数を数えるというもの。解説はこちらに上がっている。
https://atcoder.jp/contests/abc242/editorial/3516
全体として考えるべきことは
- 文字列の中央の文字までを決めれば回文は一意に定まる
- 文字列Sと中央の文字までが一致している回文S'を比べて、S < S'であればその1パターンのみ差し引く
1.については回文なので当然そうなる。2.については以下のような話
- S = BCDCAの場合、S' = BCDCBであり、辞書順比較でS < S'となっているためS’は条件を満たさない
この場合、最初の3文字が辞書順でBCD以下である5文字の回文のパターン数をすべて数えて、最後に条件を満たさなかった1パターンのみ引けば求めたい答えとなる。
解説コードの中の22~26行目に実際にすべての回文のパターン数を計算する処理があり、最初見たときにすぐ理解できなかったため整理してみた。
int last=(n-1)/2;
for(int i=0;i<=last;i++){
cres*=26;
cres+=(s[i]-'A');
}
cres++;
ちなみに
- nは文字列の長さ
- cresは計算結果のパターン数
- cresは0で初期化済み
- (今回の話の本筋から外れるためmodの計算処理は削除してある)
上で出した例と同じでS = BCDCAだと仮定して考えてみる。 中央の文字までを考えればよいので辞書順でBCD以下の3文字の文字列の全パターンを計算すればよい。
| 0文字目 | 1文字目 | 2文字目 |
|---|---|---|
| A | [A-Z] | [A-Z] |
| B | A,B | [A-Z] |
| B | C | A,B,C,D |
- 最初がAなら1, 2文字目はどのアルファベットが来ても辞書順で小さいという条件は満たせる
- 最初がBの場合でも1文字目がA,Bのどちらかなら2文字目はなんでもOK
- BCと続いた場合は2文字目に取れるのはA~Dまでの4つのみ
という感じ。なので
cres = ('B' - 'A') * 26 * 26 + ('C' - 'A') * 26 + ('D' - 'A')
と計算できることになる。A~(n文字目までのアルファベット)までの数をa(n)とすると
cres = a(0) * 26^2 + a(1) * 26 + a(2)
= 26 * ( 26 * a(0) + a(1) ) + a(2)
となるため、ここで解説コードのforループの中身と上記のカッコの中身が対応していることがわかった。直前のループで計算されたカッコの中の値がcresとして保持されて次のループで使われるという形。
a(0)側から順に和を取ろうとすると指数の計算に無駄が出るので、a(n)を求めておいて後ろから順に和を取っていけば同じ計算量でできそう。
wslでのcuda toolkitのインストールでエラー
wsl上でcuda toolkitを入れたらnvidia-smiでエラーが出るようになったのでメモ
こちらで環境に合わせたインストールコマンドがわかる
CUDA Toolkit 11.1 Update 1 Downloads | NVIDIA Developer
入れる前に実行してあったnvidia-smiの結果
+-----------------------------------------------------------------------------+ | NVIDIA-SMI 470.57.01 Driver Version: 471.41 CUDA Version: 11.4 | |-------------------------------+----------------------+----------------------+ | GPU Name Persistence-M| Bus-Id Disp.A | Volatile Uncorr. ECC | | Fan Temp Perf Pwr:Usage/Cap| Memory-Usage | GPU-Util Compute M. | | | | MIG M. | |===============================+======================+======================| | 0 NVIDIA GeForce ... Off | 00000000:01:00.0 On | N/A | | 30% 33C P8 16W / 350W | 529MiB / 24576MiB | ERR! Default | | | | N/A | +-------------------------------+----------------------+----------------------+ +-----------------------------------------------------------------------------+ | Processes: | | GPU GI CI PID Type Process name GPU Memory | | ID ID Usage | |=============================================================================| | No running processes found | +-----------------------------------------------------------------------------+
この時点でGPU-Util部分がERR!となっているが、これはwsl上で実行するとこうなってしまう模様。nvidia側のupdateが必要とのこと。
cuda toolkitを入れた後
+-----------------------------------------------------------------------------+ | NVIDIA-SMI 510.39.01 Driver Version: 471.41 CUDA Version: 11.4 | |-------------------------------+----------------------+----------------------+ | GPU Name Persistence-M| Bus-Id Disp.A | Volatile Uncorr. ECC | | Fan Temp Perf Pwr:Usage/Cap| Memory-Usage | GPU-Util Compute M. | | | | MIG M. | |===============================+======================+======================| | 0 NVIDIA GeForce ... Off | 00000000:01:00.0 On | N/A | | 30% 35C P8 20W / 350W | Function Not Found | ERR! Default | | | | N/A | +-------------------------------+----------------------+----------------------+ +-----------------------------------------------------------------------------+ | Processes: | | GPU GI CI PID Type Process name GPU Memory | | ID ID Usage | |=============================================================================| | No running processes found | +-----------------------------------------------------------------------------+
Memory-UsageがFunction not foundという表示となっている。
インストールしたパッケージを調べていくと、cuda toolkitのインストール時にはwsl専用のコマンドを指定する必要があった。環境選択時にちゃんとwslという選択用のボタンもあったのだが見逃してubuntuを選択して出てきたコマンドを使ってしまった。
インストールされたパッケージの中にはdriverと書かれたものもあったので、ubuntu用のdriverも入ってしまったためにwindows側の正しいdriverにアクセスできなくなったのではと考えられる。
ということで入れたパッケージを調べてアンインストールしてみる。 /var/log/dpkg.logでインストールしたパッケージと時刻がわかるので上記でインストールされたnvidiaと書かれたパッケージをすべて削除する。
cat /var/log/dpkg.log | grep nvidia # 時刻を見て入ってしまったであろうパッケージを列挙 apt remove nvidia-prime libnvidia-compute-510 nvidia-modprobe libnvidia-common-510 nvidia-kernel-source-510 nvidia-utils-510 libnvidia-cfg1-510 libnvidia-fbc1-510 libnvidia-fbc1-510 nvidia-compute-utils-510 libnvidia-extra-510 libnvidia-decode-510 nvidia-kernel-common-510 libnvidia-encode-510 libnvidia-gl-510 xserver-xorg-video-nvidia-510 nvidia-dkms-510 nvidia-driver-510 nvidia-settings
削除後はnvidia-smiの出力がもとの状態に戻った。
ところで調べる中で以下の2つで表示されるcudaのversionが異なることが気になった。私がおかしいなものを入れてしまったせいなのかと思ったがどうやらそうではなかった。
nvidia-smiとnvccで表示されるCUDAバージョンが異なる件
nvidia-smiで表示されるものはdriverが対応しているcudaの最大versionを表しているとのこと。勉強になりました。
tmuxで保存したセッションを間違って上書きしてしまった場合
通常tmuxのwindowやpaneの内容はtmux serverをkillしてしまうと消えてしまう。そのためPCの再起動などかける場合は消えてしまうのだが、tmux-resurrectというプラグインを利用することでディスクに内容を保存しておいて復旧することができる。
さきほどPCを再起動してtmuxを起動してセッションを復旧させようとした際、間違って保存用のコマンドを実行してしまった。やってしまった、、と思ったのだが考えてみればディスクに履歴くらい残ってるのでは？と思いちょっと探ってみた簡単に元に戻せたのでメモしておく。
セッション保存の際に履歴が保存される場所
$ ls ~/.tmux/resurrect last ... tmux_resurrect_2022-02-18T21:52:05.txt
途中省略したがこのPCを使い始めた頃の日付のファイルもあったので保存したものがすべて残っている模様。
ちなみに中身は各windowやpaneの名前やカレントディレクトリ、サイズなどがざっと書いてあるだけでサイズはとても小さい。
lastというファイルがシンボリックリンクになっていて最新の日付のものを指していたので、以下のように一度消してから復旧したい日付のものに貼り直す。
$ cd ~/.tmux/resurrect $ rm last $ ln -s <復旧したい日付のtxt> last
これでもう一度セッション復旧を行うと無事上書き前の状態が復元できた。簡単。
