2016/5 Solved(2)
5/17
行列回転のところでバグらせて悩んでしまった。また、島反転は、与えられた位置からBFSすることによってどのエリアが反転するかを求めることが出来る。
確率のDP。dp[いるマス][持っているお金]=確率という状態を持って、dp[0][0]=1として、後退することはないので0マスの位置から小さい方から順番に確率を更新していけばよい。
C++に文字列のsplitはないので、自前で実装しないといけない。そんなにめんどくさくないけど、忘れてしまうので、この実装を時々思い出すようにしたい(submission)。
5/18
まだ訪れていない点があればBFSし，訪れた頂点を保存，そして訪れた頂点数をnとして訪れた頂点同士を結ぶ辺の個数がn-1個ならその連結部分は木であると分かる．そして，その訪れた頂点を更新し同じことを繰り返す(submission)．
5/19
「i番目の人が現時点でj番目の地図を集められうるか」というn*nの2次元配列(pとする)を用意して，日ごとに調べていく．グラフ的に考えるとわかりやすい(人が頂点，辺が会えることを表す)．その日ごとにやるべき操作としては，
- その日が空いている人のリストアップ
- リストアップされた人m人に対してiとjを結ぶm*(m-1)/2本の辺を張る
- 各頂点からたどり着ける人を調べ，そのたどり着ける人たちxでp[x][]の論理和を取る．すると，これがたどり着ける人たちx全てに対して新しいpと出来るのでそれを更新する．
- 各頂点に対して，全ての地図が集まっているかチェックする．なければ次の日へ進み，1.から順に繰り返す．
となる．n頂点に対してただBFSをすると結構重くなる可能性があるが，調べている途中で既に訪れている頂点から，それを根とするBFSは必要ない(結局同じものが得られてしまう)ので，BFSの回数は抑えられるはず．
シンプルなDFS．どの順番で手前から重ねっているかを仮定して，長方形もしくは影になっている部分だけで構成されていればそれは危険なものではないという方法を使い最後までたどりつけるルートがあればtrueを返せば良い．
5/20
再帰を使って構文解析していく．論理積と論理和の部分は，左から見ていって開き括弧と閉じ括弧の数が一致している部分のすぐ右を適用すべき演算子として選び，その演算子より左の部分列と右の部分列の構文解析の結果をその演算子によって計算する処理にすれば良い．
頂点間に対して有向辺を作成するコストが与えられるので，sからg1とg2に行けるようコストの最小を答える問題．まず，最短経路の合ワーシャルフロイドを使って全頂点間の最短経路を求めておく．それから，s→g1とs→g2の経路には途中までルートを共有する部分があるはずだと考え，中継点aを1つ決め，s→aとa→g1とa→g2の経路を作るコストが最小に出来る位置を選ぶようにすれば良い．もし共有部分が無いのなら，それは中継点がスタート地点になることと等しい．また，s→g1→g2となるようなときもa=g1になることに等しいので，aを全ての頂点に対して調べることで問題は解決する．
まず式の中に現れる変数の種類をsetなどにカウントしておく．そして，'='で2つの文字列に分けて，その２式に対して変数をビット全探索的に試していく．括弧の途切れの位置は上に書いたものと同様に先読みすることで実現できる．
以下の様な判定器を作る．空文字ならTrueを返す．そうでなければ，3文字以上で先頭がm，末尾がwの時に先頭と末尾を除いた部分文字列を取り，eを見つけるごとにその前後で部分列を切り取り再帰的に判定機に入れる．前後で両方ともTrueが帰ってくるところが1つでもあればそこはTrueになる．論理積と論理和だと表現しやすい．あとは結果をメモ化する(submission)．部分文字列の先頭と末尾を決める区間DPの方が実行速度が絶対速いし，そっちが想定かもしれない...明らかに自分の提出したやつは他の人よりめっちゃ時間食ってる．
5/21
はじめに，各行に点がいくつあるかを数えておく．そして，一番右の点を+に置き換え，それ以外の点は空白にしておく．更に，行ごとの点の数をその時に数えておく．そして，上の行から順に見ていく．今見ている行を
行目として，そこから下の
行目に注目していく．そこで，先に
なる
を見つければそのスレッドから伸びる
|は無い．なる
を見つければ，
行目と
行目の間にその
+の真下には|が伸びていることになる．この方法でやると時間計算量はなので十分間に合う．
全ての文字列を実際に作ってmapに入れていく．現れた回数が2以上のもののなかで，最長かつ辞書順最小のものを選ぶ．
構文解析していく．左再帰の除去というキーワードで調べるとうまく実装出来る．また，?を全通り試す必要はない．なぜなら，文字の数と位置関係は?が何になろうと変わらない．つまり，構文解析しながら?はそのまま保持していき，最終的な結果の?の位置を全てAに置き換えるのが辞書順最小になり，この方法が最適．
ARC 054に参加
ABの2完．Cは思いつきもしなかった...
5/22
実装方針で悩んでいた．変数と数字を頂点として，同じものを辺で結んでいき，まだ訪れてないアルファベットの頂点を順に根としてBFSしてその連結成分の個数を数える．数字と繋がっていればそこはノーカン，つながってなくて先頭の変数と繋がっていれば9倍，つながってないなら10倍する．
メモ化再帰．でも，現在見ているステップと，その一個手前が分かってれば問題ないので，メモ化再帰より配るDP的に書けばもっとメモリ制約とかに悩まなくて済んだかも...
そのマスに止まった時に最終的にどこにたどり着くかの写像を前準備として作る．その時に無限ループしてしまうところがあればそこにチェックも入れておく．その上で，原点からのBFSにより最短経路を求めることが出来る．
lenとrinの座標をまとめて持ちながらBFSする．
5/23
今いる位置と持っているお金を状態にもちながらBFSする．移動の際には護衛を雇うか雇わないかの2通りが考えられるので，それで襲われる盗賊の数の最小値を更新していけば良い．
5/24
実は各色のボール個数の偶奇がそのまま答えになる(つまり消せずに余ってしまうボールはないことになる)．
5/25
5/26
CF #354 Div2に参加
ABCDの4完．Dが実装がめんどいけど結局BFSするだけだったので楽だった．なかなかいい順位だったのでレートはめっちゃ上がった．やっぱり毎回4完出来るようにしたい...
TCO 2016 Round 2Bに参加
Easyがむずかしくてダメダメだった，逆を考えて包除原理的に考えるのが楽だったらしい...本番中，必死に数式をいじってたけど，そもそもその考え方が間違っているのに終わってから気づいて，徒労だった．
5/27
appleを食べても辻褄が合うかどうかを手前から調べていき，問題なければそこをappleにして更新していくという貪欲．1つ配列を用意し，「その位置を終端とするリストの中に現在appleが何個含まれるか」という値を保存することで，計算量をに落とせる(submission)．
5/28
頂点個の木に対して，それぞれの頂点同士をつなぐパス(唯一に定まる)の長さが奇数か偶数かが与えられるので，そのような木を構成できる場合には辺の構成を，構成できない場合には-1を答える問題．0を根とした時に，その頂点の高さの偶奇の関係で頂点間パスの長さの偶奇も決定される(例えば深さ1と深さ3の頂点をつなぐパスを考えるとどうやっても偶数しか無い)．なので，まずは絶対的にありえない状況を排除(自分自身との距離は0なのでそこは偶数，対象になっていなければおかしい)する．そして，0との距離が奇数の頂点を0と繋ぐ．そして0との距離が偶数のものを前の段階で繋いだ頂点に繋げば良い(前の段階で繋いである頂点が1つもなければ失敗)．このようにして構成したものが，全ての条件を満たしているか，全頂点間の最短距離を構成した辺から計算して判定することで可能になる(submission)．
GCJ 2016 Round 2に参加
aAb---d-と解いた．Aに関しては，優勝者を決め打ちするととグーチョキパーの人数が確定するのが分かったので，あとはそれを再帰的によびながら辞書順最小になるように答えを求めた．これがなかなか早く思いつけたのがよくて，その後は結局largeは解けなかったけどsmallで点を稼いで901位に入れた．Round1をギリギリで通過していたこともあって，1000位以内でTシャツはすごく嬉しい．来年はRound3目指して頑張る．Round1の解けなかった問題たちと，Round2の3問をそのうち復習しておこう．
5/29
しゃくとり法みたいな感じで増加区間を探して，区間の長さに対して
を足していく．
wの昇順，hの降順でソートするのが全ての鍵だった．あとは，hだけに対してのLISでも良いし，SegTreeを使ったDPの更新をしても良い．
5/30
X社とY社の水道料金を愚直に計算し，minを取れば良い．
