第一回 アルゴリズム実技検定

past.atcoder.jp

AtCoderが開催しているアルゴリズム実技検定 (PAST) というものがある。 今回はお金を払って検定として受けることはしなかったが、開催期間が終了し問題が公開されているので、少しずつ解いている。

atcoder.jp

やってみると解き方はわかって実装できたものの、WAやREに悩まされるパターンが何度かあり、詰まった部分について書いておく。

E - SNS のログ / Restore

「フォローフォロー」でユーザa自身を除くのを忘れて、WAの嵐に遭う。

H - まとめ売り / Bulk Selling

偶数と奇数に分けて管理する。 さらに「セット販売」と「全種類販売」については在庫を減らしていると計算量が大変なことになるので、別でカウントしておいて毎回在庫量から引いて計算するようにする。 あとは偶数と奇数の最小値をそれぞれ記録しておけば、各クエリで在庫が足りるかどうかを判断できる。 計算量はO(max(N, Q))となる。

自分は配列を0-originのまま実装してしまい、偶奇判定やカード番号と配列インデックスの変換でだいぶ辛いことになったので、この問題については0番目要素を追加してインデックスを揃えるのがいいのかも。

n = 1の場合については場合分けしておかないと、偶数のカード集合が空になってしまいREの原因になる。

所感

Iまで解いた感想としては、実装に迷うことがなくても細部の条件で弾かれることが多かった。 基本的なことだが、問題分をきちんと読まないといけないと再認識した。

ABC 149 E - Handshake

解説を読みながら実装してもなかなか苦戦したのでメモ。

解説はもちろん公式解説PDFと、このツイート、

そしてこのブログを参考にした。

emtubasa.hateblo.jp

3つ合わせることで、実装できるところまで理解できた。

どこで詰まったか

二分探索の範囲を間違えていた。 A_iの上限は105だが、A_i + A_jの上限は2 * 105なので、2*105の範囲で二分探索する必要がある。 105の範囲で二分探索していたのでWAが多発していた。

その他

WAを直すには、自分と同じケースでWAしている提出を見つけて、その人がどこを修正してACできたのかを見てみると、どこが間違っているか気づきやすいことがわかった。 ただ、そういう提出を探すには手動で一個一個見ていくしかないのが辛いところ。 そういうツールでもあれば良いんだけど… 欲しいなら自分で作れって話ですね

あとがき

年内にACできてよかった。 しかし、E問題はまだ難しい…

Firefox Developer Editionに未署名の自作アドオンをインストールする

初めての拡張機能 - Mozilla | MDNを参考にアドオン開発を試していた。

about:debuggingでの動作はできたのだが、xpi形式のインストールがうまく行かなかった。 Firefox のアドオン署名 | Firefox ヘルプを参考に、環境はFirefox Developer Editionで用い、about:configの設定も変えていた。

ここを見ることで解決できた。 discourse.mozilla.org 結局IDが必要ということらしい。

公式ドキュメントの

extensionworkshop.com

を見ると

However, from Firefox 48 you can develop, debug, publish, and update extensions without needing to set an explicit ID at all.

とあるので一見必要なさそうだが、その下をよく読むと

If you turn the extension into an .xpi or .zip and install it through about:addons, it will not work. To have it work in this scenario, you will need to add in the browser_specific_settings key in manifest.json

とあるので、自分でzip化してインストールするときには適当なIDを付ける必要がある。

SwitchのMicroSDカードデータ移行はMac上ではできないっぽい

Finderからやっても、cp, rsyncコマンドで -a オプションをつけてもダメだった。 既知の問題のようで、いろいろ調べたけどどうやっても無理っぽいので諦めた方が良さそう。

元も子もない解決策ではあるが、Linux上で cp -a するとあっさりうまくいった。 自分の場合はMacの容量に余裕がなかったので、元SD→外付けHDD→新SDという感じでやった。

しかも副産物として、Linuxの方が新SDへの書き込みが明らかに早い。 Macだと40GBの書き込みに数時間かかっていたのが、Linuxだと20〜30分程度で終了した。 一体Macのファイルコピーはどうなっているのだろう…?

Wineで動かしたSteamでゲームがダウンロードできない

表題の通り。Steam自体は起動するが、MacでもLinuxでもゲームのダウンロードが上手くいかない。 公式WineHQ - Steam Official Releaseでも報告されている(Steam Client Fails to install games/ applications, with the error "content servers unreachable." を参照)。

解決方法は2つ。Wine 3.12以上を使うか、 WineHQ Bugzilla – Bug 45329 – Fresh steam install will not install games -- error: "content servers unreachable" に従う。

前者は、2018/08/10時点ではStableではなく開発版を使う必要があり、自分は未検証。 後者はSteamのconfig.vdfを編集する方法で、こちらは動くことを確認した。

ただし、ゲームのダウンロードが成功するだけで、ゲーム自体が起動するかどうかは別問題なので注意。

NeoVim + vimtexでSyncTeXを使う

SyncTeXを使うためには色々設定項目があって、さらにOS毎に違っており面倒臭いという話。 この記事は

qiita.com

と被るところも多い。 以降に書くことも大抵のことはvimtexのドキュメントを見れば書いてあるが、メモも兼ねて書いておく。

vimtexのインストール、最低限の設定がしてあることを前提とする。 基本的にNeoVimが対象だが、Vimでもそのまま使えるところはその都度明記しておく。

まずneovim-remoteをインストールする。

$ pip3 install neovim-remote

vimrcには次を追記する。 これでMacでもLinuxでも、VimでもNeoVimでも対応できる。 PDFビューアとしてはMacではSkim、LinuxではZathuraを用いている。

if has('mac')
  let g:vimtex_view_method='skim'
else
  let g:vimtex_view_method='zathura'
endif
if has('nvim')
  let g:vimtex_compiler_progname
        \ = 'nvr'
endif

TeXファイルを開くときは

$ NVIM_LISTEN_ADDRESS=/tmp/nvimsocket nvim file.tex

で開く。 /tmp/nvimsocket のところは任意の文字列で良さそう。 aliasを作っておくと便利。

TeX → PDF

上だけでVimでもNeoVimでもOK。 vim上で <localleader>lv を実行すればPDFの該当箇所が開く。

PDF → TeX

Linuxの場合

同じく上だけでVimでもNeoVimでもOK。 PDF上でCtrl+クリックをすれば、(Neo)Vimのカーソルが該当箇所に移動する。 残念ながらウィンドウのフォーカスまでは移動しないようだ。

Macの場合

こちらはNeoVim (CLI)を前提とする。 Skimの設定が必要になる。

環境設定の「同期する」タブを選ぶ。 「PDF-TeX同期サポート」で初期値を「カスタム」にして、 コマンドを nvr、引数を --remote-silent "%file" -c %line にする。 Skimを再起動したり、OSを再起動しないと設定が有効にならないかもしれない。 反映されるタイミングが謎。

これでPDFをCmd+Shift+クリックすれば、該当箇所にNeoVimのカーソルが移動する。

WindowsのVirtualBox上のArch Linuxでxmodmapが効かない

訳あってWindowsVirtualBox上でArch Linuxを動かしているのだが、xmodmapがうまく効かなくて困ったのでメモ。

Macユーザーだったこともあり、個人的にスラッシュの隣のキーはバックスラッシュであってほしい。 そこでxmodmapの出番となるのだが、正しく設定ファイルを書いても反映されなかった。

VirtualBoxアクセラレーション設定を「デフォルト」にしたところ解決した。 KVMが早いと聞いたのでそちらを使っていたのだが、こちらではうまく行かないらしい。 結局これでもうまくいっていないようだ。一体何が問題なのか。