ABC008-D問題
蟻本で似た問題（P121, Bribe the Prisoners）を見たことがあったので同じように考えて実装しました。機械を動かしたあとその機械で取った金塊で分断された場所は互いに関係しない独立した場所です。なので、ある機械を動かしたときに得られる金塊の数は
（１）機械を動かして得られる金塊
（２）分断されたそれぞれのエリアで得られる金塊
の和になります。それぞれのエリアについて再帰的に考えていけば得られる最大の金塊数を求められます。dp[sx][sy][fx][fy]を左上を(sx, sy)、右下を(fx, fy)としたエリアで得られる金塊としてメモ化再帰で実装しました。境界条件の部分は番兵法つかったほうが良さそう…
範囲内を全て探索しているところを機械がある点に絞れば100点の制約でも間に合いました。
ABC037-D問題
ABC038-D問題
解説読んでもわからなかったBainary Indexed Tree(BIT)ってなんだよ！ってのとソートの方法を指定する方法についてのメモ。
BITについては以下のスライドが分かりやすかったです。和ではなくその区間の最大値を保存することである区間の最大値はO(logN)で求められます。BITは1からaまでの区間についての情報を保持していますが、区間[a, b]について考えたいならセグメントツリーのほうが便利そうです。
http://hos.ac/slides/20140319_bit.pdf
hについて昇順でhが等しかったらwの降順になるようにするソートが必要です。以下のサイトを参考にソートの比較用の関数をつくることで実装しました。他にも構造体で > を定義することで行ったり、ラムダ式を用いる方法でもできそうです。
C++（ソートの補足） - アルゴリズム講習会
ABC041D
解説を読んでも満点解法がなかなかわからず苦労したのでそのメモです。
まずトポロジカルソートは有向辺が全て1方向へ向くようにソートをソートをすることです。入力例1についてトポロジカルソートを行ってみると以下の2通りになります。
このトポロジカルソートの種類を求める問題と考えることができます。
解説のように漸化式を計算することでなぜトポロジカルソートができるか考えます。頂点vをもっとも右に置くことができれば、頂点vを除いた部分集合について同じことを再帰的に行うことでトポロジカルソートとなります。部分集合Sの中でもっとも右における頂点vとは vからS-{v} への有向辺がないことと同義です。その部分集合の他の頂点に対する有向辺があると左向きの有向辺が生じてしまうためトポロジカルソートの条件を満たせないということです。
このような集合を含んでいる漸化式を扱うときにはBitDPがよくある手段（らしい）です。
頂点 1 2 3 4
0 0 1 0 S = {3}
1 1 0 1 S = {1, 2, 4}といったようにビットが1の部分の頂点を含んでいる部分集合と対応させることで集合を表現します。0から2^Nまで小さい方から順に計算していくことで答えを求めることができます。これをコードで実装します。
以下蛇足。bit演算に慣れていなかったこともあってBitDPの実装に時間をかけてしまった。集合を扱うときは鉄板の方法っぽい。あとN<=16とかでO(N!)だと間に合わないけどO(2^N)だと間に合うときはBitDPを使う方法のことが多いらしい。Nの制約から使うアルゴリズムが想像つくようになってきた。
Atomで使ってるパッケージについて
Package
あとで忘れて困る未来が浮かんだので忘備録として書いておくことにしました。C++用にパッケージをいじってます。
OS: Windows10 64bit
コンパイラ: MinGW(GCC)
atom-beautify
オートフォーマットしてくれるパッケージです。整形にClang-formatを使ってるのでClangのインストールが必須。
以下のやり方でインストールしました。
windowsでatom-beautifyを使おうとしてハマったこと - Qiita
LLVM Clang の Windows へのインストールと使い方 | プログラマーズ雑記帳
autocomplete-clang
補完をしてくれるパッケージです。autocomplete-plusが前提として必要ですが最近のなら標準で入ってます。これもClangのインストールが必須です。
linter, linter-gcc
静的コード解析、つまりエラーの位置をAtomのエディタ上に出してくれるパッケージです。いちいちコマンドプロンプトでコンパイルしてエラーメッセージと行数を照らし合わせてなんて手間はもういりません。linter は linter-gccの前提として必要です。linter-gccの設定にgccやg++のパスを入れる必要があります。MinGWでデフォルトだと C:\MinGW\bin\g++.exe です。
file-icons
ツリーやタブのアイコンを拡張子に合わせて変えてくれるパッケージです。一目でファイルの種類がわかるので気に入ってます。
highlight-line
カーソルが入ってる行をハイライトしてくれるパッケージです。これでカーソルを見逃す心配はありません。
japanese-menu
日本語化してくれるパッケージです。
minimap
エディタの右側にコードの全体図を表示してくれるパッケージです。
minimap-autohide
minimapを必要がない時は隠してくれるパッケージです。コード書いてる時は使わないので消えててくれるので便利です。
Design
font
Ricty Diminished Discordを使ってます。環境設定にフォント名を入れる欄があるのでそこに入力して再起動すればフォントが切り替わります。Ricty Diminished Discordのインストールは以下を参考に行いました。
見やすいプログラミング用フォント「Ricty Diminished」をWindowsにインストールしてSublime Textで利用する方法
style.less
選択範囲が灰色で見づらかったので以下のサイトを参考に直しました。
Atomで選択範囲の背景色を見やすく変更する – nocorica
コメントの色が灰色で同様に見づらかったのでstyle.lessに以下の記述を追加して暗い黄緑のような色に変更しました。
atom-text-editor::shadow {
.comment {
color: fade(greenyellow, 40%);
}
}
ABC049D
自力では手も足も出なかったのでeditorialと解説放送を参考に実装しました。
youtu.be
https://youtu.be/jvAX9Z7beLg
グラフの連結を管理するために、グループ分けを管理するためのデータ構造であるUnion-Find木を使います。
道路での連結を表すUnion-Find木と電車での連結を表すUnion-Find木をそれぞれ用意し管理します。
Union-Find木では連結している頂点同士では根となるノードが同じになります。
よって、道路と電車双方で連結している頂点はその頂点の根がそれぞれ同じとなります。
そのような頂点の数を数えることで両方で連結している頂点数を求めることができます。
GCCとclang間違えてCE出したり、DじゃなくてAに提出したりしてたので本番でやらかさないよう気をつけたい。
あと同じpairを数えるのにcount使ったらTLEだった。よくよく考えたらO(N^2)だし当たり前だった。
