https://atcoder.jp/contests/abc206/submissions/49840456
https://chat.openai.com/share/2b95654c-5852-4f49-a048-e83ca2a4222f
k枚の靴下Aに対して、、相異なるi, j を選ぶとき、Σ |Ai - Aj| が最小となるものを求めてください。 ただし、kが奇数の時は1枚あまるよ。
直感的に、前から二枚ずつ選んで行ったら良さそう。
こんがらがった。 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(から我々)を救いたい。
AtCoderにおいてD問題はDPのD!と呼ばれるほど頻出のテクニックであるDP(動的計画法、Dynamic Programming)のまとめ・解説です。
頻出形だが理解が難しいのが困るところ。
D - Step Up Robot
Diff: 551
典型的な1次元DP。
ロボットが階段の0段目からX段目まで登れるかどうかを判定する。
ロボットはAi段飛ばしで階段を登ることができ、また階段のBi段目には餅が置いてあり登れない。
dp[i] = i段目に登る方法
配るDP: dp[i+a[v]] += dp[i] + a[v] (ただし遷移先には餅がない)
E - Come Back Quickly
Diff:1323
https://kenkoooo.com/atcoder/#/contest/show/b57b32ea-19c0-4724-ab73-f7839e0cae86
4問目
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が3の倍数でない時はたどり着けない。
また、コンビネーションを求めるのに逆元を用いる。
5問目
atcoder.jp
AtCoder Beginner Contest 174 - YouTube
よくわからん
6問目
atcoder.jp
AtCoder Beginner Contest 214 D~F 解説 - YouTube
https://twitter.com/kyopro_friends/status/1426540512173985795
よくわからん
★DP+重複をどうやって避けるか
問題:
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の時に注意)