ツバサの備忘録

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

AOJ 2642 - 夕食

条件の作成 リベンジ

問題
提出コード

解法

T日間で、x_{0}, x_{1}, x_{2}, \dots x_{i} \dots x_{T-2}, x_{T-1}日目に自炊を行ったと仮定します。
このとき、得られる幸福度は以下のようになります。
\displaystyle \sum C_{i} - \sum_{k = 0}^{T-1}C_{x_{k}} + \sum_{k = 0}^{T-1}(Q + 2k- (x_{k} - 1))P
はじめの2つの項が食堂で食べることによって得られる幸福度、最後のΣの部分が自炊によって得られる幸福度になります。
これを式変形するとこうなります。
\displaystyle \sum C_{i} + \sum_{k = 0}^{T-1}(Q + 2k)P - \sum_{k = 0}^{T-1}(C_{x_{k}} + P(x_{k} - 1))
これを整えると、以下のようになります。
\displaystyle \sum C_{i} + (Q + T - 1)TP - \sum_{k = 0}^{T-1}(C_{x_{k}} + P(x_{k} - 1))
よって、自炊を行った日数Tを決め打ちしたときの幸福度の最大値は、\displaystyle \sum_{k = 0}^{T-1}(C_{x_{k}} + P(x_{k} - 1)) を最小にしたときになります。
この値は、X_{i}の選び方に依存しますが、C_{x_{k}} + P(x_{k} - 1)を昇順にソートし、小さい順に選んでいけばよいです。
あとは、自炊を行った日数を全探索し、幸福度の最大値を求めれば答えとなります。

感想

とりあえず条件を立式して考える、できたとしても上手く答えにたどり着くかどうか微妙なところですね…

AOJ 1168 - ぐらぐら

深さ優先探索(DFS)

問題
提出コード

解法

愚直に、それぞれのピースに対して条件を満たしているか確認していきます。
ピースそれぞれを頂点、上下で接しているかどうかを辺としたグラフを作成していき、あるピースに対してのバランスを調べる際は、そのグラフを辿って見ていきました。
前計算で、それぞれのブロックの個数、ブロックの重み(1)×横軸の座標の合計値、 X_{L} , X_{R}を計算しておきます。そして、あるピースについてのバランスを調べるときは、上記の値を用いて実際の重心を計算し、 X_{L} , X_{R}を超えるかどうかを調べることになります。

AOJ 2511 - 沈みゆく島

最小全域木(クラスカル法)

問題
提出コード

解法

まずは前から見ていき、移動経路が確保できなくなるタイミングを探します。
そして、その直前からさかのぼって行き、今構築済みの木に最小限の辺を足して、全域木になるようにしていけばよいです。
基本的には最小全域木と同じ考え方で辺を追加していけばよいです。が、同時刻に島が沈む場合の処理が少々面倒でバグを埋め込みやすいので注意する必要があります。この部分さえ注意すれば、あとは上記の方法でグラフを構築していけば答えを求めることができます。

感想

バグを埋め込みやすいと記述している、ということは自分はバグらせたということです。…

みんなのプロコン2019 D - Ears

動的計画法(DP)

問題
提出コード

解法

適当に実験をすると、散歩後の石の個数は、座標が小さい順に、次のような区間でわけることができます。

  • 石が0個の区間

  • 石の個数が2個以上の偶数の区間

  • 石の個数が奇数の区間

  • 石の個数が2個以上の偶数の区間

  • 石が0個の区間

ただし、それぞれの区間の幅が0の可能性もあります。
ということで、今現在どの区間にいるか、という情報を持たせつつDPを行います。上の5つのパターンに、上から0,1,2,3,4と番号を割り振ります。
dp[i][j] = i番目の耳まで見て、そこがパターンjだったときの、操作の最小値
とすると、
b_{ij} = i番目の耳がパターンjだった際にかかる操作回数
を用いて、
dp[i + 1][j] = min(dp[i][k] + b_{ij}) (だたし、k \leqq j)
と計算することができます。
b_{ij}は、

  • パターン0,4: A_{i}

  • パターン1,3:A_{i}が奇数なら1,0なら2,偶数なら0

  • パターン2:A_{i}が奇数なら0,偶数なら1

と計算することができるので、あとはDPの遷移を行うと、min(dp[L][j]を求めることで答えとなります。

感想

当時は解けなかったので、成長を感じますね...

AOJ 1619 - 弁当作り

bitDP 全探索 リベンジ

問題
提出コード

解法

制約に n \times m \leqq 500と書いてあります。これがすべてです。
nが大きいパターンとmが大きいパターンで場合分けをします。
\sqrt{500} \lt 23なので、実はmin(n,m)が、簡単にビットで情報を持つことができます。

  • nが小さいパターン
    全探索をします。
    それぞれの材料について、その材料を必要としているレシピの集合を前計算で求めておきます。
    そして、今回作成するレシピの集合sについて、先ほどの前計算したものとそれぞれ積集合を計算し、その結果含まれる要素の個数が全て偶数であれば、sのレシピの集合を一度に作成することができます。このsのうち、要素数が最大のものを求めればよいです。

  • mが小さいパターン
    bitDPをします。
    dp[i][s] = i番目までのレシピを作成し終えて、材料の余りがsになるようなレシピの作成方法のうち、作成したレシピの個数の最大値
    とすると、i番目のレシピを作成した際に使用する材料の集合をp_{i}として前計算しておくことで、
    dp[i + 1][s] = max(dp[i][s], dp[i][s \bigtriangleup p_{i}] + 1)
    という遷移で計算することができます。
    s \bigtriangleup p_{i}はsとp_{i}のxorをとればよいです。
    こうすると、dp[n][0]が答えになります。

    あとは、この計算を繰り返せば答えが求まります。

    感想

    制約によって場合分けをする発想が無かったので解けませんでした…(それぞれについては、この制約ならいけるのになぁみたいな感じでなんとなくは考えていました)。

COLOCON -Colopl programming contest 2018- C - すぬけそだて――ごはん――

半分全列挙

問題
提出コード

解法

あらかじめ、ある数xとyが同時に存在しうるか、を調べておきます。
使用できる数を、前半の20個と、残りの2つの部分に分け、それぞれに処理をしていきます。
最終的には、前半の状態を1つ決めた時の、後半の場合の数を高速に計算して、前半の状態を全探索します。
後半部分について、前計算で以下のようなDPを行います。
dp[S] = 後半の数から選んだ集合Sの中でのカードの選び方
iを、Sに含まれる最大の数とします。Pを、S \setminus \{i\}の中で、iと同時に選べる数の集合とします。すると、
dp[S] = dp[S \setminus \{i\}] + dp[P]
というようにして計算を行っていくことができます。
あとは、前半部分の集合を1つ決めたときに、その集合に対して使用できる後半部分の集合を計算し、その集合に対応するDPの配列を参照して足していくことで、答えを求めることができます。
最初に計算した同時に存在しうるかどうか、の情報をlong long型の変数で持っておくと、その後の計算が楽かつ高速に行えるので、この問題に答えることができます。

感想

模擬国内Eの復習をサボっていたら同じような問題にあたってしまいました…
と思っていたのですが、bitDPなり全探索なりでもいけるみたいですね！

AOJ 2200 - Mr. リトー郵便局

動的計画法(DP) ワーシャル-フロイド法

問題
提出コード

解法

まずは、陸路と海路それぞれについて、ワーシャルフロイド法を用いて、任意の町間の最短距離を計算しておきます。町iから町jの最短経路について、陸路をl_{ij}、海路をs_{ij}とします。
そして、DPを行います。
dp[i][j] = i回目の集配を終えた時点で、船が町jにあるような経路の中で、時間が最短のもの
とします。そして、i回目の集配を陸路のみで行うか、海路も含めて行うかの2パターンに分けて計算します。
初期値は、dp[1][j] = s_{z_1 \ j}となります。

  • 陸路のみを利用する場合
    i回目の集配を終えても、その前後で船の位置は移動しません。ので、
    dp[i][j] = min(dp[i][j] ,dp[i - 1][j] + l_{z_{i -1 } \ z_{i}} )
    となります。

  • 海路も利用する場合
    町kから町jまで海路を利用したとします。すると、
    (z_{i - 1}からkまでの陸路) + (kからjまでの海路) + (jからz_{i}までの陸路)
    が今回かかる時間なので、
    dp[i][j] = min(dp[i][j] , dp[i - 1][k] + l_{z_{i - 1} \ k} + s_{k \ j} + l_{j \ z_{i}} )
    となります。


あとは、このDPを行い、dp[r][j]の最小値を求めれば答えとなります。