ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

AOJ 2005 - Water Pipe Construction

ワーシャル-フロイド法

問題
提出コード

解法

設置コストを辺の距離とみなすと、結局何かしらの距離の最小値を求めるような問題に帰着できそうな気がします。ここで、制約に注目すると、Nが100以下であり、[tex:O(N3)]が通ることから、ワーシャルフロイド法が使えそう、ということがわかります。
さて、問題の条件を満たすための条件は、sからg_{1}、sからg_{2}に向かう経路が存在することで、これらの経路の距離の総和が最小になればよいです。
ここで、上の経路に含まれる以外の辺は絶対に使わないので、以下のような2パターンのみに限定できます。

f:id:emtubasa:20190426145305p:plain

1つめは、図の左側のような、どこかの頂点までは、s->g1,s->g2共に同じ経路をたどり、iで分岐するようなパターンです。
2つめは、図の右側のような、s->g2の経路の途中にそもそもg1が含まれているパターンです(もちろん、g1とg2が逆でもよいです)。しかし、これは、g1からg1の距離を0とみなしてしまえば、g1と分岐点iが一致したとみなすことができます。

ということで、あとはありうる分岐点がN通りあるので、それぞれについて、s->i,i->g1,i->g2の距離の総和を求め、その最小値を取ればよいです(もちろん、そもそも経路が存在しなければ無視します)。

感想

解法のポイントに気づいて注目すると、考察がすぐに終わるパターンですね。今回は、分岐点と、制約のN \leqq 100の部分でした。
350点問題でもこのような問題があるので、サクサクといていきたいですね。

AtCoder Petrozavodsk Contest 001 D - Forest

Union-Find木 リベンジ

問題
提出コード

解法

まずは、全ての木を連結にするには、それぞれの木について、頂点を少なくとも1つ選んで連結にする必要があるので、それぞれの木から、最もコストが小さい点を1つずつ選んでおきます。
また、コストを最も少なくして全てを連結にするには、N頂点の木にする必要があります。ので、辺はN-1-M本新しく張る必要があり、そのためには(N-1-M) \times 2個の頂点を使う必要があります。
が、それぞれの頂点は1回ずつしか選択できないので、(N-1-M) \times 2 \gt Nの場合、全ての木を連結にすることはできません。
逆にそれ以外の場合は、最初に選んだ点の個数をXとして、(N-1-M) \times 2 - X個の頂点を、X個に含まれない頂点の中から、コストが小さい順にとっていけば、それらの頂点をうまく組み合わせることで、全ての木を連結にすることができます。

解法

解説を聞くと、あーなんだそれだけか、となるような問題でした。この手の問題を安定して解けるようになりたいですね。

AtCoder Petrozavodsk Contest 001 C - Vacant Seat

二分探索

問題
提出コード

解法

インタラクティブ問題なので、二分探索を考えていきます。
まずは、どこか1つの席の情報がわかっていないと何も始まらないので、0番の席を特定します。
ここが空席ならばその時点で終了、女性だったならば、男性だった場合と真逆のことをかんがえればよいので、男性だった場合について考えていきます。
0番目が男性だった場合、1番、2番…の席に、男女交互に配置すると下の図のようになります。

f:id:emtubasa:20190426093452p:plain

ここで、青が男性、橙が女性を表します。
このままだと、図のように0とN-1番目の席に座る人が、どちらも男性になってしまいます。
なので、これを回避するために、(0,N-1]の区間のどこかしらに、空席が存在しているはずです。

次に、i番の席の情報を特定したとします。空席ならばその時点で操作が終わるので、それ以外について考えます。
上の図で割り振った男女男女…は、席の番号が偶数ならば男性、奇数ならば女性になっているはずです。
i番目の情報は、この偶奇に対する男女と一致しているか、していないかの2択です。

  • 一致している(iが奇数ならば男性、偶数ならば女性)場合
    この場合、0からiまでの席は、 空席が1つもなく、男女交互に座っている、もしくは空席が存在している、の2パターン存在しています。
    つまり、この部分は、空席が存在していない可能性があるので、この区間を今後探索するのは効率が悪そうです。
    一方、i+1からN-1までの席は、最初の状況と同じで、もし仮にi+1以降も男女交互で並んでいるとすると、N-1と0番目の席について矛盾が生じます。
    ということは、少なくとも1つはこの部分に空席が存在しているはずです。

f:id:emtubasa:20190426095142p:plain
i=3だった場合

よって、結局は(i+1,N-1]について、同じ探索を行えばよさそうです。

  • 一致してない(iが奇数ならば女性、偶数ならば男性)場合
    このパターンは先ほどと逆の状況になります。
    iからN-1の区間は、男女交互に配置しても条件を満たすことができるため、空席が存在するかもしれませんし、存在しないかもしれません。
    逆に、1からi-1の部分については、男女交互に配置すると矛盾が生じるので、空席が確実に1つは存在します。

f:id:emtubasa:20190426095753p:plain

よって、こちらのパターンについては、(0,i-1]について同じ探索を行えばよさそうです。

上の状況を、どちらのパターンにころんでも効率よく行うために、iを区間のちょうど真ん中にしてあげるとよいです。ということで、結果二分探索を行えばよいことになります。
結局、やることは

  1. 0番の席について調べる。調べるべき区間を(0,N-1]とする。

  2. (l,r]について調べる。x = (l+r)/2についてクエリを出して、その部分が、仮にlから男女交互に配置していった場合の情報と一致するかどうかを調べる。一致したら、次に調べる区間を(x,r]とし、そうでなければ(l,x-1]とする。空席が見つかるまでこれを繰り返す

ということを行えばよいです。

感想

久々のインタラクティブ問題でした。AtCoderだと初めてかもしれないです。
あんまり経験がないので、インタラクティブといえば二分探索っぽいことをしたくなります。そこから考察をさらっと終わらせたのはよかったのですが、例によってデバッグで時間をかけました。
xorを利用して条件の一致を判定したので、その部分を丁寧にやる必要がありましたね…

AtCoder Petrozavodsk Contest 001 B - Two Arrays

条件の作成

問題
提出コード

解法

a_{i}とb_{i}を同じ数字にそろえる場合に、3パターンの選択の方法があります。

  • a_{i}を選び、b_{i}以外を選ぶパターン
    a_{i}はa_{i}+2になり、b_{i}は据え置きです。
    この方法だと、a_{i} \lt b_{i}かつb_{i}-a_{i}が偶数の場合にそろえることができます。

  • a_{i}とb_{i}を選ぶパターン
    a_{i}+2,b_{i}+1になります。ので、a_{i} \lt b_{i}の場合、これを行うことでそろえることができます。

  • a_{i}以外を選び、b_{i}を選ぶパターン
    a_{i},b_{i}+1になります。
    a_{i} \gt b_{i}の場合にそろえることができます。

これらより、a_{i} \lt b_{i}の際は、2つめの方法でいくらでも数を調整することができますが、a_{i} \gt b_{i}の際は3つめの方法を使うしかありません。
しかし、3つめの方法を利用するには、その回数分だけ、同時に1つめのパターンも行うことになります。
ということで、結局は、1つめのパターンと3つめのパターンを同時に行い、3つめのパターンが必要な部分の数を全てそろえた後、残った部分を2つめのパターンを利用してそろえる、というのが確実な方法になります。
ここで、3つめのパターンを行う必要がある回数は、\sum max(0,a_{i} - b_{i})です。1つめのパターンは、a_{i} \lt b_{i}である限り行うことができるので、最大で \sum max(0,\frac{b_{i} - a_{i} }{2})回行うことができます。
なので、結局問題の条件を満たすかどうかの判定は、

  • \sum max(0,a_{i} - b_{i}) \leqq \sum max(0,\frac{b_{i} - a_{i} }{2})

を満たしているかどうかと一致します。

感想

この問題、大学の友人との勉強会でも出題したのですが、説明が難しすぎます…
結局調べるべきことはシンプルなのですが、その発想に至るまでの経緯が少し複雑でした。

ABC102 D - Equal Cut

しゃくとり法 累積和 二分探索

問題
提出コード

解法

パッと見とっつきにくい問題。
まずは、3つのうち、どこか1つの仕切りを固定して考えるとして、どの仕切りを固定すると見通しがよくなるかを調べます。

f:id:emtubasa:20190425010205p:plain

まず、右端の仕切りを固定することと、左端の仕切りを固定することによる見通しの良さに差はありません。
ので、端の仕切りを固定したパターンと、真ん中の仕切りを固定した2つのパターンで見比べていきます。

  • 端の仕切りを固定したパターン
    このパターンでは、最終的な4つの数列のうち、1つの総和が確定します。今回は、右端の仕切りを固定して、Sが固定されたと考えます。
    すると、残った1つの長い数列を3分割して、うまく最適解を求める問題に帰着できます。が、この問題を解くのはあまり効率的ではないです。

  • 真ん中の仕切りを固定したパターン
    このパターンでは、数列が2つにわかれ、それぞれで、もう一つずつ仕切りを置く形になります。
    この時の最適な2つの仕切りの置き方を考えます。このとき、abs(P-Q)、abs(S-R)がそれぞれ最小となるように仕切りを置けばよいです。
    簡単のためにP \lt Q、R \lt Sとします。実際の求める値のパターンは S-P,S-R,Q-P,Q-R の4パターンであり、どのパターンでも、abs(P-Q),abs(S-R)が最小になるようにすることで、値を小さくすることができます。こちらのパターンの方が、先ほどの仕切りの固定の仕方よりも見通しが良くなります。

ということで、真ん中の仕切りを固定して、そのパターンについての残りの2つの仕切りの置き方を探し、これを全探索すればよいです。
ということで、あとは、とある数列に対して、それを二分したときの、それぞれの総和の差の絶対値が最小になるような仕切りの置き方を求めることができればよいです。
abs(P-Q)が最小となるようなP,Qの分け方は、2通りの方法で求めることができます。どちらの場合も、累積和をあらかじめ計算しておく必要があります。

  • 尺取り法で求める
    累積和は、数列の要素が増えるにつれて単調増加します。ので、尺取り法を用いると、rが数列の右端だった場合に、その数列の仕切りの最適な場所lが、O(N)で前計算した後、O(1)で参照できます。lとl+1を見比べていって、lの方が差の絶対値が少ない場合、rに対するlが求まったことになります。

  • 二分探索で求める
    abs(P-Q)が最小になるということは、P,Qは、\frac{(P+Q)}{2}に最も近い値になっているはずです。ということで、累積和がこのような場所になる部分を二分探索で求めれば、O(logN)で求めることができます。

これらのどちらかを利用すると、真ん中の仕切りをある位置に固定したときの、残り二つの仕切りの最適な配置がO(1)もしくはO(logN)で求めることができるので、あとは真ん中の仕切りの位置を全探索していけばよいです。

感想

一見とっつきにくい600点問題ですが、丁寧に最適なパターンを調べていくと、解ける…ような問題です。累積和で前計算＋αというパターンはよく見るので、抑えておきたいです。

AOJ 1156 - ちょろちょろロボット

ダイクストラ法

問題
提出コード

解法

マス目を移動するコストが移動方法によって異なる迷路問題なので、ダイクストラをします。
dis[i][j][k] = マス(x,y)で、kを向いているような行き方の中でのコストの最小値
とします。あとは、現在のマス、方向、コストを1まとめにし、ダイクストラ法を利用して上の配列を埋めていけばよいです。
4方向の処理を丁寧に行っていけば、バグりにくい…はずです。

感想

バグらせなくて安心しました。ICPCの問題は、考察より実装面で重いものが多いので、感想や解法で書くことがバグ関連の話しかない気がしますね…

AOJ 1155 - 如何に汝を満足せしめむ？ いざ数え上げむ…

構文解析

問題
提出コード1
提出コード2

解法

構文解析です。
変数がP,Q,Rの3種類しかないので、それぞれについて、値が0,1,2だったパターンの3^{3} = 27通りを調べればよいです。
構文解析の処理を1つの関数にまとめて再帰をしている方法が提出コード1、それぞれの役割に分担して行っているのが2です。
とりあえず普段の方法が提出コード1のパターンだったのでそちらを書き、バグりにくい方法をしらべたところこのような記事が見つかったのでこちらも練習で書いてみました。が、構文解析らしいバグではなく、別の部分でバグを発生させ、1時間以上溶かしました…
基本的にはどちらのコードも、文字列を前から見ていって、文字ごとの処理をガリガリ実装していけばいいです。やはり、構文解析といえば、現在見ている位置関係のバグが発生しやすいので、そこに注意しながら書きます。演算の処理も、おとなしく言われた通り実装するしかないです。

感想

本番は、どっちで書くか悩み中です…が、実際、機能ごとに関数が分かれている方が見やすいといえば見やすいので、しばらくは提出コード2の方で練習してみようかなと思います。