https://atcoder.jp/contests/abc206/submissions/49840456
https://chat.openai.com/share/2b95654c-5852-4f49-a048-e83ca2a4222f
ABC335 C Socks 2
問題
提出コード
問題要約
k枚の靴下Aに対して、、相異なるi, j を選ぶとき、Σ |Ai - Aj| が最小となるものを求めてください。 ただし、kが奇数の時は1枚あまるよ。
k が偶数のとき
直感的に、前から二枚ずつ選んで行ったら良さそう。
k が奇数のとき
こんがらがった。 k枚の靴下のうち、選ばないものを全探索する。 [2, 3] [4, 5] [6, 7] [1 3] [4, 5] [6, 7] [1, 2] [4, 5] [6, 7] [1, 2] [3, 4] [6, 7] このように、偶数番目と奇数番目で推移がことなりややこしい => 偶数と奇数で分ければよい！ ただし、実際は奇数番目のみでよいらしい？
雑
4月は環境が変わってバタバタしてたが、5月も中頃に差し掛かり新しい生活にも慣れてきた。
競プロ
最近は一日一問緑の問題を解いている。一週間のうちに解く緑7問を日曜日に選定し、一日一問ずつ解いている。
先週までは帰宅後問題を見ていたが、通勤時や昼休みなど割と手持ち無沙汰な隙間時間が存在しているため、最近は前日や週頭に問題を閲覧し、頭のスタック領域に入れている（ヒープ領域かもしれない）。
そのおかげか、緑の問題も解けることが多々ある。脳内で無意識のうちに解法を考えているのかもしれない。
麻雀
鬼畜悪魔の囁きにより、しばらく離れていた麻雀の熱が再燃してしまった。昼休みに一局、帰ってから数局打っている。麻雀は拘束時間が長いので控えたいという気持ちもあるが、🥴である。
千羽黒乃本2も購入した。何切る本もぼちぼち読み進めている。とりあえず雀聖とは言わないので、雀豪2に上がりたい。
ゲーム
FF7Rを買った。第一印象はお花の子が好き。でもティファも好き。多分爆弾の子も好きになる。
スプラも楽しい。時間がない。
最近は睡眠に失敗し続けて辛いので早く寝たい。布団に入って1時間以上経過した🦴。
DPを救いたい
DPの問題のまとめ
我々の前に常に立ちはだかるDP（から我々）を救いたい。
AtCoderにおいてD問題はDPのD!と呼ばれるほど頻出のテクニックであるDP（動的計画法、Dynamic Programming）のまとめ・解説です。
頻出形だが理解が難しいのが困るところ。
D - Step Up Robot
Diff: 551
典型的な１次元DP。
ロボットが階段の０段目からX段目まで登れるかどうかを判定する。
ロボットはAi段飛ばしで階段を登ることができ、また階段のBi段目には餅が置いてあり登れない。
dp[i] = i段目に登る方法
配るDP： dp[i+a[v]] += dp[i] + a[v] (ただし遷移先には餅がない)
ダイクストラまとめ
E - Come Back Quickly
Diff:1323
まよコン 2023-02-17
https://kenkoooo.com/atcoder/#/contest/show/b57b32ea-19c0-4724-ab73-f7839e0cae86
４問目
atcoder.jp
（+1, +2）, (+2, +1)
★マスの移動は下記のように分解できる。
(+1, +2 ) = (0, 1) + (1, 1)
(+2, +1 ) = (1, 0) + (1, 1)
n * m の格子点の左下から右上に行く問題に帰着できる。
また、一回移動するたびに x + y = +3
移動回数をnとすると
合計でn回移動するため、目標地点（格子の右上の点）は(X-n, Y-n) となる。
これを (A, B) とすると
↑と→の矢印の並べ方
により答えが求められる。
なお、X+Yが３の倍数でない時はたどり着けない。
また、コンビネーションを求めるのに逆元を用いる。
５問目
atcoder.jp
AtCoder Beginner Contest 174 - YouTube
よくわからん
６問目
atcoder.jp
AtCoder Beginner Contest 214 D~F 解説 - YouTube
https://twitter.com/kyopro_friends/status/1426540512173985795
よくわからん
★DP＋重複をどうやって避けるか
競プロ典型90問-007
問題：
https://atcoder.jp/contests/typical90/tasks/typical90_g
解説：
kyopro_educational_90/007.jpg at main · E869120/kyopro_educational_90 · GitHub
愚直に計算するとO(300,000 ^ 2)で到底間に合わないので二分探索を用いる必要がある。
C++のライブラリには、lower_bound()なる便利なものがあるらしい。
方針としては、
①Aをソートする
②Bの各要素に対し、B[i] <= A[j] となる最小のjを探す(ここでlower_bound()を用いる)
⓷解の候補は j or j-1 (j=0の時に注意)
