# 10/21 ~ 10/28

## 10/21

2072diff
[ARC081-E Don't Be a Subsequence](https://atcoder.jp/contests/arc081/tasks/arc081_c)

### 解法

部分列dpをやる

[提出](https://atcoder.jp/contests/arc081/submissions/59026044)

### 感想

非典型に強くなるために始めたARC精進だが、結局典型 or 変なギャグしか解けていない。

## 10/22

試験管1898diff
[ARC051-C 掛け算](https://atcoder.jp/contests/arc051/tasks/arc051_c)

### 解法

何回か操作を行うと、 $A\times \min (a)\gt \max (a)$ という状態が保たれるようになる。こうなると、操作する値の列は周期性を持つようになる。

周期性が出るまで愚直に操作を行って、周期性が出たらまとめて計算する。

[提出](https://atcoder.jp/contests/arc051/submissions/59050217)

### 感想

CodeChefかCFで見たことある問題設定だった。 $A = 1$ がいやらしいな。

## 10/23

試験管2004diff
[ARC039-C 幼稚園高橋君](https://atcoder.jp/contests/arc039/tasks/arc039_c)

### 解法

高橋君のいる場所の $x, y$ 座標の絶対値は $K + 1$以下である。この範囲内を区間をsetで管理するテクをつかってシミュレーションする。

[提出](https://atcoder.jp/contests/arc039/submissions/59075600)

### 感想

ライブラリ化していない....

## 10/24

試験管2997diff
[ARC028-D 注文の多い高橋商店](https://atcoder.jp/contests/arc028/tasks/arc028_4)

### 解法

https://maspypy.com/%E5%A4%9A%E9%A0%85%E5%BC%8F%E3%83%BB%E5%BD%A2%E5%BC%8F%E7%9A%84%E3%81%B9%E3%81%8D%E7%B4%9A%E6%95%B0%EF%BC%88%EF%BC%92%EF%BC%89%E5%BC%8F%E5%A4%89%E5%BD%A2%E3%81%AB%E3%82%88%E3%82%8B%E8%A7%A3%E6%B3%95

から大体の方針を知っていた。自力で解法を導けることを確認して通した。

注文が無い場合を考える。今回のdpをFPSで解釈すると$[x^{M}]\prod_{i = 1}^{N}(1 + x + x^2 + \cdots + x^{A_{i}})$となる。等比数列の和の公式から$(1 + x + x^2 + \cdots + x^{A_{i}}) = \frac{x^{A_{i} + 1} - 1}{x - 1}$である。この計算は共に$O(M)$で計算することができる。
- $\sum q_{i}x^{i} = F(x)\sum p_{i}x^{i}$として、次数が同じ所をまとめた$M + 1$個の方程式を建てるとわかる

注文がある方を考える。クエリを先読みしておく。以下のようなことができれば良い。

1. $i$ 種類目の商品からの寄与を打ち消す
2. $j = 1, 2, \dots, A_{i}$について、$\text{dp}[M - j]$を計算する
3. $i$ 種類目の商品からの寄与を戻してあげる

2は配列にアクセスするだけ、3は$\frac{x^{A_{i} + 1} - 1}{x - 1}$をかける。1は逆をすれば良いので、$\frac{x - 1}{x^{A_{i} + 1} - 1}$をかける。

[提出](https://atcoder.jp/contests/arc028/submissions/59101716)

### 感想

特になし

## 10/25

1964diff
[ARC105-C Camels and Bridge](https://atcoder.jp/contests/arc105/tasks/arc105_c)

### 解法

可能、不可能の判定は自明。

各ラクダの集合及び各橋について、「ラクダの集合が同時に橋に存在して、耐えられるか？」というのを計算して良い。

ここから各ラクダの集合に対して、「ラクダの集合が一列に並んでいるときのvalidな間隔の最小値」が前計算できる。

ラクダの並べ方を固定する。前計算の情報から、 $O(N^2)$ 個の「$r$番目のラクダと$l$番目のラクダは少なくともOO離れていてはいけない」という制約に帰着する。

これはできる。

$O(N^2N!)$ で解けた。

[提出](https://atcoder.jp/contests/arc105/submissions/59126007)

### 感想

あんまり難しくなかった。CDの難易度が逆転しているっぽくて、それがdiffが高めな原因かも。

## 10/26

1749diff
[ARC072-D Alice&Brown](https://atcoder.jp/contests/arc072/tasks/arc072_b)

### 解法

実験すると $|X - Y|\le 1$　だと後手必勝、それ以外先手必勝と予想できる -> 投げるとAC

[提出](https://atcoder.jp/contests/arc072/submissions/59140764)

### 感想

まともに頭を使おうとした時点で敗北なんだろうな。構築とゲームは別ゲーすぎる。

## 10/27

1750diff
[ARC111-C Too Heavy](https://atcoder.jp/contests/arc111/tasks/arc111_c)

### 解法

$A_{i}$が最小の人を一人取り、$u$とする。$u$と$I_{u}$のswapを試みる。ただし、$I$を$P$の逆置換とする。
- $u = I_{u}$ならばそもそもswapする必要が無く、人$u$は存在しないものとして考えて良い。サイズ$N - 1$の問題に帰着する。
- そうでなくて、$A_{u}\le B_{P_{u}}$ならば、人$u$はswapに参加できない。$u$はずっと荷物を交換できないので条件を満たすことができない。`-1`を出力する。
- そうでないならば、swapする。$A$の最小が$A_{u}$であるという仮定から、人$I_{u}$はこの交換によって疲れることは無い。$u = P_{u}$となったため、サイズ$N - 1$の問題に帰着する。

~~一回の荷物の交換で$P_{i} = i$なる$i$は高々1しか増やせない。この手続きでは一回のswapでそのような$i$を必ず増やしている。~~

よって条件が達成可能ならば、この手続きで操作回数の下界を達成することが可能である。

[提出](https://atcoder.jp/contests/arc111/submissions/59202172)

### 感想

青diffでおっかなびっくりしていたが、結構シンプル