Codeforces Problems の不具合対応
概要
Codeforces Problems で特定の問題が大量に表示される不具合が発生しました。 原因はクローラのバグだったので直しました。
はじめに
Codeforces Problems
は私が開発した Codefores で出題された問題およびその各ユーザーごとの正答状況を確認しやすくするための Web アプリケーションです.
AtCoder Problems を模倣して作りました。
最近 Codeforces Round #822 (Div. 2)
が重複して大量に表示されるという不具合が発生しました。
この記事では事象の原因および解決方法について述べます。
発生する事象
以下の画像に示すように同じコンテストが重複して大量に表示されています。
原因の究明
Codeforces Problems
では1日1回クローラにより問題のデータを fetch して json ファイルに書き出しています。
コンテストおよび問題のデータが格納されている contests.json
を確認したところ、#822 (Div. 2) が重複して格納されていました。
$ cat contests.json | grep 1734 "id": 1734, "id": 1734, "id": 1734, "id": 1734, "id": 1734, "id": 1734, "id": 1734, "id": 1734, "id": 1734, "id": 1734, "id": 1734, "id": 1734, "id": 1734, "id": 1734, "id": 1734, "id": 1734, "id": 1734, "id": 1734, "id": 1734, "id": 1734, "id": 1734, "id": 1734, "id": 1734, "id": 1734, "id": 1734, $ cat contests.json | grep 1734 | wc -l 25
数えてみたら25個同じコンテストの情報が格納されていました。
コンテストの情報の書き込み時の処理を見たところ以下のような Python コードで実装されていました。
if idx != -1: prev_contest = contest_json[idx] if prev_contest["problems"] is None: contest_json[idx] = add elif len(add["problems"]) > len(prev_contest["problems"]): contest_json = [add] + contest_json elif len(add["problems"]) == len(prev_contest["problems"]): for i, (prev_problem, add_problem) in enumerate( zip(prev_contest["problems"], add["problems"])): if prev_problem != None and "rating" in prev_problem: continue contest_json[idx]["problems"][i] = add_problem else: contest_json = [add] + contest_json
idx
という変数は更新前のコンテスト情報が格納されているインデックスです。
バグの原因は 1つめ elif ブロックでの記述です。
elif len(add["problems"]) > len(prev_contest["problems"]): contest_json = [add] + contest_json
同じコンテストの情報に関して新しいものと古いものを比較して、新しいほうが古いものより問題数が多かった場合、古い情報とは別にデータを追加しています。
これにより、#822 が無限に書き込まれていました。何を意図したコードなのかは不明です。
以下のコミットによりこのバグを修正しました。
また重複して書き込まれた情報については手で直しました。
終わりに
久しぶりにこのアプリのコードを読んだのですが、今回関連するコードだけ見てもかなりひどかったので近いうちにリファクタリングしたいと思います。
長らく放置している issues の対応もそのうちします。
今回の作業は着手してから記事の執筆も含めて1時間程度で終わったので隙間時間を使ってこれからもちょいちょい手直ししていきたいと思います。
Linux でマイクの入力音量が勝手に下がる問題
概要
Linux で有線接続のマイクの入力音声のボリュームが勝手に下がる現象が発生しました.
これは Zoom
や Google Chrome
といったクライアントが勝手にデバイスの音量を操作することが原因であることが分かりました。
また Pulse Audio 側でクライアントによる音量操作を無効化するオプションは現時点では用意されていないようでした。
そこで以下のようなスクリプトを常時実行するという手法によりデバイス音量を一定に保つことでクライントによる音量操作を事実上無効化することに成功しました。
(alsa_input.???-?????.analog-stereo
はデバイス名で適切に置換する必要があります)
$ while sleep 0.1; do pacmd set-source-volume alsa_input.???-?????.analog-stereo 65535; done
環境
以下のようなソフトウェアを使用している環境で検証しました.
- OS :
Ubuntu 20.04
- デスクトップ環境 :
GNOME 3.36.5
- サウンドサーバー :
pulseaudio 13.99.1
- Zoom :
Version: 5.9.3 (1911)
$ cat /etc/os-release NAME="Ubuntu" VERSION="20.04.3 LTS (Focal Fossa)" ID=ubuntu ID_LIKE=debian PRETTY_NAME="Ubuntu 20.04.3 LTS" VERSION_ID="20.04" HOME_URL="https://www.ubuntu.com/" SUPPORT_URL="https://help.ubuntu.com/" BUG_REPORT_URL="https://bugs.launchpad.net/ubuntu/" PRIVACY_POLICY_URL="https://www.ubuntu.com/legal/terms-and-policies/privacy-policy" VERSION_CODENAME=focal UBUNTU_CODENAME=focal $ gnome-shell --version GNOME Shell 3.36.9 $ pulseaudio --version pulseaudio 13.99.1
事象の再現
Zoom Version: 5.9.3 (1911)
Zoom
で会議に参加してマイクを有線接続。ミュートを解除して何かしらの音をマイクに拾わせたところ自動的にマイクの音量が小さくなりました。
音量の設定にはデバイスごとの設定とアプリごとの設定がありますが、今回自動的に下がったのはデバイスごとの設定のみでした。
以下のキャプチャは GNOME のデフォルトのシステム設定を行う GUI である 設定 (Setting)
のサウンド設定の画面です。
入力デバイスの音量が自動的に下がっていることが確認できます。(もちろん音量を手動で下げているわけではありません)
Google Chrome
(Google Meet)
この問題は Zoom
固有の問題ではなく他のアプリケーションでも発生しました。
Google Chrome 上で Google Meet
を起動し会議に参加してマイクに音声を拾わせた場合も同様の事象が発生しました。
原因
ググったら同様の事象についての質問が既にありました。
どうやら Zoom
や Google Chrome
といったクライアントアプリ側で自動で入力デバイスの音量を調節するという迷惑な機能があるようです。
Zoom
の場合は以下のように Automaticcaly adjast microphone volume
という設定項目があり, クライアント側でこの機能をオフにすることができました。
実際にこの機能をオフにした状態で Zoom で会議に参加してマイクに音を拾わせたところ自動的に音量が変化する現象はなくなりました。
しかし, Google Chrome
で Google Meet
のようなアプリを起動している場合はアプリ側でこの機能をオフにすることはできなさそうでした。
以下に引用するように, Google Chrome
ではおそらく WebRTC
プロトコルが使われており, Chrome/Chromium の WebRTC 実装には Auto Gain Control
という機能があり,
ウェブアプリ自体にこの機能をオフにするオプションが無い限りオフにできないらしいです。
Unfortunately the WebRTC implementation in Chromium comes with a handy “feature” called Automatic Gain Control that tends to screw with your microphone volume. Unless the web app itself gives you an option to disable it, there is otherwise no way turn it off, and Chrome developers don't want to add a global “off switch” for it.
また, PulseAudio 側でクライアントによる音量操作を無効化するオプションは現時点では用意されていないようでした。issue がたっていました。
- 関連する issues
解決策
下記の質問の解答の内最も upvote が多いものを試したところクライアント側で入力デバイスの音量を変更を事実上禁止することができました。
手法は単純で以下のスクリプトを実行するだけです。
$ while sleep 0.1; do pacmd set-source-volume alsa_input.???-?????.analog-stereo 65535; done
なお, alsa_input.???-?????.analog-stereo
のところは下記のコマンドで得られるデバイス名で適切に置換する必要があります。
$ pacmd list-sources | grep alsa_input name: <alsa_input.usb-USB_HD_Camera_USB_HD_Camera-02.iec958-stereo> name: <alsa_input.pci-0000_00_1b.0.analog-stereo> name: <alsa_input.usb-USB_HD_Camera_USB_HD_Camera-02.iec958-stereo.echo-cancel>
私の場合は alsa_input.pci-0000_00_1b.0.analog-stereo
で置換しました。
このスクリプトは 0.1 秒ごとに pacmd
という PulseAudio の設定を変更するコマンドを実行してデバイスの音量を固定値としています。
65535
という値は 100% に該当します。上記の質問の解答者は 90000
(135%) に設定していました。
この手法は無駄に CPU リソースを使うのであまりエレガントな解決法とは呼べなさそうです。
しかし残念ながら現時点ではクライアントからデバイスの音量の制御を抑制する方法としてはこれくらいしかなさそうです。
今後 PulseAudio に新しいオプションが追加されることを期待したいです。(お前がコミットしろ)
このスクリプトを実行すると以下のように手動でデバイス音量を調節しようとしても固定値にすぐに戻されてしまいます。 バグっぽいですがこれは意図した通りの挙動です。
毎回このスクリプトを手動で実行するのは面倒なので, systemd により起動時に自動で実行するようにしてみます。
上記のシェルスクリプトを適当な場所に保存して chmod +x
で実行権限を付与します。
次に、以下のように ~/.local/share/systemd/user/
に systemd ファイルを作成します。
ExecStart
に渡す PATH は絶対PATHで指定しました。
$ vim ~/.local/share/systemd/user/no-agc.service $ cat ~/.local/share/systemd/user/no-agc.service [Unit] After=pulseaudio.service Requires=pulseaudio.service [Service] ExecStart=/home/kira924age/work/configs/saber/pulse-audio/no-agc.sh ExecReload=/bin/kill -s HUP $MAINPID KillSignal=SIGQUIT TimeoutStopSec=5 KillMode=process PrivateTmp=true Restart=always [Install] WantedBy=default.target
次に以下のコマンドで自動起動を有効にします。
$ systemctl --user enable no-agc.service
再起動して service が起動していれば勝ちです。
$ sudo reboot $ systemctl --user status no-agc.service ● no-agc.service Loaded: loaded (/home/kira924age/.local/share/systemd/user/no-agc.service;> Active: active (running) since Thu 2022-02-17 22:06:44 JST; 13s ago Main PID: 2141 (no-agc.sh) CGroup: /user.slice/user-1000.slice/user@1000.service/no-agc.service ├─2141 /bin/bash /home/kira924age/work/configs/saber/pulse-audio/n> └─4359 sleep 0.1 2月 17 22:06:44 saber systemd[2083]: Started no-agc.service. 2月 17 22:06:46 saber no-agc.sh[2190]: デーモンが応答しません
試したけどうまく行かなかった手法
ArchWiki の以下の項目に書いてあることも試しましたがうまく動作しませんでした。
/usr/share/pulseaudio/alsa-mixer/paths/analog-input*.conf
に該当するファイルを検索. (Ubuntu の場合は Arch とは該当ファイルがあるディレクトリが異なっていました)
$ sudo ls /usr/share/pulseaudio/alsa-mixer/paths/ | grep -oE ^analog-input.*\.conf$ analog-input-aux.conf analog-input-dock-mic.conf analog-input-fm.conf analog-input-front-mic.conf analog-input-headphone-mic.conf analog-input-headset-mic.conf analog-input-internal-mic-always.conf analog-input-internal-mic.conf analog-input-linein.conf analog-input-mic-line.conf analog-input-mic.conf analog-input-rear-mic.conf analog-input-tvtuner.conf analog-input-video.conf analog-input.conf
検索に該当した全てのファイルについて以下のようにファイルを編集 (!!! PulseAudio の設定ファイルを編集する前にバックアップを取ることをおすすめします。何かあったときにすぐ元に戻せるようにしたほう良さそうです !!!)
[Element Capture]
の下の volume を zero に設定[Element Internal Mic Boost]
の下の volume を zero に設定[Element Int Mic Boost]
の下の volume を zero に設定[Element Mic Boost]
の下の volume を zero に設定
(注意) [Element Headphone Mic Boost]
や [Element Mic Boost (+20dB)]
といった全てのバリエーションでも同様に設定する
PulseAudio を再起動して設定を反映させる。
$ pulseaudio -k $ pulseaudio --start
この手法は PulseAudio の Auto Gain Cntorol を無効化する方法としていろいろなところで紹介されているものですが私の場合はうまく動作しませんでした。
音量が小さくなる現象はなくなりましたが、逆に大きくなる現象が発生しました。
また, /usr/share/pulseaudio/alsa-mixer/paths/
は PulseAudio のパッケージを更新するたびに上書きされるので, そのたびに編集する必要があります。
参考文献
AtCoder Problems のパクリアプリ CF Problems を作りました
概要
AtCoder Problems
を模倣して CF Problems
という Web Application を作りました.
(2021-07-07追記) 衝突を避けるためにサイト名を Codeforces Problems
に改名しました.
はじめに
AtCoder Problems
の Codeforces
版みたいな Web Application があったら良いなと思っていたのですが, これまでのところ私の観測する範囲では存在していませんでした.
(2021-07-07追記) あとでちゃんと探したらありました.
- Contest Mania
- https://tom0727.github.io/cf-problems/
- このブログ書いた後に出来たサイト
そして, ちょうど Web フロントエンドの勉強をしたいということもあり良い機会だと思って作りました. 下記に示すリンクから作ったものを見ることが出来ます.
Codeforces は Codeforces API
という API を公開しているので今回はこれを利用しました.
開発の際は AtCoder Problems
と yukicoder problems
のコードを参考にさせてもらいました.
宇宙ツイッタラーX (@kenkoooo) さん, iiljj さん, その他のコントリビューターの皆さんに感謝してます.
CF Problems とは?
CF Problems
は Codeforces API
を利用して Codeforces
の問題およびユーザー情報を本家とは違う形で表示するフロントエンドツールです.
AtCoder Problems
っぽいものを目指して作りましたが, 実装が面倒あるいは Codeforces API
のみでは不可能だった機能を省きました.
まず. ページが Table
と User
の2種類しかありません. List
は面倒だったので省きました. (今後やる気があれば実装するかもしれません)
それぞれのページの外観は以下の画像が示す通りです.
Table
ページの外観
User
ページの外観
AtCoder Problems
に寄せた外観であることが確認できます.
既知の問題点
CF Problems
には現時点で把握しているだけでも以下のような問題点があります.
- 本来表示されて欲しい問題が Table ページに表示されないことがある.
例えば直近では Codeforces Round #700 (Div. 2)
のC問題以降が Table で表示されていません.
これは Codeforces API
の仕様なのでフロントエンド側で対処するのは難しそうです.
なので当分あるいは永遠に改善されないと思います.
(2021-07-07追記) GitHub Actions でクローラを定期実行することでこの問題は解決しました.
issue URL : Div1 と Div2 の併設回で共通で出題されている問題がテーブルページにおいてどちらか一方にしか表示されない · Issue #1 · kira924age/CodeforcesProblems · GitHub
- Dark Theme で Table を Chrome 系のブラウザで表示すると右に謎の白い線が入る
以下の画像に示すとおり謎の白い線が Table に右側に表示されています. CSS を色々いじったのですが消えてくれないです. ちなみに FireFox ではなぜか表示されません. 意味不明です.
(2021-09-12追記) 何もしてないのに今見たら手元の環境では治ってました. ブラウザ (Chrome) のバグだったのかも?
- コードが雑
これは機能的な問題ではないのですが, コードがとても雑です.
Web フロントエンド初心者が雑に書いたものなのでそれはそうです.
具体的に言うと, TypeScript の型定義をサボって any
を多用した,
エラーハンドリングをサボった, などがあります.
コードが雑なので把握していないバグが潜んでいる可能性は非常に高いです.
汚いコードは下記の GitHub のリポジトリから見ることが出来ます.
使用したツール
最後にアプリケーションを作る上で利用したツールを書いておきます.
- React
- JavaScript の View ライブラリです
- https://github.com/facebook/react
- Create React App
- ワンライナーで環境構築をしてくれる便利なやつです
- https://github.com/facebook/create-react-app
- ant-design
- 自称世界で2番目に人気のある React UI Library です
- https://github.com/ant-design/ant-design
- recharts
- React 向けのグラフ描画ライブラリです
- https://github.com/recharts/recharts
- nivo
@nivo/calendar
を使って Heatmap を実装しました- https://github.com/plouc/nivo
- react-router
- ルーティング (ここでは状態 と URL を紐付けるの意) するために使いました
- https://github.com/ReactTraining/react-router
- react-toggle
- toggle (切り替え) 機能を手軽に実装するために使いました
- https://github.com/aaronshaf/react-toggle
- react-helmet
- theme の切り替え機能を実装するために使いました
- https://github.com/nfl/react-helmet
- react-collapse
- collapse (折りたたみ) 機能を手軽に実装するために使いました
- https://github.com/nkbt/react-collapse
- drawio-desktop
- Codeforces っぽいロゴを作成するのに使いました
- https://github.com/jgraph/drawio-desktop
- Favicon Generator
- Favicon を作成するのに使いました
- https://favicon.io/favicon-generator/
- Codeforces API
- GitHub Pages
- GitHub Actions
- クローラの定期実行やデプロイの自動化をするために使いました.
- Public Repository なら制限無しで無料で使えてお得
- Go
GNOMEで時刻表示形式を変更する
概要
GNOMEはUnixライクなOSで動作するオープンソースのデスクトップ環境です. 現在, Ubuntu や CentOS などの多くのLinuxディストリビューションで標準のデスクトップ環境として採用されています.
今回はGNOMEにおいて時刻表示形式をどのように変更するかを調べました.
環境
以下のような環境で検証しました.
$ cat /etc/os-release NAME="Ubuntu" VERSION="18.04.4 LTS (Bionic Beaver)" ID=ubuntu ID_LIKE=debian PRETTY_NAME="Ubuntu 18.04.4 LTS" VERSION_ID="18.04" HOME_URL="https://www.ubuntu.com/" SUPPORT_URL="https://help.ubuntu.com/" BUG_REPORT_URL="https://bugs.launchpad.net/ubuntu/" PRIVACY_POLICY_URL="https://www.ubuntu.com/legal/terms-and-policies/privacy-policy" VERSION_CODENAME=bionic UBUNTU_CODENAME=bionic $ gnome-shell --version GNOME Shell 3.28.4
設定 (Settings)
設定 (Settings) からは表示形式を 24時制/12時制 のいずれかに変更することができます.
この変更画面にたどり着くのも少し面倒なので手順を述べます.
- 設定 (Settings) を開く. (左上の アクティビティ (Activity) ボタンを押して, Settings と入力すると開けます)
- サイドバーの一番下の
詳細 (Details)
ボタンを押す. - サイドバーの
日付と時刻 (Date & Time)
を押す.
Tweaks
GNOMEのUIのカスタマイズをGUIから行える Tweaks というツールがあります.
下記のコマンドでインストールできます.
$ sudo apt install gnome-tweaks
Tweaks のトップバー (topbar)
という項目から日付や秒を表示するかどうかを選択できます.
Clock Override
Clock Override
というGNOMEの拡張機能により, ステータスバー(トップバー)の時刻表示形式を変更することができます.
インストールはブラウザ経由で行う方法とUbuntuソフトウェアセンターから方法があります.
Ubuntu ソフトウェアセンターまたは https://extensions.gnome.org の検索バーに Clock Override
と入力して適当にボタンを押せばインストールできます.
拡張機能は Tweaks の拡張機能/Extension という項目から設定できます.
Clock Override
を使うことで, トップバーに表示される時計の時刻表示形式は自由に変更できます.
Datetime Format
Datetime Format
というGNOMEの拡張機能により, トップバーおよび日付メニューの時刻表示形式を変更することができます.
文字コードに日本語を含むものを指定すると, 設定自体はできるのですが, それ以降この拡張機能の設定をしようとすると以下のようなエラーが出ます.
Error: Failed to convert locale string to UTF8: 変換する入力に無効なバイトの並びがあります Stack trace: dateTimeFormat@/home/kira/.local/share/gnome-shell/extensions/datetime-format@Daniel-Khodabakhsh.github.com/Utilities.js:15:20 create/updatePreview@/home/kira/.local/share/gnome-shell/extensions/datetime-format@Daniel-Khodabakhsh.github.com/FormatTarget.js:49:25 create@/home/kira/.local/share/gnome-shell/extensions/datetime-format@Daniel-Khodabakhsh.github.com/FormatTarget.js:55:2 buildPrefsWidget/<@/home/kira/.local/share/gnome-shell/extensions/datetime-format@Daniel-Khodabakhsh.github.com/prefs.js:136:61 buildPrefsWidget@/home/kira/.local/share/gnome-shell/extensions/datetime-format@Daniel-Khodabakhsh.github.com/prefs.js:136:2 _selectExtension@resource:///org/gnome/shell/extensionPrefs/main.js:91:22 wrapper@resource:///org/gnome/gjs/modules/_legacy.js:82:22 _onCommandLine@resource:///org/gnome/shell/extensionPrefs/main.js:243:17 wrapper@resource:///org/gnome/gjs/modules/_legacy.js:82:22 main@resource:///org/gnome/shell/extensionPrefs/main.js:397:5 @<main>:1:43
どうやら Unicode をサポートしていないようです. Github に issue が立ってました.
GSettings
GUIによる Datetime Format
の設定ができなくなったので,
GSettings
を使って Datetime Format
の値の設定をしてみます.
GNOMEにおいて日付の表示形式を含むユーザの設定情報は dconf
という設定システムにより管理されています.
GSettings
は dconf
のフロントツールで, 設定を行うためのAPI群です.
gsettings
コマンドにより, ユーザ設定の編集を行うことができます.
man gsettigns
と言うコマンドを叩くとマニュアルが表示されます.
以下のコマンドで Datetime Format
の key をリスト表示させてみます.
$ gsettings --schemadir ~/.local/share/gnome-shell/extensions/datetime-format@Daniel-Khodabakhsh.github.com list-keys org.gnome.shell.extensions.datetime-format datemenuday-format statusbar-format statusbar-toggle datemenudate-toggle datemenudate-format datemenuday-toggle
statusbar-format
の値を変更することでステータスバー (トップバー) の時刻表示形式を変えてみます.
日付の書式文字列は man date
とするとマニュアルを参照できます.
以下のコマンドで, statusbar-format
の値を %m月%d日(%a) %H:%M
に変更できます.
$ gsettings --schemadir ~/.local/share/gnome-shell/extensions/datetime-format@Daniel-Khodabakhsh.github.com set org.gnome.shell.extensions.datetime-format statusbar-format "%m月%d日(%a) %H:%M"
以下のコマンドで, datemenuday-format
の値を %H:%M:%S
に変更できます.
$ gsettings --schemadir ~/.local/share/gnome-shell/extensions/datetime-format@Daniel-Khodabakhsh.github.com set org.gnome.shell.extensions.datetime-format datemenuday-format "%H:%M:%S"
以下のコマンドで, datemenudate-format
の値を %Y年%m月%d日(%a)
に変更できます.
$ gsettings --schemadir ~/.local/share/gnome-shell/extensions/datetime-format@Daniel-Khodabakhsh.github.com set org.gnome.shell.extensions.datetime-format datemenudate-format "%Y年%m月%d日(%a)"
これらの設定により時刻表示部分は以下のような外観となりました. カレンダーの月の値の表示の下部が少し隠れているのが気になりますが概ね良さそうです.
参考文献
- https://en.wikipedia.org/wiki/GNOME
- https://help.ubuntu.com/stable/ubuntu-help/clock-set.html.en
- http://ubuntuhandbook.org/index.php/2019/02/customize-time-date-format-ubuntu-18-04-gnome-panel/
- https://kokufu.blogspot.com/2018/11/gsettings-dconf.html
- https://en.wikipedia.org/wiki/Dconf
- https://access.redhat.com/documentation/ja-jp/red_hat_enterprise_linux/7/html/desktop_migration_and_administration_guide/configuration-overview-gsettings-dconf
転倒数 アルゴリズム
転倒数 (inversion number) とは?
数列 a = {a_0, a_1, a_2 ... a_n-1 } が与えられたとき,
i < j かつ a_i > a_j を満たす (i, j) の組の個数を転倒数または反転数という.
たとえば a = {3, 1, 5, 4, 2} のとき,
i < j かつ a_i > a_j となっている組は,
(3, 1), (3, 2), (5, 4), (5, 2), (4, 2) の 5組であるから転倒数は 5 となる. (添字ではなく要素の組を列挙した)
転倒数は下記のようなバブルソートを行った際の交換回数と等しくなることが知られている. 一回の交換で反転数は1減少し, ソートが完了すると反転数は0となるのでそれはそう.
#!/usr/bin/env python3 def bubble_sort(A): cnt = 0 for i in range(len(A)): for j in range(len(A)-1, i, -1): if A[j] < A[j-1]: A[j], A[j-1] = A[j-1], A[j] cnt += 1 return cnt
直感的には転倒数は昇順ソートされた状態を正しい並びとしたとき, 正しくない並びとなっている組の数と考えることができる.
転倒数を愚直な実装で求めると時間計算量は となるが以下に示すように
のアルゴリズムが存在する.
Fenwick Tree(Binary Indexed Tree)を用いる方法
i < j かつ a_i > a_j を満たす要素を数えるには以下の 2 つの方法が考えられる.
i についてループを回し i < j かつ a_i > a_j となるものを数える.
j についてループを回し i < j かつ a_i > a_j となるものを数える.
どちらもほぼ同じように見えるが, 後者のように考えないとうまくいかない.
後者の方法で i < j かつ a_i > a_j となるものを数えるとき Fenwick Tree を使うと各 j について で求めることができる.
Fenwick Tree は区間の和の計算, 要素の値の更新がそれぞれ でできるデータ構造.
- C++ による Fenwick Tree の実装例
struct fenwick_tree { typedef int T; T n; vector<T> bit; // 各要素の初期値は 0 fenwick_tree(T num) : bit(num+1, 0) { n = num; } // a_i += w void add(T i, T w) { for (T x = i; x <= n; x += x & -x) { bit[x] += w; } } // [1, i] の和を計算. T sum(T i) { T ret = 0; for (T x = i; x > 0; x -= x & -x) { ret += bit[x]; } return ret; } // [left+1, right] の和を計算. T sum(T left, T right) { return sum(right) - sum(left); } };
使い方
Fenwick Tree は最初 a = {a_0, a_1, a_2 ... a_n-1} の数列があり, 各要素の初期値は 0 となっている.
j = 0 から n-1 までループを回し. 以下のような処理をすることで転倒数を求めることができる.
fenwinck_tree f_tree(n); for (int j = 0; j < n; j++) { ans += j - f_tree.sum(a[j]); f_tree.add(a[j], 1); }
fenwick tree の i 番目の値が x であるとき, 値が i である要素が x 個あるものとみなす. すると sum(a[j])
が返す値は i < j かつ a_i <= a_j の個数となる. なぜなら sum(a[j]); が実行されるとき fenwick tree に追加されている数列の要素は必ず, 現在の j より小さいときに追加されたものであり(i < j を満たす), sum(a[j]) は区間[1, a[j]]
の和であるから.
数えたいのは i < j かつ a_i > a_j であるから, 現在見ている数列の要素の個数である j から sum(a[j]) を減算した値を足せば良い.
注意点としては size n の tree を作成する際の n の値は数列の最大値より大きなものを設定する必要があるという点と, 数列の要素に0以下のものがあると要素の追加ができないので下駄を履かせる必要があるという点である.
分割統治法を使う方法
以下のようなコードでマージソートを行いながら転倒数を求めることもできる. (引数として渡した配列はソートされてしまう破壊的な関数である点に注意!!!)
long long merge_cnt(vector<long long> &a) { int n = a.size(); if (n <= 1) { return 0; } long long cnt = 0; vector<long long> b(a.begin(), a.begin() + n / 2); vector<long long> c(a.begin() + n / 2, a.end()); cnt += merge_cnt(b); cnt += merge_cnt(c); int ai = 0, bi = 0, ci = 0; // merge の処理 while (ai < n) { if (bi < (int)b.size() && (ci == (int)c.size() || b[bi] <= c[ci])) { a[ai++] = b[bi++]; } else { cnt += n / 2 - bi; a[ai++] = c[ci++]; } } return cnt; }
与えられた数列を A とし, その数列を B と C に分割(Devide)する.
B, C をそれぞれソート済みとすると, Aの転倒数はBの転倒数とCの転倒数を足し, さらにBとCとの間にまたがって存在する i < j かつ a[i] > a[j] となるような組の数を足したものとなる.
数列 a = {3, 1, 5, 4, 2,} を例として考える. merge_cnt() が実行されると, 数列は以下のように再帰的に分割される.
A = {4, 2}, B = {4}, C = {2} とする. B と C はそれぞれサイズが1なので転倒数は0である.
BとCを merge するとき, cnt がどのように更新されるかを見る.
while (ai < n) { if ( bi < b.size() && (ci == c.size() || b[bi] <= c[ci]) ) { a[ai++] = b[bi++]; } else { cnt += n / 2 - bi; a[ai++] = c[ci++]; } }
数列 C の要素が Aに merge されるとき (i < j), cnt は更新されている. これは転倒数の定義 (i < j and a[j] < a[i] となる i, j の組の数) を考えれば当然である.
cnt += n/2 - bi;
の n/2
は数列B のサイズを表している. bi は BのインデックスでBの要素全てがAに代入されると n/2 となる.
数列Cの要素が merge されるとき, 数列 B のうちまだ merge されていない要素の個数を cnt に足している.
merge の処理が済んだ数列はきちんとソートされる.
分割された数列の転倒数を赤で示したのが下図である.
使用例
AOJ: ALDS1-5 D
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_D&lang=jp
Fenwick Tree による解答例
- http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3395873
- 109 個の配列を確保はできないので map を使って数列を置換する.
- 分割統治による解答例