2016/11 solved(1)
11/1
CF #378(Div2)に参加
ABCDの4完だった。codeforcesは実装に罠が多い問題が多いような感じがしてきた。今回はちゃんと出したやつを全部通せたけど、実装方針とかは場数がどうしても必要になる感じがある。ここで紫に到達。
時間、個数、座標のめんどくさいDPを書いてハマりまくってしまった。何個目まで取ったか、個数だけでできるらしい...
最初、命令を変える部分はマスが書き換わるのだと勘違いしていて、これ状態数やばいな...と思ってたけどマスは変わらずにその都度命令を与えるので、現在位置とロボットの向きを保存してBFSすればよい。
ログをIDごとに分けておいて、inとoutの区間をペアで保存しておく。ID番とID
番を比べながら区間の被覆を見て累計をカウントしていく。
11/2
貪欲に消せるところ探していけば良い。消せる位置の候補は、行または列が同じならそのうち間の叩けるどこか1箇所よく、どちらも一致しない時は2箇所が叩けるか見て、その2箇所を叩いてみる。
陸路だけ使うときと海路だけ使うときの最短経路をそれぞれワーシャルフロイドで求めておく。そして、陸路の結果から島の形が分かるので、どの町が陸路でつながっているかを保存しておく。最後に、dp[i][j] = z[i]まで集配が終わり、そのとき船は町jにあるときの最短コストを計算していく。スタート地点が1で固定だと勘違いしてちょっと時間を溶かした...
11/3
現在位置、向きを考慮すれば100*100*4通りしかないのでいつかループに入ることになる。そのループを見つけて、最終位置を計算する。
行列累乗で解く。
凸法を作って、凸包の長さ+直径Lの円周が最小になる。例で図が与えられるので分かりやすかった。
蟻本見ながらキャリパー法を実装した。
累積和をソートして尺取するという方針にたどり着くのが凄い難しかった。
11/4
桁DPで数え上げ。
s[i],s[j]の順で繋いだときにいくつ節約出来るかを保存しておいて、bitDP。
11/5
個数制限のないナップサック問題と同じようなDPをsingleとallの魔法別々に行い、ダメージxを与えるための最小コストを求めておく。それが終わったあとで、allで与えるダメージをyで固定すると、それぞれのモンスターにsingleの魔法を使う必要のコストが決まるので、全体にかかる最小コストを更新していけばいい。
インデントの個数を全探索する。
11/6
disposeの意味を完全に逆に解釈していた。ミサイルを順番に配置していくのかと思ったら、順番に取り除いていくということだった(まあ問題タイトル的にそうでしょという感じがするけど)。あとはミサイルの個数ぶんループをして、ループあたりの処理をSegtreeを使ってで処理した。
メッシュ状に領域にカットして、あとは領域がいくつあるかをBFSで数えた。
11/7
3次元のフィールドを用意して、愚直にシミュレーションした。
11/8
dp[from][now][carrot]=fromから来てnowにいるとき人参をcarrot個手に入れるためにかかる最小距離を保存しながら更新していき、限界まで更新できたところが答えになる。
11/9
11/10
その都度、最少人数を貪欲に決定できる。
貪欲に出す手を決めていく。
向かい合う2面を全探索していく。その2面を決める(片方の面を固定し、もう片方の面を4つ向きぶん試す)と、立方体の角に来るべき色が全て決まるので、側面の4つにどのような色を持つ面が来るべきかがそれぞれ決まってくる。そのような面をmapで管理する。その管理にあたって、回転によって一見違う色の組が同じであったということを避けるために、解説にもあるが色の組を正規化しておく(具体的には4つあるうち、辞書順最小を選んでおく)。すると、各面に対して、使える面の個数が分かるので、あとはその向きと側面に同じ色の組が何個有るかを考慮しながら何通りありえるかを掛け算して、それを足し合わせていく。最後に重複を取り除かなければいけないが、向かい合う2面が立方体には3組あるので、同じ立方体を3回数えてしまうことになるので、最後に求まった組み合わせ数を3で割ることで答えを出せる(submission)。
蟻本のアリ問題と同様の考え方で、時間は簡単に計算出来る。では、最後に落ちる人の名前は何かということを考えるとなると、もし、正の方向を向いている人が最後に落ちる時は、それよりも座標が大きいところにいる負の方向を向いている人の数だけindexが右に移動することになる。これは逆の場合でも言えることで、これによって線形オーダーで名前を求めることも出来る。
同じ数字は連続しているので、問題の例にあるような数列に対して2 2 4 4 4 4 1 3 3 3というような数列でSegTreeを初期化しておき、あとは端の区間を別に処理して間の区間をSegTreeの最大値クエリに投げた。
11/11
xとyの最大公約数Gに対して、x-yもGで割り切れるから下2桁の組み合わせの差の絶対値のGCDを考えればいいかというとこまでは考えついてたけど、そっからその求まったGCDの約数が答えになりうるから、あとはそれを順番に大きい方からチェックすればいいだけだったけどそこが時間内に詰められなかった(submission)。
11/12
11/13
vectorで解いた。
隣同士が反転している個数がそのまま答えになる。
11/14
基本的なアイデアとして、解説と同じなのだが、自分の答えの導出の部分だけなんか解説とは違った。ある橋で2つの部分に分けるのは良いが、その分けた方に葉が個あるときにはそれにかかるコストはその端の端点の接続している辺の数が2なら
(橋をないものとして考えるとその端点も新たに葉になるため)、2より大きいなら
回の結合が必要になる。また、uの次数が1だけを見ればいいのは、二重辺連結成分分解して得られるグラフが木で、その辺は全て橋になるので、かならず次数が1の頂点が出てくることがわかっているからである(submission)。
まず二重辺連結成分分解する。するとこれは木になり、もともとの頂点がグループ化されて一つの頂点になっている。そして、AからCへ行くときにBを中継して同じ道を通らないようなものがあるかを知りたい時は、この木に変換されてグラフ上での最短距離(A,C)が(A,B)+(B,C)に等しいかどうかを見れば良いことになる。なので、木上の最短距離を高速に求めるために自分はLCAを使った(submission)。
円と円の交点を考えて、その点が他の円に覆われていなければそのエリアが見える→その円が見えると考えることができるので、見えるかどうか判定すべき個数は各円に対して個に抑えることができる。円と円の交点は、直線の方程式を出してからその式を円の方程式に代入して解の公式で求めるというのをかいた。他にも誤差制約が厳しくてバグ取りがつらかった。
11/15
解説どおり実装した。はじめはsetで縦の区間と横の区間を管理してそれらをマージしていこうとかいろいろやってたけど重すぎた。この1つのマスに対して4近傍をデータ構造で確かに実現できて、面白い問題だった(submission)。
