ツバサの備忘録

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

ABC138 F - Coincidence

桁DP

問題
提出コード

解法

(x,y)が問題の条件を満たすには、これらを2進数に直した時に、

  • 最上位桁が一致している

  • それぞれの桁について、xのi桁目とyのi桁目が一致している、もしくはxのみ0でyのみ1になっている

という条件を満たす必要があります。
ということで、最上位桁が下からd桁目の際の(x,y)のペアを求めるために、桁DPを行います。あとはこれを全ての桁について行えばよいです。
dp[i][j][k]を用意し、

  • i:上から何桁目を見ているか(ただし最上位桁は確定しているのでないものとします)

  • j:xがmax(L, 2^{d-1})以上であることが確定しているか

  • i:yがmin(R,2^{d} - 1)以下であることが確定しているか

とします。
あとは、下の表をもとに遷移をひたすら書いていけばよいです… f:id:emtubasa:20190820173515p:plain

感想

Lの存在が邪魔で、うまい処理方法を思いつきませんでしたが、よくよく考えればR同様フラグを立てれば処理できますね…ただ桁DPの実装は丁寧にやらないといつもバグらせるので悲しいです(コンテスト中にラスト10分で書き直したものはもちろんバグだらけでした)

ABC138 E - Strings of Impurity

二分探索 全探索 貪欲法

問題
提出コード

解法

tに含まれ、sに含まれない文字が存在する場合、答えは-1になります。逆に、それ以外の場合は、必ず答えを見つけることができます。
s'の部分列でtを作る際、お互いの先頭から順番に、一致する部分を選んでいけばよいです。
作りたい文字列はtと固定されているので、tのx文字目がs'の何文字目に相当するかを調べていけば、tの最後の文字と対応するs'の番号が答えになります。
あとは、愚直にシミュレーションをしていきます。
あらかじめ、sを文字の種類ごとに分け、どの文字には何文字目が含まれるか、を調べて昇順で記録しておきます。
そして、今sの何文字目に居るか、というインデックスiを更新しながら(初期は0文字目、としておきます)シミュレートしていきます。
次に決めるのがtのx文字目t_{x}のとき、iよりも後で登場するt_{x}の場所を、先ほどの記録を二分探索して探します。iよりも後ろにt_{x}が存在しない場合は、sの中で一番最初に存在するt_{x}の場所になります。
そして、iを今探した場所に更新すればよいです。
これを繰り返すと、最終的にいる位置がわかります。
そして、肝心の答えですが、先ほどi以降にt_{x}が存在しなかった場合、sを1周することになるので、
(i以降にt_{x}が存在しなかった回数) \times |s| + i
になります。

感想

それなりにスッキリとした実装ができたので個人的に満足です。

AOJ 2152 - Restrictive Filesystem

実装系

問題
提出コード

解法

手で連結リストを作成していきます。
setで現在存在しているファイルの識別子を管理しておくことで、リストの中身を毎回書き換えずとも、削除のクエリを処理できるようにします。
あとは、リストを毎回前から探索していき、空きスペース(もしくは最後)に現在書き込みたいファイルの書き込みをしたり、ファイルの読み込みを行ったりすればよいです。

AOJ 1604 - デッドロック検出

未分類 リベンジ

問題
提出コード

解法

まずは、すでにロックを獲得した資源と、次に獲得する資源を対にした頂点を作成していきます。
10個程度しか資源は存在しないので、ビットで情報を持たせることができます。
その後、2つの頂点を選んだときのパターンを見ると、今回は3パターンします。

  • 2つの頂点どちらも既にロックを獲得した資源が存在しているパターン
    f:id:emtubasa:20190814183156p:plain
    2つの頂点が同時に存在することはないので、無視してかまいません。

  • 2つの頂点どちらも既にロックを獲得した資源が存在せず、片方の頂点が所有している資源をもう片方の頂点が次に獲得するパターン
    f:id:emtubasa:20190814183324p:plain
    片方(青い方)はこれ以降資源を獲得することはできませんが、もう片方(黄色)は次の資源を獲得することができます。この2つの頂点は、和集合の資源を獲得した状態で、次に黄色のNEXTの部分の資源を獲得しにいく1つの頂点とみなすことができます。

  • 2つの頂点どちらも既にロックを獲得した資源が存在せず、お互いの頂点が、相手が所有している資源を次に獲得するパターン
    f:id:emtubasa:20190814183552p:plain
    言うまでもなくデッドロックが発生します。

  • 2つの頂点どちらも既にロックを獲得した資源が存在せず、お互いが次に獲得する資源はどちらも所有していない資源のパターン
    f:id:emtubasa:20190814184015p:plain
    お互いが影響しあうことはないので、無視できます。


全てのパターンについて、tps://onlinejudge.u-aizu.ac.jp/problems/1604)
提出コード

解法

まずは、すでにロックを獲得した資源と、次に獲得する資源を対にした頂点を作成していきます。
10個程度しか資源は存在しないので、ビットで情報を持たせることができます。
その後、2つの頂点を選んだときのパターンを見ると、今回は3パターンします。

  • 2つの頂点どちらも既にロックを獲得した資源が存在しているパターン
    f:id:emtubasa:20190814183156p:plain
    2つの頂点が同時に存在することはないので、無視してかまいません。

  • 2つの頂点どちらも既にロックを獲得した資源が存在せず、片方の頂点が所有している資源をもう片方の頂点が次に獲得するパターン
    f:id:emtubasa:20190814183324p:plain
    片方(青い方)はこれ以降資源を獲得することはできませんが、もう片方(黄色)は次の資源を獲得することができます。この2つの頂点は、和集合の資源を獲得した状態で、次に黄色のNEXTの部分の資源を獲得しにいく1つの頂点とみなすことができます。

  • 2つの頂点どちらも既にロックを獲得した資源が存在せず、お互いの頂点が、相手が所有している資源を次に獲得するパターン
    f:id:emtubasa:20190814183552p:plain
    言うまでもなくデッドロックが発生します。

  • 2つの頂点どちらも既にロックを獲得した資源が存在せず、お互いが次に獲得する資源はどちらも所有していない資源のパターン
    f:id:emtubasa:20190814184015p:plain
    お互いが影響しあうことはないので、無視できます。


全てのパターンについての判定がこれで網羅できるようになるので、あとは複数頂点が1つの頂点にまとめられる回数、つまり10回程度、任意の2頂点について操作を行うということを繰り返せば、デッドロックが起こるかどうかを判定できます。

感想

資源数が少ないので状態を頂点にするという発想まではよかったのですが、それ以降どうすればいいかわかりませんでした…

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 - 沈みゆく島

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

問題
提出コード

解法

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

感想

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