2019-08-14

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なり全探索なりでもいけるみたいですね！

2019-08-14

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]$ の最小値を求めれば答えとなります。

2019-08-13

AOJ 1132 - Circle and Points

幾何リベンジ

問題
 提出コード

解法

1個のみ円の中に入るパターンは明らかなのでここでは2個以上のパターンのみ考えます。
円の中に入る点の個数が最大の円の配置方法があるとき、その個数を減らさないまま、ある2点を同時に円周上に乗せることができます。
ということで、これ以降は2点が円周上にあるパターンの円の配置方法について、点の個数が最大となるパターンを探せばよいです。
f:id:emtubasa:20190811170916p:plain
ある距離が1以下の2点が存在するとき、上の図のような2つの円のパターンが存在します。それぞれについて、入る点の個数を求めれば良いです。
円の中心座標が求まれば、全部の点について、中心からの距離が1以下であるかどうかを調べ、1以下であるものをカウントすれば円の中に入る点の個数がわかります。
ということで、あとは円の中心座標がわかればよいです。
f:id:emtubasa:20190811172202p:plain
今、図の線分 $AB$ が2点を結ぶ直線だとします。この際の、中心座標を求めます。
$\angle ABC = 90^{\circ}$ です。
また、線分 $AC$ の長さは2で、 $AB$ も、2点の座標がわかっているので求めることができます。ということで、三平方の定理から、 $BC$ の長さも求めることができます。これにより、 $\overrightarrow{BA}, \overrightarrow{BC}$ を求めることができ、円の中心は $A$ と $C$ の中点なので、上手く計算することができます。
あとは、全部の円について中心を求め、その中に入る点の個数の最大値を計算すれば答えとなります。

感想

ある点を中心に持ってきてもダメそう→2点を結ぶ直線を円内にいれたいよね→なんかある点はギリギリに持ってきた方がよさそう→だからなんだろう…？(終)
という感じで考察が終わってしまったので、幾何は苦手です(?)
周りの人々がだいたい秒殺していたので、負けないように頑張りたいです…

2019-08-12

AOJ 1176 - 輪番停電計画

動的計画法(DP) 再帰前計算累積和メモ化再帰

問題
 提出コード

解法

はじめに、2次元累積和を用いて、ある長方形の範囲の需要の合計を $O(1)$ で求めることができるようにしておきます。
ここから、DPを行います。
$dp[i][j][k][l] =$ 長方形の左上が $(i,k)$ ,右下が $(j,l)$ となるような範囲のグループの分け方の最適解
とします。最適解、なのでグループ数と予備力の2つの情報を持ち、グループ数、予備力、の優先順位でより値が大きいものが最適解となります。

そもそもですが、左上が $(i,k)$ ,右下が $(j,l)$ となるような範囲を停電させても供給力が足りない場合、すなわち $s-(与えられた町全体の需要)+(今見ている範囲の需要の合計) \lt 0$ ならば、答えはありません。
それ以外の場合を見ていきます。
答えの候補ですが、

今見ている範囲をこれ以上分割しない
今見ている範囲をある縦線で区切る
今見ている範囲をある横線で区切る

の3パターンになります。全ての候補を調べ上げ、その中での最適解を選べばよいです。
一番最初のパターンは、グループ数がもちろん0、予備力は $s-(与えられた町全体の需要)+(今見ている範囲の需要の合計)$ そのものです。
また、2つめのパターンと3つめのパターンでは、縦横が異なるのみで操作自体は同じなので、今回は横線で区切るパターンを見ていきます。
左上が $(i,k)$ ,右下が $(j,l)$ となっている範囲を横線で区切ると、
左上が $(i,k)$ ,右下が $(x,l)$ と、左上が $(x+1,k)$ ,右下が $(j,l)$
の2つの範囲に分割されます。
まずは、それぞれの範囲の最適解を調べます。これは、再帰的に調べればよいです。
あとは、2つに分けた範囲それぞれのグループ数の和と、2つに分けた範囲それぞれの予備力のうち小さい方をセットにすれば、今見ている左上が $(i,k)$ ,右下が $(j,l)$ の範囲の答えの候補になります。

後は適当にメモ化再帰を行えば、答えを求めることができます。

感想

条件がややこしかったり次元が大きかったりしましたが、丁寧に詰めたのでさらっと解くことができました。
多少複雑な問題でも頭が真っ白にならないようにしたいですね。

2019-08-06

AOJ 0570 - ジグザグ数 (Zig-Zag Numbers)

桁DP コーナーケース

問題
 提出コード

解法

$B$ 以下のジグザグ数の個数から、 $A-1$ 以下のジグザグ数の個数を引くと答えになるので、あとは $X$ 以下のジグザグ数の個数を求める方法がわかればよいです。
桁が明らかに大きいので桁DPをしていきます。
$dp[i][j][k][l][o]$ について、
$i$ : 今見ている桁の番号
$j$ : $X$ 以下が確定しているかどうか(1,0で管理)
$k$ : 今の桁と1つ前の桁について、ジグザグの増加と減少がどちらか(1,0で管理)
$l$ : 今どの番号を当てはめるか(0 ~ 9)
$o$ : 今の段階でのmod $M$ の値
を考えていきます。
状態数が多い(~~面倒くさい~~)のでざっくりでいきますが、1つ前の遷移と今の遷移を見比べたときに、 $k$ は交互になるように遷移していきます。そして、ジグザグの増加(減少)の条件を満たすように、今見ている桁の数字と1つ前の桁の数字を当てはめていきます。あとは、桁DPおなじみの $X$ 以下かどうかの判定を行いつつ、 $o$ の値をうまく計算しながらDPをしていけばよいです…
のですが、 $p$ 桁の数字 $X$ に対して、 $p$ 桁未満の数字を数え上げるとき、
$0000...$ のように0埋めされている、と考えてしまうと、これはジグザグ数ではなくなってしまいます。ので、 $i$ 桁目の遷移を考えるときに、それより上の桁が0埋めされている数についてあらかじめカウントしてあげる必要があります。
このコーナーケースの処理も書くと、この問題の答えを求めることができます。

感想

桁DPに見えるので遷移を考えると、情報を適当にもっていても計算量的には大丈夫、ということで書き始めたのですが、mod $M$ の計算の部分でバグを埋め込んでしまい、時間を溶かしてしまいました…
桁DPのうまいデバッグ方法がわからないので、訓練したいです。

2019-07-22

AGC036 C - GP 2

数え上げ

問題
 提出コード

解法

まず、最終的な数列の中に奇数が $p$ 個存在するときについて考えます。 $p$ は最大で $min(m,n)$ となります。
すると、残った $x_{j}$ に1加算する操作を2つまとめて、 $x_{i}$ に2加算する操作 $(m-p)/2$ 回分に置き換えることができます(もちろん、残った回数が奇数の際は端数が発生するので、考慮せずスルーします)。
すると、 $p$ 個の奇数を選ぶのは、 $_{N}C_{p}$ で求めることができます。そして、 $x_{i}$ に2加算する操作 $m + (m-p)/2$ 回を $N$ 個の数字に割り振るのは、 $_{m + (m-p)/2}H_{N} = _{m + (m-p)/2 + N -1}C_{N-1}$ で求めることができます。
基本的にはこれでよいのですが、いくつか実現不可能なパターンが存在します。 $i \neq j$ の制限があるためです。
これは主に2つのパターンがあります。数列のどこか1つが $2M+1$ 以上の奇数パターンと、 $2(M+1)$ 以上の偶数パターンです。どちらのパターンも、そのような数字が同時に2個以上出現することはありません(全体の総和が $3M$ にしかならないからです)。

$2M+1$ 以上の奇数パターン
仮に $x_{0}$ がその値だったと仮定して、最後に $N$ 倍してあげることで網羅できます。 $x_{0}$ が奇数なので、それ以外に $p-1$ 個の奇数が存在するはずです。この割り振り方は、 $_{n-1}C_{p-1}$ 通りです。
そして、2を加算する操作は、 $(m-p)/2$ 回だけ残っています(少なくとも $M$ 回は $x_{0}$ に割り振らなければなりませんが、それ以外はどこに割り振ってもいいです)。よって、割り振り方は $_{(m-p)/2}H_{N}$ 通りとなります。
$2(M+1)$ 以上の偶数パターン
1つめのパターンと同様に考えると、奇数の割り振りは $_{n-1}C_{p}$ となります。
2を加算する操作の割り振りは、 $_{(m-p)/2-1}H_{N}$ となります。今回は、 $x_{0}$ に少なくとも $M+1$ 回割り振る必要があるので、残る回数は $(m-p)/2 - 1$ 回です。

あとは、最初に計算した全体から、実現不可能なパターンを引けばよいです。
$_{N}C_{p} \times _{m + (m-p)/2}H_{N} - N ( _{n-1}C_{p-1} \times _{(m-p)/2}H_{N} - _{n-1}C_{p} \times _{(m-p)/2-1}H_{N})$
となります。
これを全ての $p$ に対して計算を行い、総和を求めれば答えとなります。

感想

奇数の個数を決め打ちして、2に加算する回数にまとめてしまう、という考え方が天から降ってきました(わーい)。
実現できないコーナーケースを見つけて、冷静に対処できたのも良かったです。

2019-07-22

AGC036 B - Do Not Duplicate

未分類

問題
 提出コード

解法

同じ状況になる部分をどんどん取り除き、最終的に残る数回を愚直にシミュレーションします。
まずは、空の数列 $s$ に対して $i$ 番目の数字 $A_{i}$ を $s$ に入れたときに、 $A_{i}$ を取り除くことで再び数列が空になるタイミングはどこか、を調べます。
これは、 $A_{i}$ の種類ごとに $i$ を昇順にまとめ、 $i$ に対しては $A_{i} = A_{j}$ となるような、 $i \lt j$ となる $j$ のうち最小の物をメモすればよいです(もし存在しなければ、 $A_{i} = A_{p}$ となる最小の $p$ をメモします。 $i = p$ となることもあります)。
次に、初期状態( $s$ が空の状態で、次に挿入するものが $A_{0}$ であるタイミング)まで一回ループするのに何回操作をするか、を調べます。
これは、次に操作する数列の番号 $i$ を最初に $i = 0$ とし、先ほどのメモを見ながら、数列が空になるタイミングごとに区切って調べていけばよいです。
$i$ に対してのメモが $j$ の場合、 $j - i + 1$ 回操作を追加すると数列が空になり、次に操作する対象は $j+1$ 番目になります。ので、操作回数に $j - i + 1$ を加算し、 $i = j + 1$ と再定義します。ただし、 $i \geqq j$ の際は、 $j - i + 1 + N$ となります。
これを、再び $i = 0$ となるまで行います。
メモの種類はもちろん添え字 $i$ の分だけなので、これは最悪でも $N$ 回の操作となります。
$s$ が空かつ、 $i = 0$ で操作を開始して、再び同じ状態に戻ってくるまでの回数を $L$ とします。すると、操作をする回数 $NK$ は、最終的に $NK \ mod \ L$ となります。これを、新たに $K$ と定義しなおします。
この時点での $K$ は、最大で $N^{2}$ 程度です( $A_{i}$ が全て異なるパターンです)。
ここから、さらに値を減らします。
先ほど、1回ループするまでの回数をシミュレーションをしましたが、これと同じ操作をしつつ、今度は $j - i + 1$ を $K$ から直接減らしていきます。そして、 $j - i + 1$ を減らすと $K$ が負になる、というタイミングでやめます。このシミュレーションは、先ほどと同じく最悪でも $N$ 回の操作で済みます。
こうすると、残っている操作回数 $K$ は、最大でも $N$ となります(次に操作する添え字を問わず、数列が空の状態から再び空になる際の最悪ケースは、先ほどと同じで $A_{i}$ が全て異なるパターンだからです)。
ということで、操作回数を $N$ まで減らすことができたので、あとは現状の $i$ から愚直にシミュレーションをしていけばよいです。
これは、stackを使うと、最大で $2N$ 回程度のプッシュ、ポップの操作になるので十分間に合います。すでにスタック内に存在するかどうかは、setを利用しました(こっちの方が計算量的には重くなると思います)。
計算量的には、おそらく $O(N log N)$ です(自分は最初の $A_{N}$ ごとにまとめる操作を行う際にc++のmapを使用したため)。