はじめに

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

問題集

ABC303 E - A Gift From the Stars

問題

星グラフに毛を生やしてつなげちゃった
毛を切って復元しよう

感想

初めて挑戦したグラフ問題
解法がおもしろいとおもった
入力例2のグラフ

AGC017 A - Biscuits

問題

ビスケットが奇数個入った袋と偶数個入った袋がいくつか与えられる。
袋はいくつでも選択してよく、選択した袋の中のすべてを食べる。
食べる個数を奇数個にする組み合わせは何通り？
偶数個にする組み合わせは何通り？

感想

解説の解法がとても面白かった（小並感）
僕の解法

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  # 奇数個の袋を奇数個選ぶ組み合わせ

解説の解法

if num_odd == 0:  # すべて偶数の時
    if P == 0:  # 偶数個食べたいなら
        print(2 ** N)  # 任意の選び方をしていい
    else:  # 奇数個食べたいなら
        print(0)  # 無理
else:  # 奇数が一つでも混ざっているとき
    print(2 ** (N-1))  # これでいいみたい

解説を読んだら雰囲気は伝わってきたけど難しい

Code Festival 2017 Final B - Palindrome-phobia

問題

a, b, cのみからなる文字列Sを並び替えて回文を含まないようにできるか？

感想

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

ABC 096 D - Five, Five Everywhere

問題

55555以下の素数55個を選び、どの5個の和も合成数になるようにしろ。

感想

55555以下の素数から55個選ぶのは

num_primes = 5637  # 55555以下の素数の個数
comb(num_primes, 55)  # 12279509736240630295872230609749835176075446268539023044427833079338455863836350516172941356136528886172125091535625620544893414278400

で不可能。
DFSやってみたけどせいぜい10個しか選べなかった。
どうやって選ぶ？となったときに、5個の数の和が何かの倍数になるように設定することで作ることができる。
解説がすごく分かりやすかった

てみじかまとめ

ABC313 D - Odd or Even

N=4, K=3のときの問題を界隈外の人に見せたら競プロの説明として面白そう

ARC023 B - 謎の人物X

D回の遷移をsetでまとめて高速化？と思いきや間に合わない
ある程度の回数（左上から右端まで動けるだけの回数）遷移した後は，単純な2周期の繰り返しであることを利用する．

D回の移動で届かないマスのコストを全部0にする
Dが偶数か奇数か求める
Dが偶数なら，grid[i][j]のi+jが偶数のマスのみに行けて，奇数ならi+jが奇数のマスのみに行ける
行けるマスの中で最大値を求める
周期性を可視化できて，面白い

ABC184 C - Super Ryuma

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

ABC 085 D - Katana Thrower

解説に書いてある方法で解く必要はないけど、面白いことが書いてあった。

ABC 126 D - Even Relation

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

ABC 242 D - ABC Transform

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

ABC 296 E - Transition Game

青木君にはお手軽最強行動が1つ存在する。

CADDi 2018 D - Harlequin

解説見てびっくり。
1行でACできます。