ABC 345
ABC 345 に参加しました。
A 問題
入力に改行文字が入っているため、 getLine を使うか init で落とします。
t=True;i=init;main=interact$(\x->if x==(t,t,t)then"Yes"else"No").((,,)<$>(=='<').head<*>(=='>').last<*>all(=='=').i.tail).i
B 問題
まず整数除算が切り捨てとは限らないことを思い出します (参考):
ghci> 5`div`10
0
ghci> 5`quot`10
0
ghci> (-5)`div`10
-1
ghci> (-5)`quot`10
0
思い出してはいけません。 div は切り捨てであると割り切ります:
main=interact$show.(`div`10).(+9).read
C 問題
遅い解法のようですが、次の通り考えました。
左から右へ \(i\) を動かしつつ、 \(i\) < \(j\) となる \(j\) を選択します。 \(S_i \ne S_j\) となる \(S_i, S_j\) を入れ替えた場合は新しい文字列が生成されます。そうでない場合は元の文字列が生成されます。
よって文字毎に文字数の累積和を作っておけば、新しい文字が生成される場合の数は \(i,j \in [1, N]\) として \((N - i) - \mathit{csum}[S[i]].\mathit{get}(i + 1, N)\) であり、すべての \(i\) に対する計算結果の総和を取って \(O(WN) (W = 26)\) 程度で解答できます。コーナーケースは要注意……
D 問題
ぱっと見で配置の全探索しか思いつかなかったため飛ばしました。普通に解けません。
タイルの向きと順番を決めたら貪欲に配置すれば良いようです。使わないタイルの決め方としては、条件達成時に枝刈りすれば、後ろの方の順番のタイルは暗に不使用となります。
Upsolve します。
E 問題
DP にこだわりがあって特攻しました。これは解法が難しいですし、 TLE の回避が困難な問題だと思います。ざっくりメモします。
\(n\) 個の入力を走査します。まず思いつく \(\mathit{dp}[i][\mathit{iColor}][\mathit{nDiscard}]\) ですが、 \(O(N^2 K)\) は巨大です。次に \(K\) 個まで入力を破棄できる = 最大 \(K\) 個まで振り返ることができると捉え、地理的な DP を考えました。 \(\mathit{dp}[i][iDiscard]\) は最後に \(i\) 番目のボールを取った場合の最大価値とします。
ただしこの計算でも \(O(NK^2)\) となって高速化が足りません。 \(K\) 個前まで振り返るのは止めて、直前まで振り返る畳み込みを考えれば正解間近です。
DP 配列の各スロットに保存した Max と \(c_i\) の色が被った場合はどうするか。それは 2 色分の Max を保存する Top2 モノイドがあれば解決します。そんなのアリ……？
Top2 の高速化
Top2 を半群として結合 <> するのは難しく、ソートなど使ってみましたが TLE になりました。結局 cojna さんの提出 から高速化のアイデアを借りて AC しました。 <> するのではなく insert します。 <> で緩和しない DP として計算するのはショックでした。 sact で緩和するんだと思えなくも無い……？
ソートしない <> としても AC できますが、倍以上に低速化します。青 diff ぐらいから定数倍にも厳しくなりますから、黄〜コーダーを見習って常に最速の実装を選択できる実力が必要だと思いました。たとえばセグメント木ではなく Imos 法とか尺取り法で実装できるというような……。
やはり DP が解けるようになりたいものです。
F 問題
難しそうです。
繰り返し二乗法
ダブリング (binary lifting) を書き直しました。
高速化
ビットの取り出しを U.generate 63 id から以下に変更しました。枝刈りが効きますね。
{-# INLINE bitsOf #-}
bitsOf :: Int -> U.Vector Int
bitsOf x0 = U.unfoldrExactN (popCount x0) f x0
where
f x =
let !lsb = countTrailingZeros x
in (lsb, clearBit x lsb)
API
配列生成
繰り返し二乗法のための配列生成を関数化しました:
-- | Binary lifting.
class BinaryLifting a where
-- | @V.Vector a@ or @U.Vector a@
type VecBL a
-- | @cacheBLV@ or @cacheBLU@
cacheBL :: a -> VecBL a
{-# INLINE cacheBLU #-}
cacheBLU :: (Semigroup a, U.Unbox a) => a -> U.Vector a
cacheBLU = U.iterateN 63 (\x -> x <> x)
{-# INLINE cacheBLV #-}
cacheBLV :: (Semigroup a) => a -> V.Vector a
cacheBLV = V.iterateN 63 (\x -> x <> x)
半群の n 回結合 (stimesBL)
繰り返し二乗法を実施します:
{-# INLINE stimesBL #-}
stimesBL :: (Semigroup a, G.Vector v a) => v a -> Int -> a -> a
stimesBL cache n !s0 = U.foldl' step s0 (bitsOf n)
where
{-# INLINE step #-}
step !s i = let !s' = s <> cache G.! i in s'
型はこの方が良いかもしれません:
stimesBL :: (Semigroup a, BinaryLifting a) => VecBL a -> Int -> a -> a
n 回の半群作用 (sactBL)
たとえば \(M^7 \mathbb{x}\) の計算には \((M^4 M^2 M) \mathbb{x}\) よりも \(M^4 (M^2 (M \mathbb{x})))\) の方が効率が良いので、専用の関数を作っておきました:
{-# INLINE sactBL #-}
sactBL :: (SemigroupAction a b, G.Vector v a) => v a -> Int -> b -> b
sactBL cache n !b0 = U.foldl' step b0 (bitsOf n)
where
{-# INLINE step #-}
step !b i = let !b' = cache G.! i `sact` b in b'
問題演習
Binary lifting を使った主な計算を整理しました。
- \(b^{-1} \bmod p (b < p) = b^{p - 2} \bmod p\)
フェルマーの小定理を使った mod 上の逆元の計算です。Product ModIntを半群としてstimesBLを使って実装できます。が、面倒くさくてリファクタリングしませんでした。 - EDPC R - Walk
行列累乗の問題です。Semigroup (Mat e)およびSemigroupAction (Mat e) (Col e)を実装しました。行列の実装はarrayからvectorに乗り換えました。 - TDPC M - 家
同上です。vectorには直接ModIntが載るので楽ですね。 - ABC 235 E - MST + 1
LCA で解けます (フレンズさんの解説) 。TransitionalAction aを遷移 + 半群として LCA を実装しました。半群が不要な場合はa = ()を割り当てます。
ちなみに () に対する unboxed Vector (関連型、もとい data family) の割り当て は単なる Int (配列長) です。ヒープ使用量 0, ほぼゼロコストですね。 Rust の Vec も似た振る舞いをしますが、ドキュメントを見た感じ、 mem::size_of::<T>() が 0 の場合で実行時に分岐する っぽい です。
MiniAxe (WIP)
以下、完全に自分用です。
背景
MiniAxe (はんだ付けサービス) の Tap-Hold が Permissive Hold だった (?) ので、設定変更のために『QMK をビルドする』方法を調べています。
関連
- Qmk - NixOS Wiki
nixpkgs上のqmkを入れて 公式ドキュメント を読みなさいとのことです。 - QMK Firmware
公式ドキュメントを見てみます。
Setup
コマンドを打つだけで良いようです:
$ qmk setup
..
Ψ QMK is ready to go
$ # `$HOME/` 直下に `qmk_firmware/` が clone された
Building Your First Firmware
QMK のリポジトリに kagizaraya/miniaxe が入っています。画像付き！
$ qmk list-keyboards | rg miniaxe
kagizaraya/miniaxe
qmk compile で miniaxe を指定すればビルドできます。設定変更が必要な場合は miniaxe フォルダ内のファイルを編集すれば良いようです。
ひとまず初期設定のままビルドしてみます:
$ qmk compile -kb miniaxe -km default
出力 (長い)
Ψ Compiling keymap with make -r -R -f builddefs/build_keyboard.mk -s KEYBOARD=kagizaraya/miniaxe KEYMAP=default KEYBOARD_FILESAFE=kagizaraya_miniaxe TARGET=kagizaraya_miniaxe_default INTERMEDIATE_OUTPUT=.build/obj_kagizaraya_miniaxe_default VERBOSE=false COLOR=true SILENT=false QMK_BIN="qmk"
Generating: .build/obj_kagizaraya_miniaxe_default/src/info_deps.d [OK]
Generating: .build/obj_kagizaraya_miniaxe_default/src/default_keyboard.c [OK]
avr-gcc (GCC) 8.5.0
Copyright (C) 2018 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
Generating: .build/obj_kagizaraya_miniaxe_default/src/info_config.h [OK]
Generating: .build/obj_kagizaraya_miniaxe_default/src/default_keyboard.h [OK]
Compiling: .build/obj_kagizaraya_miniaxe_default/src/default_keyboard.c [OK]
Compiling: quantum/keymap_introspection.c [OK]
Compiling: quantum/quantum.c [OK]
Compiling: quantum/bitwise.c [OK]
Compiling: quantum/led.c [OK]
Compiling: quantum/action.c [OK]
Compiling: quantum/action_layer.c [OK]
Compiling: quantum/action_tapping.c [OK]
Compiling: quantum/action_util.c [OK]
Compiling: quantum/eeconfig.c [OK]
Compiling: quantum/keyboard.c [OK]
Compiling: quantum/keymap_common.c [OK]
Compiling: quantum/keycode_config.c [OK]
Compiling: quantum/sync_timer.c [OK]
Compiling: quantum/logging/debug.c [OK]
Compiling: quantum/logging/sendchar.c [OK]
Compiling: quantum/matrix_common.c [OK]
Compiling: quantum/matrix.c [OK]
Compiling: quantum/debounce/sym_defer_g.c [OK]
Compiling: quantum/split_common/split_util.c [OK]
Compiling: quantum/split_common/transport.c [OK]
Compiling: quantum/split_common/transactions.c [OK]
Compiling: quantum/main.c [OK]
Assembling: platforms/avr/xprintf.S [OK]
Compiling: platforms/avr/printf.c [OK]
Compiling: quantum/crc.c [OK]
Compiling: quantum/process_keycode/process_grave_esc.c [OK]
Compiling: quantum/process_keycode/process_magic.c [OK]
Compiling: quantum/send_string/send_string.c [OK]
Compiling: quantum/process_keycode/process_space_cadet.c [OK]
Compiling: tmk_core/protocol/host.c [OK]
Compiling: tmk_core/protocol/report.c [OK]
Compiling: tmk_core/protocol/usb_device_state.c [OK]
Compiling: tmk_core/protocol/usb_util.c [OK]
Compiling: platforms/suspend.c [OK]
Compiling: platforms/synchronization_util.c [OK]
Compiling: platforms/timer.c [OK]
Compiling: platforms/avr/hardware_id.c [OK]
Compiling: platforms/avr/platform.c [OK]
Compiling: platforms/avr/suspend.c [OK]
Compiling: platforms/avr/timer.c [OK]
Compiling: platforms/avr/bootloaders/dfu.c [OK]
Compiling: platforms/avr/drivers/i2c_master.c [OK]
Archiving: .build/obj_kagizaraya_miniaxe_default/i2c_master.o [OK]
Compiling: platforms/avr/drivers/i2c_slave.c [OK]
Archiving: .build/obj_kagizaraya_miniaxe_default/i2c_slave.o [OK]
Compiling: platforms/avr/drivers/serial.c [OK]
Archiving: .build/obj_kagizaraya_miniaxe_default/serial.o [OK]
Compiling: tmk_core/protocol/lufa/lufa.c [OK]
Compiling: tmk_core/protocol/usb_descriptor.c [OK]
Compiling: lib/lufa/LUFA/Drivers/USB/Class/Common/HIDParser.c [OK]
Compiling: lib/lufa/LUFA/Drivers/USB/Core/AVR8/Device_AVR8.c [OK]
Compiling: lib/lufa/LUFA/Drivers/USB/Core/AVR8/EndpointStream_AVR8.c [OK]
Compiling: lib/lufa/LUFA/Drivers/USB/Core/AVR8/Endpoint_AVR8.c [OK]
Compiling: lib/lufa/LUFA/Drivers/USB/Core/AVR8/Host_AVR8.c [OK]
Compiling: lib/lufa/LUFA/Drivers/USB/Core/AVR8/PipeStream_AVR8.c [OK]
Compiling: lib/lufa/LUFA/Drivers/USB/Core/AVR8/Pipe_AVR8.c [OK]
Compiling: lib/lufa/LUFA/Drivers/USB/Core/AVR8/USBController_AVR8.c [OK]
Compiling: lib/lufa/LUFA/Drivers/USB/Core/AVR8/USBInterrupt_AVR8.c [OK]
Compiling: lib/lufa/LUFA/Drivers/USB/Core/ConfigDescriptors.c [OK]
Compiling: lib/lufa/LUFA/Drivers/USB/Core/DeviceStandardReq.c [OK]
Compiling: lib/lufa/LUFA/Drivers/USB/Core/Events.c [OK]
Compiling: lib/lufa/LUFA/Drivers/USB/Core/HostStandardReq.c [OK]
Compiling: lib/lufa/LUFA/Drivers/USB/Core/USBTask.c [OK]
Compiling: tmk_core/protocol/lufa/usb_util.c [OK]
Linking: .build/kagizaraya_miniaxe_default.elf [OK]
Creating load file for flashing: .build/kagizaraya_miniaxe_default.hex [OK]
Copying kagizaraya_miniaxe_default.hex to qmk_firmware folder [OK]
Checking file size of kagizaraya_miniaxe_default.hex [OK]
特に依存追加など不要でビルドに成功しました。ビルド結果は .build/ ディレクトリに入っています:
$ ls ~/qmk_firmware/.build/
kagizaraya_miniaxe_default.elf* kagizaraya_miniaxe_default.map
kagizaraya_miniaxe_default.hex obj_kagizaraya_miniaxe_default/
この結果をキーボードに書き込めば良いようです。
Flashing Your Keyboard
なぜか permissive hold の設定など無かったため、デフォルトのファームウェアをそのまま MiniAxe に書き込んでみます。 (Permissive hold じゃなかった……？)
QMK Toolbox という GUI ツールでファームウェアの書き込みができるそうです。 Linux は非対応でした。
TODO: MiniAxe をブートローダーモードに持っていく？