2016/9 solved(1)
9/1
CSAcademy Tasksのチュートリアル的3問。3問目は個の点を始めにqueueに入れてBFSすればよい。
9/2
どうやら難しく考えすぎていたみたい。最大値を保存するSegtreeeと最小値を保存するSegtreeを用意して左から順にみて区切れそうかを調べるという方法をとった。
9/3
9/4
問題文の図のように青のテーブルと赤のテーブルがあるとして、1番の人が青に座るとした時に、1番と知り合いではない人は必ず赤のテーブルに付かなければならない。そして、その赤のテーブルに付いた人たちと知り合いではない人は必ず青のテーブルに付かなければならない。...と、知り合いではないという情報を辺にしてBFSを行う。途中で色の衝突が起きてしまったら、答えはNOになる。一通り色が決まったら、2頂点間について色が同じなら知り合いかどうかを判定して最後にYES/NOを答えると良い。
AGC 004に参加
ABCの3完。4問目がどうしてもできない...Cを思いつけたのは良かったけど、時間をかけすぎだったかもしれない。
9/5
1を自己ループに変えて、根付き木として考える。根からの距離が遠いほうから貪欲にちょうどKになるように頂点を切ってつなげていく。その頂点からBFSすると既に訪れた頂点を更新でき、重複を防いでで解答できる(submission)。
9/6
まず、s[i]からs[j]までが全て文字cになる確率をdp[i][j][c]として、このDPを計算する。そして、この確率を利用しながら期待値を計算していく。いくつかの同じ文字が連続する区間に分けて考えることができるので、E[i][c]=i文字目まで見終わった、そのi文字目はcであるときのスコアの期待値を保存しておくと、次の遷移が必ず違う文字でなければいけないということを上手く考慮ながら期待値を更新していくことが出来る。最終的に答えるものは、n文字目まで見終わって最後の文字をa-zまでは独立に足し上げてしまうことが出来る(submission)。
9/7
HourRank 12に参加
自明部分しか出来なかった。2問目はとてもよくありそうな感じの問題だったのに全然手が出なかった...
9/8
(なにもしてない)
9/9
自分の開放はAGC 002 D的な感じでparallel binary search + Union Findをしていく方法を取った。クエリを処理する際には、橋がどんどん減っていくので後ろから処理していくようにする(submission)。
9/10
(なにもしてない)
9/11
ARC 061に参加
CDの2完。EはTLE除去できず...
9/12
9/13
式の形を見て、立っているbitの数に一致するなあというのにすぐ気づいた。そうすると個数は組み合わせで求めることが出来る。総和は、各桁ごとにそのビットが立つ場合の数を数え上げて足すとよい。
9/14
解説放送では駅と連結された同じ鉄道会社の成分の二部グラフとして考えて、1からnへの距離を求めた後にそれを2で割るという解法が取られていた。連結成分の効率的構成方法をいまいち思いつけなかったので、解説にある通り(現在いる駅,最後に利用した鉄道会社)の拡張した頂点での最短経路を求めることにした。本番の提出はDijkstraとかじゃなく、よく見たらただのBFSを書いててそりゃ通るわけ無いでしょという感じだった。各駅ごとに、最後に利用した鉄道会社はたかだかその駅に繋がっている路線の個数個しかないので、この拡張グラフの頂点数がになることは想像できる。ただ、この頂点間に辺を張るとなった時にただ思考停止で辺をはると辺の数が
になってしまい、Dijkstraが間に合わない。そこで、解説では改札という概念を導入し、乗り換えという動作を改札を出て入るという動作に帰ることで辺の数を減らした。これによってなぜ辺が減らせるのかイメージがつきにくいかもしれないが、ある駅で例えば複数の路線があるときに、その乗り換え口をハブのような形にして1箇所にまとめたと考えるとイメージしやすい(ちょうど東京の地下鉄とかをイメージするとわかりやすいかも)。これによって辺の数が
になり、十分間に合う。ただ、拡張した頂点をそのまま使うのがmapなどを使うことになり時間がかかってしまうので、一度整数に落とし込んでからdijkstraをしないと時間がかかって微妙に間に合わなくなってしまうので注意...(submission)。
