ツバサの備忘録

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

AOJ 2014 - 土地囲い

問題
提出コード

解法

黒の杭と拡大隣接してるマスは、幅優先探索を用いて行うことができます。白も同様です。
ということで、それぞれの色について、拡大隣接しているマスをすべて洗い出します。
その処理が終わったら、片方の色についてのみ拡大隣接しているマスをカウントしていけば、答えになります。

感想

実は、思いつくのに少し時間がかかりました(というより、問題文を理解するのに時間がかかりました)
困っていたのは拡大隣接の判定で、白と黒どちらかのみに隣接しているマスを一発で求めようとしていたのが原因でした。
結局、それぞれに分けて考えてから、最後に判定すればいいだけでしたね。

AOJ1626 - 超高層ビル「みなとハルカス」

問題
提出コード

解法

解の候補について、フロアのうち最下層の階数をa、フロアの総数をcとします。すると、[a,a + c - 1]の階を借りることになるので、料金は次のようになります。
\displaystyle \sum_{k=a}^{a+c-1}k = \frac{(2a+c-1)c}{2}
これがbと一致するので、結局
(2a+c-1)c = 2b
という条件が成り立つことになります。
cを1つ固定すると、aは式変形によって簡単に求めることができます。
a  = \frac{\frac{2b}{c} - c + 1}{2}
これが正の整数になるかどうかを確認して、あとはcが最も大きくなるようなペアを探せばよいです。
cの列挙は、O(\sqrt{b})で行うことができるので([1,\sqrt{2b}]からiを取り出し、2biで割り切れるとき、iおよび2b/icの候補になります)、これを全部調べればよいです。

感想

久々にAOJをやりました。が、実装系というよりかは数学系でした。
この問題は2018の国内予選のC問題で、自分のチームはほかの2人が通したものです。
当時もし自分が解いていた場合、解けたんでしょうか…?
思考の過程としては、ひたすら式を組み立てて何か条件がないか、と探しただけです。このレベルの\sumの変形は、まだ自分の頭にも残っていたので、割とささっと解けました。

AGC005 B - Minimum Sum

問題
提出コード

解法

i番目の数字、a_{i}が採用される区間について調べてみます。
l \leqq i \leqq rとなる区間[l,r]について、a_{i}がその区間の最小値になるには、 i\neq jかつl \leqq j \leqq rとなる任意のjについて、a_{i} \lt a_{j}が成り立たなければなりません。
こうなるようなlの候補の最小値、rの最大値を求めてみます。
これが計算できれば、a_{i}が最小値となる区間の個数を利用して、
a_{i} (i - l + 1)(r-i+1)
という計算をすべてのiについて行い、その和を取れば答えとなります。
lは、a_{i} \gt a_{l-1}となるようなlの最大値、ra_{i} \gt a_{r+1}となるようなrの最小値です。
このままでは、一見簡単に求めるのが難しいように見えます。しかし、上のような条件を満たすl,rが存在しない場合、すなわちa_{i}区間全体における最小値だった場合は、問答無用でl区間の左端、r区間の右端になります。このことを利用します。
例えば、下のようなN=8の数列について考えてみます。

f:id:emtubasa:20190318231518p:plain

最初、区間全体を見ます。
[1,8]区間にあるa_{i}の最小値はもちろん1になります。
ということで、i = 4,l = 1,r = 8として、a_{i} (i - l + 1)(r-i+1) を計算すると、
1 \times 4 \times 5 = 20
となります。
1が絡む区間はすべて見終わったので、これを含まないような区間を調べます。すると、区間がちょうど2つに分かれます。
[1,3][5,8]です。
この新しくできた2つの区間について、それぞれの区間の中での最小値と、その位置を調べます。
前者は、i = 2,a_{i} = 2で、後者はi = 5,a_{i} = 3です。
同じようにa_{i} (i - l + 1)(r-i+1) を計算してあげると、それぞれ
2 \times 2 \times 2 = 8
3 \times 1 \times 4 = 12
となります。
これで、2および3が絡む区間を見終わったので、また区間を分けていきます。もし、最小値が端にある(今回の[5,8]のような)パターンについては、新しい区間は1つしかうまれません。
この操作を、最終的に区間の幅が1になるまで繰り返していきます。
こうして、a_{i} (i - l + 1)(r-i+1) を計算していって全ての総和を取れば、答えがでてきます。
区間の最小値を取り出すのは、RMQを利用します。配列のインデックスは、ペアか何かで持たせておけば大丈夫です。

操作をまとめると、はじめはl = 1,r = Nとして、
[l,r]について、その区間内の最小値とそのインデックスa_{i} ,iを探します。そして、
a_{i} (i - l + 1)(r-i+1)
を計算します。その後、
[l,i-1]i+1,r]の新しい区間について、同じことを繰り返していきます。
そして、計算したa_{i} (i - l + 1)(r-i+1) の総和を取れば答えになります。
調べたい区間をペアで管理し、新しく調べたい区間が出てくるたびにキューかスタックに格納していき、1つの区間を調べ終わったらまたそこから区間を1つ取り出していく、というようにすると、いい感じに調べることができると思います。

感想

てこずりました。ある数字が加算される(区間の最小値になる)条件と個数を調べていくのだろうな、とは思ったのですが、それを調べる方法がなかなか思いつきませんでした。
思考の過程としては、まずa_{i}が最小値になるときのことを考えると、その区間[l,r]は、一定の場所までは区間を広げても常に成り立ち、一回条件を満たさなくなるとそれ以降区間をどれだけ広げても再び最小値になることはないことを確認します。すると、その区間が一番広い場所を探すことができれば、a_{i}が最小値になる回数がわかるので、a_{i} (i - l + 1)(r-i+1)を計算するだけでよいことになります。あとは、一番広くなる区間を探すだけなのですが、最初はa_{i}を昇順に見ていってうまく処理できないかということを考えていました。結局それで調べる方法が思いつかなかったので悩んでいると、逆に、ある区間に対しての最小値を求めれば、その区間が答えになる、ということに気づいたので、上のような解法を思いつきました。

ABC092 C - Traveling Plan

問題
提出コード

解法

毎回愚直に計算するともちろん間に合わないので何か工夫をする必要があります。そこで登場するのが累積和です。
まず、始点と終点も観光スポットとみなし、A_{0} = A_{N+1} = 0としておきます。

  • s[i] = 観光スポット0からiまで順番に行ったときにかかる金額の総和

とします。
これは、
\displaystyle s[i] = \sum_{k=1}^{i} |A_{k} - A_{k-1} |
という計算をすることで求めることができます。しかし、s[i]を求めるのに、s[i-1]を利用すると、
\displaystyle s[i] = \sum_{k=1}^{i-1} |A_{k} - A_{k-1} | + |A_{i} - A_{i-1} |
であることから、
s[i] = s[i-1] + |A_{i} - A_{i-1} |
というように変形できます。
これにより、s[i]O(1)で、1からN+1すべてについてのs[i]を求めるのにO(N)で計算できるようになりました。
さて、s[i]は、観光スポット0から、という区間についてしか計算できません。[i,j]という区間についてのみ移動した場合の金額を計算するにはどうすればよいかというと、
\displaystyle  \sum_{k=i+1}^{j} |A_{k} - A_{k-1} |
という計算ができればよいので、式を変形すると
\displaystyle  \sum_{k=0}^{j} |A_{k} - A_{k-1} | -  \sum_{k=0}^{i} |A_{k} - A_{k-1} |
となります。
よって、始点を0にした計算式に置き換えることができたので、s[i]を利用して、
s[j] - s[i]
と計算すればよいことになります。

さて、下準備ができたので、i番目のスポットに行かない場合の金額の計算を行います。
このとき、移動ルートは次のようになり、それぞれ以下のようにして計算できます。

  1. [0,i-1]
    s[i-1]を参照するだけでよいです。

  2. i-1から直接i+1
    |A_{i+1} - A_{i-1}|を計算すればよいです。

  3. [i+1,N+1]
    先ほど求めたように、s[N+1] - s[i+1]を計算すればよいです。


ということで、上の3つを組み合わせ、
s[i-1] + s[N+1] - s[i+1] + |A_{i+1} - A_{i-1}|
が答えになります。これはO(1)で計算できるので、N回答えるには、O(N)かかりますが、十分間に合います。

解法

累積和入門にちょうどいいと思います。
添え字のバグにも注意しつつコードを書く必要があるのでそこだけ大変でした。

ABC091 C - 2D Plane 2N Points

問題
提出コード

解法

2次元のままこの問題を考えると、いろいろと大変なことになるので、どちらか片方の条件を無視してよくなるような条件を探します。
すると、赤の点と青の点を同時にxの昇順、yの昇順の優先度でソートを行うと、i番目の赤い点と、j番目の青い点について、i \lt jが成立しているときに、xについては常に条件を満たすようになります。
ということで、この後は次のような問題に置き換えることができます。

  • i \lt jかつ、y_{i} \lt y_{j}となる赤い点iと、青い点jのペアの個数の最大値はいくつか。

制約を見ると、点の個数はとても少ないので、探索にそこそこ時間をかけても大丈夫です。
ということで、上のソート済みの数列に対して前から順番に見ていき、次のような操作をします。

  • 次に見る点iが赤い点だった場合
    別のリストに、赤い点を記録していく。

  • 次に見る点jが青い点だった場合
    赤い点を記録したリストをyについて昇順にソートしなおし、y_{j}より小さいy_{i}のうち、y_{i}が最大となっている点を二分探索で調べる。その点と、jをペアにする(リストからiの点を消す)。


xが小さい順に青い点を持ってきたときに、まだペアになっていないかつ、今見ている青い点とペアを組める赤い点のなかから1つペアを組むとしたら、組める中でyが最も大きいものを選んだ方が得になるので、青い点を取ってくるたびに二分探索でそのような点を探します。
ということで、これを繰り返し、完成したペアの個数が答えになります。

感想

これ、400点にしても難しい気がします…
たしかにやっていること自体は400点っぽい内容なのでなんともいえないです。
初見のときは解けなかったのですが、今回もかなり時間がかかりました。完全に点の個数が10^{5}ぐらいあると思っていたので、ソートした後どうやってペアをつくればいいかずっと悩んでいました。

AGC031 B - Reversi

問題
提出コード

解法

まずはじめに、c_{i}c_{i+1}以降も連続していた場合、その連続している部分の石は必ず同じ色になるので、1つの石に圧縮してしまいます。
この操作を行った、残りの石の列について考えていきます。

次のような操作について考えてみます。
f:id:emtubasa:20190317020108p:plain 左側が1番、そこから1ずつ増えていって、右端が9番とします。
ここで、一番上の初期状態から、[4,6]の石に対して操作を行った後、[2,7]の石に対して操作を行うと、上の図の一番下の列のような結果になります。
さて、この操作を見ると、明らかに[4,6]に対して行った操作が意味をなしていません。ということで、[x,y]に対して操作を行うとき、[i,j] (ただしx \lt i \lt j \lt y )の操作は無視してもよいことになります。
さて、次のようなDPを考えます。
dp[i] = i番目までの石に対する列の種類数
場合分けをしていきます。

  • i区間の右端となるような操作を行わない場合
    このように決めた場合、i-1番までに対して操作を行ったときの種類数がそのままi番目までの種類数になります。ので、このパターンについては
    dp[i-1]
    を参照すればよいです。

  • i区間の右端となるような操作を行う場合
    上の図についてみてきたように、j \lt iとなるj区間の左端として、[j,i]に対して操作を行うとした場合、この区間内の操作はどのようにしても1通りにしかなりません。
    さて、上の図において、青い石は3,5,8番目に3つ存在しています。このとき、[3,8]に対する操作は、[3,5]に対して操作を行った後、[5,8]に対しても操作を行うことと等しくなります。
    [3,5]に対する操作は、dp[5]にすでに含まれている(dpの定義が、その場所までの全ての石の色の並び方を網羅していることになっているため)ので、特別な操作を行う必要はなく、結局、i区間の右端となるような操作を行う場合は、
    dp[j] (ただし、jc_{i} = c_{j}かつj \lt iとなる数字のうち最も大きいもの)
    がそのまま新たな種類数となります。

    ということで、
     dp[i] = dp[i-1] + dp[j] (ただし、jc_{i} = c_{j}かつj \lt iとなる数字のうち最も大きいもの)
    という計算を行っていけば、dp[N]が答えになります。
    jは、前計算をするなり、DPの遷移と同時に計算していくことで求められます。

    感想

    今回はA問題を自力で解けなかったので、こちらだけ解くことができました。問題を読んでからわりとすぐに考察を終えることができたので、なかなか良かったかなと思います。
    思考の過程としては割と解法そのままで、まずは連続した部分が必要ないこと、そして片方の区間がもう片方の区間を完全に含んでいた場合に、小さい方の区間の操作が全く意味をなさないことに気づきます。
    その後、2つの区間でダブりがあるものについても、どちらか片方しか操作ができないことがわかり、あとは、上の青い石のような、3つ以上存在するパターンの処理の仕方について考えました。
    明らかに区間DPが通らないので、この処理をどうするかわかれば、1次元のDPができそうだなと思い、悩んでいると、3つの石のうち、一番遠い2つについての操作は、2つの操作に分けることができるということに気づけたので、あとは遷移を丁寧に求め、この問題が解けました。

Educational DP Contest / DP まとめコンテスト T - Permutation

問題
提出コード

解法

i番目までの順列が完成しているときに、i+1番目の数字を加えて条件を満たす数列を作成することを考えます。
dp[i][j] = 長さiの数列で、一番後ろにjを選ぶときの並べ方の通り数
とします。
dp[i+1][j]を求めるために、i番目の数字とi+1番目の数字の関係をもとに場合分けしていきます。

  • p_{i} \lt p_{i+1}のとき
    p_{i} \lt jとなっている、i番目まで完成している任意の順列を1つ選びます。そして、この順列を少し組み換え、j以上の数字に+1をしてあげると、これはjを除き、[1,i+1]からなる数列になっていて、なおかつこの数列は問題の条件を満たしています。
    ということで、今作成した数列の最後尾にjを付け加えると、これは長さi+1の順列で、かつ問題の条件を満たしています。
    これ以外で作成できる、長さi+1で問題の条件を満たす順列は存在しません。上の操作と逆のことをすると元の順列を作成することができますが、逆操作を行う対象の順列が異なれば、逆操作後の順列も必ず異なるものになります。ので、長さi以下の順列を数え終えていることに反します。
    とういことで、p_{i+1} = jのとき、p_{i}j未満になればよいので、
    \displaystyle dp[i+1][j] = \sum_{k=1}^{j-1} dp[i][k]
    となります。

  • p_{i} \gt p_{i+1}のとき
    こちらも上と同様の手順を踏むことで、問題の条件を満たす順列が作成できます。これ以外に作成する方法がないので、結局はp_{i}j以上になっていればよいです(上の操作では、j以上の数に+1という操作を行っているので、p_{i}jになっていても、条件を満たすことができることに注意します)。
    ということで、
    \displaystyle dp[i+1][j] = \sum_{k=j}^{i} dp[i][k]
    となります。

    さて、あとはこのDPを行えばいいのですが、このままだと総和を取る操作で計算するのに時間がかかってしまいます。そこで、
    \displaystyle sum[i][j] = \sum_{k=1}^{j}dp[i][k]
    とすると、
    上の2つの遷移はそれぞれ、
    \displaystyle dp[i+1][j] = sum[i][j-1]
    \displaystyle dp[i+1][j] = sum[i][i]-sum[i][j-1]
    となります。
    ということで、このDPを行うと、答えは
    dp[n+1][n+1]を参照すればよいです。

    感想

    証明まできっちり行ってから通すことができたので良かったのではないかなと思っています。
    式変形も素直にできたのでよかったです。
    思考の過程としては、割と上の解法をそのままたどるような形で、まずはある時点での数列を完成していた場合に、1つ長さを増やした数列を作成するにはどのようにすればいいだろうか、という部分から解法を思いつきました。