AtCoder 面白かった問題集（随時追加）

# はじめに
水色コーダーになりました（希望）
面白いと思った問題を貼っておいて、いつでも振り返れるようにしようと思いました。
感想の項に普通に解法書いちゃってるので解きたい方は気を付けてください。
多分ほとんど更新されません。

# 問題集
## ABC303 E - A Gift From the Stars
### 問題
星グラフに毛を生やしてつなげちゃった
毛を切って復元しよう
### 感想
初めて挑戦したグラフ問題
解法がおもしろいとおもった
入力例2のグラフ
![Figure_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1119776/57a4057b-b6bf-b3be-8852-f3f6e152c431.png)

https://atcoder.jp/contests/abc303/tasks/abc303_e

## AGC017 A - Biscuits
### 問題
ビスケットが奇数個入った袋と偶数個入った袋がいくつか与えられる。
袋はいくつでも選択してよく、選択した袋の中のすべてを食べる。
食べる個数を奇数個にする組み合わせは何通り？
偶数個にする組み合わせは何通り？
## 感想
解説の解法がとても面白かった（小並感）
僕の解法
```Python3
if P == 0:  # 食べる個数を偶数個にしたいとき
    # 奇数個の袋を偶数個選ぶ組み合わせ
    choice_odd = 1  # 何も選ばないのが1通り
    for i in range(2, num_odd+1, 2):  # 2, 4, 6, ...個選ぶとき
        choice_odd += math.comb(num_odd, i)  # 組み合わせを足す
    print(choice_odd * (2 ** num_even))  # 奇数袋を偶数個選ぶ組み合わせと、偶数袋を任意個選ぶ組み合わせ
else:  # 食べる個数を奇数個にしたいとき
    pass  # 奇数個の袋を奇数個選ぶ組み合わせ
```
解説の解法
```Python3
if num_odd == 0:  # すべて偶数の時
    if P == 0:  # 偶数個食べたいなら
        print(2 ** N)  # 任意の選び方をしていい
    else:  # 奇数個食べたいなら
        print(0)  # 無理
else:  # 奇数が一つでも混ざっているとき
    print(2 ** (N-1))  # これでいいみたい
```
解説を読んだら雰囲気は伝わってきたけど難しい

https://atcoder.jp/contests/agc017/tasks/agc017_a

## Code Festival 2017 Final B - Palindrome-phobia
### 問題
a, b, cのみからなる文字列Sを並び替えて回文を含まないようにできるか？

### 感想
偶数文字からなる回文は中心に2文字の回文を含み、奇数文字からなるものは中心に3文字の回文を含む。
ここから、「2文字・3文字の回文を含まない文字列が作れるか？」という風に言い換えることができる。
それは結構単純に求めることができる。解説参照

https://atcoder.jp/contests/cf17-final/tasks/cf17_final_b

## ABC 096 D - Five, Five Everywhere
### 問題
55555以下の素数55個を選び、どの5個の和も合成数になるようにしろ。
### 感想
55555以下の素数から55個選ぶのは
```Python3
num_primes = 5637  # 55555以下の素数の個数
comb(num_primes, 55)  # 12279509736240630295872230609749835176075446268539023044427833079338455863836350516172941356136528886172125091535625620544893414278400
```
で不可能。
DFSやってみたけどせいぜい10個しか選べなかった。
どうやって選ぶ？となったときに、5個の数の和が**何か**の倍数になるように設定することで作ることができる。
解説がすごく分かりやすかった

https://atcoder.jp/contests/abc096/tasks/abc096_d

# てみじかまとめ
## ABC313 D - Odd or Even
N=4, K=3のときの問題を界隈外の人に見せたら競プロの説明として面白そう

https://atcoder.jp/contests/abc313/tasks/abc313_d

## ARC023 B - 謎の人物X
D回の遷移をsetでまとめて高速化？と思いきや間に合わない
ある程度の回数（左上から右端まで動けるだけの回数）遷移した後は，単純な2周期の繰り返しであることを利用する．
1. D回の移動で届かないマスのコストを全部0にする
1. Dが偶数か奇数か求める
1. Dが偶数なら，`grid[i][j]`の`i+j`が偶数のマスのみに行けて，奇数なら`i+j`が奇数のマスのみに行ける
1. 行けるマスの中で最大値を求める
周期性を可視化できて，面白い

https://atcoder.jp/contests/arc023/tasks/arc023_2

## ABC184 C - Super Ryuma
↑のARC023Bと同じように、初期位置からマンハッタン距離が偶数離れたポイントにはどれだけ遠くても高々2回の移動で行けることが重要。
馬要素は分かるけど竜かな？と個人的に思った。

https://atcoder.jp/contests/abc184/tasks/abc184_c

## ABC 085 D - Katana Thrower
解説に書いてある方法で解く必要はないけど、面白いことが書いてあった。

https://atcoder.jp/contests/abc085/tasks/abc085_d

## ABC 126 D - Even Relation
問題文だけ読むと、使うべきアルゴリズムが全く想像できず、難しそうに思える。
何かに気が付くと一発ギャグだということが判明する。

https://atcoder.jp/contests/abc126/tasks/abc126_d

## ABC 242 D - ABC Transform
1e18回の遷移をクエリごとにやらされるのか...となる。
実際にはそんなことはなく、2つの事実に気づければ解ける問題になっている。

https://atcoder.jp/contests/abc126/tasks/abc126_d

## ABC 296 E - Transition Game
青木君にはお手軽最強行動が1つ存在する。

https://atcoder.jp/contests/abc296/tasks/abc296_e

## CADDi 2018 D - Harlequin
解説見てびっくり。
1行でACできます。

https://atcoder.jp/contests/caddi2018/tasks/caddi2018_b