ABC075 D - Axis-Parallel Rectangle
解法
まずは、4点を決めます。同じ頂点を選んでも問題ないです。
そうしたら、その4点を含むような長方形のうち最小のものを求めます。
この長方形の座標は、
右、上:それぞれ4点のx座標、y座標のうち最大のもの
左、下:それぞれ4点のx座標、y座標のうち最小のもの
となります。
ここまできたら、あとは、この長方形の中に含まれている点の個数を数えます。
これは、すべての点に対して、先ほどの上下左右の範囲内に収まっているかどうかを調べることで判別できます。
含まれている点の個数がk個以上だった場合、長方形の面積の最小値を更新します。
(上 - 下)×(右 - 左)
によって求めることができるので、この最小値が答えになります。
あとは、最初に決める4点を全探索すれば、で求めることができます。
ABC074 D - Restoring Road Network
解法
まずは、答えが-1、つまり入力された値で条件を満たすグラフを作成できるかどうかの判定をします。
これは、ワーシャルフロイド法を用いて行うことができます。行った結果、すべての距離が更新されることがなかった場合、条件を満たすグラフを作成することができます。
続いて、道路の距離の和を求めます。小さい方から、貪欲に決めていきます。
まずは、全ての種類の辺を、つながっている2つの頂点と共に一つの配列に格納します。そして、辺の距離の昇順でソートを行います。
あとは、前から見ていきます。イメージはエラトステネスの篩です。
まずは、一番小さい距離の辺を取り出します。これは確定で使うことになりますので、答えの合計値に加えておきます。
この辺が、iとjを繋いでいるものだったとすると、i,j以外の頂点kを持ってきたときに、
(iとjの距離)+(jとkの距離) = (iとkの距離)
であったとき、頂点iとkの辺をカウントしてしまうと、ダブりが発生します。ので、iとkの辺を配列から取り出した場合に距離の合計に加えないようにフラグを立てておきます。
この操作を、右辺が(jとkの距離)の場合も含めて、kについて全探索します。
この操作が終わったら、辺を格納した配列の次の要素を見ます。それが先ほどフラグを立てた辺でない場合は今と同じ操作を、立てた辺であれば操作を何も行わずにスキップをします。
これを、全ての辺について行っていきます。
これを繰り返すことで、最終的な辺の距離の和が求まります。
ABC074 C - Sugar Water
解法
全探索が間に合わないので、ある1箇所だけを探索せずに計算でぱっと求めるパターンです。
操作1~3を探索し、操作4はある1~3のパターンに対する最善手を計算によって求めます。
操作1をx回、2をy回、3をz回行ったとします。
このとき、水は100(ax+by) [g]、砂糖は cz [g]存在しています。これをそれぞれw [g]、s [g]とします。
そして、この場合の操作4を行うべき回数pは、
min(f-w-s,ew/100-s) / d 回
となります。
min()の左側が、合計質量の残りグラム数、現在の水にたいして溶かすことのできる砂糖の量です。
この中の小さい値を超えないギリギリまで、操作4を行うのが正解なので、上のような式になります。
あとは、濃度が100(s+pd)/(w+s+pd)によって求められるので、(x,y,z)について全探索を行い、濃度が最大になるようなパターンを探します。
コーナーケースが存在します。濃度が0%になるのは、砂糖が0[g]の”水”に対してです。水と砂糖どちらも存在しない場合は、そもそも濃度が定義できないので、あやまって出力しないようにしましょう。このケースに気づかず時間を溶かしました。
ABC073 D - joisino's travel
解法
まずは、頂点数が200しかないので、が間に合います。ので、とりあえずワーシャルフロイド法を適用し、それぞれの頂点間の距離の最小値を求めておきます。
そして、通りたい頂点数は8しかないので、全探索が間に合います。ので、c++であれば、next_permutationを利用して、順列を1つ1つ作成し、その順番に頂点を通った場合の距離を先ほどのワーシャルフロイド法によって求めた値から計算して、最小値の更新を行っていけば、答えがもとまります。
next_permutationを行うときはdo-while文を利用するといいかと思います。通る頂点をあらかじめ昇順でソートしておくことや、ワーシャルフロイド法を適用するにあたって初期化がであること、0-indexedか1-indexedかの確認など、基本的な部分に注意しましょう。
第4回 ドワンゴからの挑戦状 予選 B - 2525文字列分解
解法
シミュレーションをしていきます。
現在の文字列をSとします。その中で作成できる最長の2525文字列をSから取り除き、残った中でまた文字列を取り除き…と繰り返していきます。
最終的に、Sが空になれば完了です。
Sの文字に対し、残すか取り除くかを決定していきます。
次に取り除くべき文字をtとします(初期はt='2'です)。
Sの先頭から順番に見ていき、tと一致するものがあったらそれが取り除く文字です。tと一致しなければ残す文字列です。
tと一致する文字列があったら、tを逆にします(2→5、5→2)。そしてこの操作を繰り返します。
最後まで操作をし終えた時、t='5'であった場合、取り除いた文字列は2525文字列ではない(最後に2がきているはずです)ので、残す文字列に'2'を1つ移動させてあげます。
そして、残った文字列が'2'もしくは'5'だけになった場合、そしてtと一致する文字列が存在せず一度も操作が行われなかった場合は失敗となり、-1を出力します。
Sが空になった場合は、Sの先頭から最後まで見る操作を行った回数を出力すると答えになります。
第4回 ドワンゴからの挑戦状 予選 D - ディスクの節約
問題
提出コード
なんかこの問題の解説すごくむずかしいですね
解法
Nの制約が少ないので、現在のメモリの状態に対していろいろすることを考えます。ということで、bitDPです。
2進数に対し、小さい桁から順番に頂点の番号を割り当てていきます。
例えば、101だと、頂点1と3が書き込まれたような感じです。
dp[S] = 状態Sになるような、タスクの処理の手順のうち、"必要最大ディスク量"の最小値
とすると、答えはdp[1]となります。ここから、何も存在しない初期状態に向けて戻してあげることを考えます。
また、有向木の葉の部分のみがディスクにあるような状態(立っているビットが1つのみの場合)のdpの中身は、その頂点のディスク量そのものになるので、あらかじめ初期化をしておきます。
さて、ある状態Sになるには、そのSの中の頂点を1つ選び、その頂点の子すべてと置き換えてあげる作業が必要になります。
置き換えた後の状態をTとします。
ここで、必要最大ディスク量は、ある手順でSから初期状態に戻した時、その手順の中で最も大きかったディスク量になります。
すると、dp[S]は次のように書くことができます。
dp[S] = min{ max(Sから選んだ頂点とTに含まれる全ての頂点のディスク量の総和, dp[T]) }
Sから状態Tにうつるときに一番使用ディスク量が増える瞬間は、Tに含まれる頂点とTにうつるために選んだ頂点が同時に存在するときです。その後の手順についてはdp[T]を見れば最大使用量がわかるので、その二つのうち大きな値をとれば、SからTに遷移したと仮定したときの最終的な必要ディスク量がわかります。
これをすべてのTに対して調べて、最小値をとればよいです。
ということで、この遷移を繰り返すと、答えを求めることができます。
