# ARC1日1問 10/14~10/20

## 10/14

試験管556diff
[ARC030-A 閉路グラフ](https://atcoder.jp/contests/arc030/tasks/arc030_1)

[提出](https://atcoder.jp/contests/arc030/submissions/58814070)

### 感想

特に言うことなし

## 10/15

504diff
[ARC179-A Partition](https://atcoder.jp/contests/arc179/tasks/arc179_a)

### 解法

$K \ge 0$ ならば、 $K$ 未満の値が累積和に出てきてはいけない。累積和の各値を極力大きくしたい -> $A$ を降順にならべる。

$K \lt 0$ ならば、序盤に累積和上の $K$ 未満の値をかき集めたい -> $A$ を昇順に並べる。

[提出](https://atcoder.jp/contests/arc179/submissions/58822972)

### 感想

うーん。

## 10/16

2092diff
[ARC127-C Binary Strings](https://atcoder.jp/contests/arc127/tasks/arc127_c)

### 解法

1桁目は必ずであるので、2桁目以降から前から順番に桁数を確定させていく。

$i$ 桁目を決めるとき、候補が三つある
- $i$ 桁目が無い (現在の文字列が解である)
- 0とする
- 1とする

$X = 1_{(2)}$ のときは $i$ 桁目が無い。現在の文字列が解である。

$i$ 桁目が0 であって $i + 1$ 桁目から $N$ 桁目を決める通り数は $2^{N - i + 1} - 1$ 通りある。

このことから、 $2 \le X\le 2^{N - i + 1}$ ならば $i$ 桁目は0であり、$i + 1$ 桁目以降の辞書順 $X - 1$ 番目を求めることに帰着する。そうでなければ $i$ 桁目は $1$ であり、 $i + 1$ 桁目以降の辞書順 $X - 2^{N - i + 1}$ 番目を求めることに帰着する。

愚直にこれを実行しようとすると、 $N$ 桁の二進数の引き算や大小比較を沢山やるので大変なことになる。ここで冷静になる。

**大小比較**

大小比較する値は $(2^{N - 1}, 2^{N - 2}, 2^{N - 3}, \dots, 2^{0})$ であり、この順なので、一番左の立っているbitと立っているbitの数さえわかればできる。

**引き算**

「大小比較」での議論より、 $2^{N - i + 1}$ 引く = $X$ の最左のbitを外すだけ

$1$ 引くのはたかだか1回 $O(|X|)$ かかったあと、後は $O(\log N)$ 回のbit操作で抑えられる

以上より $X$ の立っている1をdequeで頑張ればできる。

[提出](https://atcoder.jp/contests/arc127/submissions/58846032)

### 感想

辞書順 $X$ 番目を求めろ問題はやることが決まっているので、助かる。

## 10/17

731diff
[ARC070-C Go Home](https://atcoder.jp/contests/arc070/tasks/arc070_a)

### 解法

毎回右に飛ぶとして、$i$回目で座標が$X$以上になったとする。このときの現在の座標を$X'$とすると$0\le X'-X\lt i$ が成り立つ。すなわちこれまでの右のジャンプをたかだか一個取り消せば座標をちょうど $X$ にすることができる。結局解は $i$

[提出](https://atcoder.jp/contests/arc070/submissions/58867170)

### 感想

ちょっとおもしろい。yukicoderとかでありそうな問題設定。

## 10/18

1332diff
[ARC185-B +1 and -1](https://atcoder.jp/contests/arc185/tasks/arc185_b)

### 解法

$i = 2, 3, \dots, N$ の順に $A_{i}$を調整していく。

$A_{i - 1} \gt A_{i}$ならば、後ろから$A_{i - 1} - A_{i}$だけもらうことにする。もらうことができなかったらNoと出力する。$A_{i} \leftarrow A_{i - 1}$とする。

$A_{i - 1}\lt A_{i}$ ならば、($A_{i + 1}$以降のことを考えると)$A_{i}$はできるだけ小さい値になって欲しい。$A_{i}$からどれだけ前に配れうかを二分探索で調べる -> 実際に前に値を配る

1ケースあたり$O(N\log N)$

[提出](https://atcoder.jp/contests/arc185/submissions/58897045)

### 感想

二分探索内の不等号を逆にしてしまい完全にコードが壊れていたのにサンプル全部通ってしまった。サンプル作りが上手ですねぇ

## 10/19

試験管861diff
[ARC042-A 掲示板](https://atcoder.jp/contests/arc042/tasks/arc042_a)

[提出](https://atcoder.jp/contests/arc042/submissions/58931479)

### 感想
特になし

## 10/20

試験管1111diff
[ARC023-B 謎の人物X](https://atcoder.jp/contests/arc023/tasks/arc023_2)

[提出](https://atcoder.jp/contests/arc023/submissions/59017593)

### 感想
特になし