第6回 ドワンゴからの挑戦状 予選

　AとBはそこそこ早く解けたものの、それ以後何もできずに終了。主にCを考えていたけど、Dを考えた方が良かったか。とりあえず、黄色維持には成功しました。

コンテストへのリンク

A - Falling Asleep

　実装問題

B - Fusing Slimes

　期待値系の問題。ABC150のEやABC151のEと似た考え方で解ける。

　このときはABC150のEの復習が済んでおらず、問題を見たとき、「そのせいで解けなかったらどうしよう」と焦った。それより簡単な問題だった（と思う）ので助かった。

C - Cookie Distribution

・かけ算のままでは扱いにくいのでどうするか。

　コンテスト中はあまり良い方法が思いつかず、logを取ったらどうだろう？　などと考えてしまったが、和と積が混じった式なので当然上手くいかない。

　解説動画のように、積を場合の数へ言い換えるのがポイントで、DPに帰着できる。maspyさんのブログを見ると、式計算でもできるようだけど、結構テクニカルに見えてしまう……。

　とりあえず、

・積を場合の数へ言い換えできることがある

　を頭に入れておきます。

D - Arrangement

　コンテスト後に考えたとき、解法ツイートが目に入っていたこともあって、ダメなパターンが、

1.（入力例2のように）残り二個で互いが互いを禁止している場合

　と、

2. 残っている数字のうちにaがあって、X以外の全ての数字が、Xを禁止している場合（は、まずXを選択しないとハマる）

　なことは分かった。厳密な証明は難しくても、ちゃんと考えればここまでは辿りつけそう。

　だけど、その後の実装も結構難しいと思う。

　私は、まず、リストAの各要素の出現回数をカウントしたもの（PythonだとCounter(A)）をリストでもち、heapqにそれらの(カウント数, index)という組を入れて、最大値を管理しました。

　出現回数をカウントしたリストは常に更新していきます。

　なので、heapqで出てきた最大値がMでそれを取る要素がxとなっているけど、それがリストと異なっているときは、リストの方が正しいので、一度heapqから抜き、正しい値をheapqに入れ直します。

　それでも、2.の条件に抵触した場合に限り、2.の条件を適応（つまり、次をXにする）します。

　また、最後は、残り三要素を全探索することで、1.の条件を満たすようにできます。

　これ実装しているときは、こんな大変なことしなくちゃいけないのかなぁ、と思ったけど、今ここにまとめると結構自然な実装な気もする。(もっと簡単に書けますか？）

E - Span Covering

　 解説動画を見てAC。

・とりあえずソート

　今回は、大きい順に見た方が分かりやすそう（早めに全体が埋まったら、後は簡単に計算できることなどから予想できる）

→制約を見るとDPしそう

　というところまではコンテスト中に考えていて、そこまでは正しかった。

　後は何を状態に持てばDPできるか？　ということだけど、今回は、「区間が何個に分かれているか」「区間の長さの総和」を持てば良い。（それが分かれば遷移は書ける）

　確かに、DPで解けるとしたら、状態として持てるものはこれくらいしかなさそうか……。

　これが思いつきにくいのは、途中の計算が問題文の処理中に現れる場合の数と一致していないためだと思う。

　たとえば、入力例1では、最初に2の区間を置くけど、このとき（区間：1、長さの総和：2）のときの場合の数は1。全体5の区間に2を一個置く場合の数4とは異なる。

　なのに、最終的に、（区間：1、長さの総和：全体X）を調べれば答えになっているというのは不思議な感じがしてしまう。

　問題通りの処理をするDPではなく、途中は違っても、

・最終的に答えが一致するDP

　をしなくてはいけない。

　何を使ってDPすれば良いか、柔軟に考えるのが重要か。

　ところで、これと似たDPをどこかで解いたことがある気がしたんだけど、どこだったのかなぁ……。

Codeforces Round #613 (Div. 2)

　Dまでそこそこ早く解けたのでレートは上がったものの、二時間近くあってEが解けなかったのは辛い。

コンテストへのリンク

B. Just Eat It!

　「全ての連続部分列の和が、全体の和より小さい」かどうかを判定する問題

・連続部分列は、元の列から左右を削ったもの

→左右の連続する何個かの列の和が0以下になっていれば良い。

→が、和が負になるためには、片方0以下でなくてはいけないし、片方が負ならそれ以外の部分列をとれば良いので、左右からの累積和を見て０以下の部分があるか調べればOK

C. Fadi and LCM

　 整数$X$が与えられるので、$LCM(a,b)=X$なる$a, b$のうち、$max(a,b)$が最小になるものを求める

・たとえば、8が$X$の約数のとき、$a$か$b$のどちらかは8の倍数になる。LCMを考えているので、片方に2、片方に4のように振り分けることはできない。ならば、中途半端にせず、片方に8を割り振るのがベスト

・なので、どの素因数を$a$に割り振るか調べれば$a, b$の値は定まる。

→bit全探索

D. Dr. Evil Underscores

yukicoderにそのままの問題があったらしいけど、自分はそれは解いてなかった。ただ、別のyukicoderの問題「No.911 ラッキーソート」に近いと感じた。
　そもそも、

・上位bitから0か1かを決めていく

　はXORの問題では重要ですね。

E. Delete a Segment

　けんちょんさんのブログやながたかなさんのブログに解説があります。

　これらの解説や公式解説で共通するのは、各セグメントを見るだけでなく、各時間における重なり合いを見ているところ。つまり、Hello2020のDで書いた「区間のままみるのではなく、時間ごとにみる」という発想の転換を使っている。

　私もコンテスト中にそのことは考えたのだけど、結局、それでそんなに簡単になると思えなかった。実際、そうしても実装は結構大変だと思う。（これらの解説を参考に書いたのがこれです。長くはないけど、「どこで+1するか」とかがややこしくてきつかった）

　だから、（私のコンテスト中の方針である）各セグメントごとに考えてもいけるんじゃないの？　と思って、さっき通したのですが……。非常に大変でした。もっと上手く書けるのかもしれないけれど……。


　一応、このコードでしていることを簡単に書きます。

・とりあえずソートして、

・左右それぞれから、そのセグメントまで順に使ったときのUnionの個数のリストを作る

-左から考えるときは、i番目までの右端の最大値を使えば更新していける。（これをLEFTという名前にします）

-右から考えるとき（この名前をRIGHTとします）が難しい。

★
S[i] = [l,r] としたとき, 左端がr以上のものの中で一番左にあるセグメントが何番目かを二分探索で求める。→x番目だったとする

S[x]=rなら、RIGHT[i]=RIGHT[x]、ではなく、「RIGHT[i+1]～RIGHT[x]の最小値」がRIGHT[i]になる（図がないと分からないと思うけど、どういう図を描けば良いかよく分からないので省略。すみません）。
これを、（RIGHTを値として持ち、区間の最小値を得られる）セグメント木を更新しながら求めていく。

S[x]>rなら、RIGHT[i]は、RIGHT[x]+1、もしくは、R[i+1]～R[x]の最小値。
★


・これを使って、i番目を取り除いたときを考えたい。

-左側はLEFT[i-1]でOK

-右側は、i-1番目までの最大値を使って、★と似たようなことをすれば求まる

　これ、★というほぼ同じことを二回やっていて、その上結局、RIGHTの配列は使ってないから、★は一回にまとめられるはずですよね……。整理すればもう少し簡単になるはずですが、整理するにも頭が混乱してしまい大変です。

　方針としては自然だと思うんだけど、どうでしょう？

AtCoder Beginner Contest 150

　Dで混乱してEにいったらどちらも解けずに終了という散々な出来。Unratedで助かった。

コンテストへのリンク

D - Semi Common Multiple

・（入力例1の）6と10の場合を考えると、LCM+2*LCMかな？　と思う

・だが、6と8の場合を考えると答えが存在しない。2で割ったときの偶奇か、2ベキが関係するかも？

　……と、コンテスト中に考えて、どっちか分からず止まった。立式したらさらに混乱して、「拡張ユークリッドの互除法」を使うの？　などと思ってしまった。

　実際は、「2ベキが一致するとき」を考えるのが正解で、2で割っていくことで2を一つしか因数に含まない場合に帰着していけば良いのだけど、ちょっと思いつきにくい気がする……。

E - Change a Little Bit

・とりあえずソート

→Sの種類が多いので、各Sについて考えるのは無理。Cの各数が何回使われるか、もしくは使われる確率を求めよう！

→今回は、Sを[0, 0, 0](0がN個)として考えても一般性を失わないので考えやすい。

　たとえば、Nが三個のとき、
$S=[0, 0, 0]$ に対して、$T=[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]$
　の八つ。コストが小さい数を後に使う方が良いのは明らかなので、

・index 2 の重みが何回使われるか考えると、SとTでindex 2 が異なるときの4回

・index 1 の重みが何回使われるか考えると、SとTでindex 1 が異なる四つ$[0, 1, 0], [0, 1, 1], [1, 1, 0], [1, 1, 1]$のうち、

-index 2が同じ場合$[0, 1, 0], [1, 1, 0]$は一回ずつ,
-index 2が異なる場合$[0, 1, 1], [1, 1, 1]$は二回ずつ
の計6回

・index 0 の重みが何回使われるか考えると、SとTでindex 0 が異なる四つ$[1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]$のうち、

-index 1,2が共に同じ場合$[1, 0, 0]$は一回
-index 1,2のうち一つが異なる場合$[1, 0, 1], [1, 1, 0]$は二回ずつ
-index 1,2が共に異なる場合$[1, 1, 1]$は三回
で計$1+2*2+3=8$回、のようになる

　ここで、「index 1, ... , N-1のうちi個が異なる場合」というのは二項係数を用いて表せる。
　たとえば、「index 1,2のうち一つが異なる場合」というのは、Combi(2,1)

　これを用いてまとめると、
・index 0の重みがk回使われるのは、Combi(2,k)回と書ける。

　同じようなことが一般のNやindexについて言えることが分かるので、
$(*)1*Combi(x, 0) + 2*Combi(x, 1) + 3*Combi(x, 2) + ... + (x+1) * Combi(x, x)$
　のようなものが高速で計算できれば良いと分かる。

　……と、ここまではコンテスト中に考えていて、ここからどうすれば良いかが分からず解けなかった。考えられる方針としては、

・式変形でどうにかする（OEISを使うことも視野に入れる）

・DP的な方法。$(*)$式で、x-1を利用してxを求める。

　などがあると思うけど、どういうわけかコンテスト中は二番目の方針ばかり考えてしまった。

　式変形でいけるとさえ分かれば、$Combi(x, k)=Combi(x, x-k)$なので、$(*)$式の左側からk番目と右からk番目のCombiは同じなので、まとめられる。そうすると、係数の和が同じ式になるので、

・$Combi(x, 0)+ Combi(x, 1)+ ... + Combi(x, x) =2^x$

　の公式を使って解決できる。

　式変形できないのかな？　と真面目に一分くらい考えていればいけそうだと気付いたはずなので、

・式変形できないか試す！

　のが重要なのかなぁ。

　「方針が立っていたけど解けなかったとき」が一番悔しいんだけど、そういうとき何を反省すべきかも難しい。

　なお、youtubeの公式解説では、二項係数の計算をしていないけど、それはそれで難しい気がする。

F - Xor Shift

　自力では分からず、解説を読んでACしました。

・隣り合った二項のxorを考えると、文字列アルゴリズムに帰着できる

　がポイントですね。

　色々な式変形ができるのに、あえて隣り合った二項のxorを考えるためには、文字列アルゴリズムで何ができるかが頭に入っていることが大切そう。

　公式の解説動画を見てMP法を理解しました。うーん、原理は理解できても、0から実装しろと言われたらきついアルゴリズムですね。

Codeforces Round #612

　Aで時間がかかってしまって混乱したので飛ばし、B、Cを考えていたけれど分からずの0完……。

Div. 2　B. Hyperset

　$O(n^3)$だと厳しいので、どうやって計算量を落とすか、という問題（C++で枝狩りすれば$O(n^3)$で通るようですが）

・半分全列挙で$O(n^2)$に。

→本当に半分だと半分全列挙は思いつきやすいけど、$O(n^3)$を$O(n^2)$に落とすとき思いつきにくくなるので注意。

コンテストへのリンク

A. Garland

・（上手く貪欲すれば解けるらしいけど）制約を見るとDPが自然

→偶奇のどちらを使ったか、偶数・奇数それぞれを何個使ったかを持ってDP。これで$O(n^3)$

・コンテスト中は、i番目を見るとき、今まで使った偶数の個数＋奇数の個数がiになることを使えば$O(n^2)$になるし、DP配列を使い回せばメモリ節約できる……とか混乱してハマった。

→この問題は制約が甘いので、$O(n^3)$で簡単に書けば良い。まあ$O(n^2)$にするだけなら良いと思うけど、後半のDP配列の使い回しは混乱を招くので避けるべきだった。

B. Numbers on Tree

・制約を確認！！

→これも制約が甘いので、単純な$O(n^2)$でOK。葉から貪欲にnodeの値を決め、今まで使った数字の間の値にしたくなったなら、それより大きい数字を一個ずつずらせば良い。

C1. Madhouse (Easy version)

・「全ての部分列」にはかなりの情報量が含まれるので、簡単に決まるのでは？

→1:nと2:nだけで決定できる！

Hello 2020

　今後、参加したコンテストにはできるだけメモを残しておこうと思います。（既に五日も経ってますが……）
　一応、解けた問題は解法を書きますが、厳密さは重視せず、箇条書きっぽく書きます。（解法ツイートの文字数制限ない版、という感じで）

　この回は、Dが解けず、Cまでの三完でした。

コンテストへのリンク

A. New Year and Naming

　実装問題

B. New Year and Ascent Sequence

　n個の配列から二つを選び連結したとき、$a_i<a_j (i<j)$ となる箇所が存在するものが何個あるかを全探索（$O(n^2)$）せずに求める問題。

・そもそも、一つの配列に$a_i<a_j (i<j)$ となる箇所が存在すればどれと連結しても条件を満たす

・そうでないとき、その配列は大きい順にソートされている。

ので、条件を満たすためには、$a_1>a_2>a_3>...>a_n<b_1>b_2>...b_m$のようになっていれば良い.
→あとはソートして、二分探索を使うか、尺取り法でOK。

C. New Year and Permutation

　解法として思い浮かぶのは、

・DP or 数学的にcombinationなどを使う (or OEIS)

　といったあたりか。

→今回はDPは上手くいかないので、数学的に考える
→幅を固定すれば求まる

　幅$k$の配列がhappyになるとき、

- どの数字を選ぶか
- どの位置を選ぶか
- 中身の組み合わせ
- 残りの数字の組み合わせ

　を調べればOK

D. New Year and Conference

　D, Eはアルメリアさんのブログが詳しいです。私はこれを見て通しました。

・とりあえずソート

　は、良いとして、今回は、「開始時間でソートして区間を順番に見ていく」のほかに、「開始、終了時刻をまとめてソートして時間ごとにみていく」という方法があり、後者が正解。

・区間のままみるのではなく、時間ごとにみる

　という発想の転換が重要。

（区間のままでも解く方法はあるかもしれないけど分からなかった。遅延セグ木を使ったり、リストのHashを調べたりする解法もあったけど、この発想の転換は必須？）

E. New Year and Castle Construction

　偏角でソートは思いついていたけど、その後が考察できなかった。
　解説を読んで実装してみたけど、TLEが取れず。Pythonじゃ厳しい？

AtCoder黄色になりました、2019年の振り返り～2020年の目標

　年末のAtCoder Grand Contest 041で黄色になりました！

　また、上がり下がりが激しいのですが、Codeforcesでも薄橙に戻って新年を迎えることができました。

　約一年でAtCoder青→黄色というのは、早い方とは言えないかもしれませんが、自分としてはかなり上手くやった方だと思っています。一年前青になったときは、2020年をAtCoder黄色になって迎えられるとは予想していませんでした。早くとも一年半はかかるだろうと覚悟していました。

　AtCoderを始めて、色の感覚がなんとなく分かった頃から、黄色以上は天才という感覚がありましたし、今もあります。そこに一度でも到達できたということは非常に嬉しいです。

黄色になるまでしたこと

基本的には、この一年やってきたことは青以前と変わりません。

・コンテストに大量に出る→読んで解けなかった問題をできるだけ復習
・AtCoderのStreakを繋げる

　くらい。

　コンテストにはたくさん出ました（2019年のCodeforcesのコンテスト参加回数二位だったらしいです。えぇ……、自分でもちょっと引く）が、効率良く勉強できていたかは疑問。特に、Codeforcesでは解きっぱなしの問題が多くて、あまり身になっていないと思う。
　とはいえ、一年前と比べれば、復習する範囲は広がっています。700点くらいの問題なら解説ACはしなきゃ、と思えるようになりました。ただ、本当に手の届かなそうな問題にチャレンジしたりはしていません。

　AtCoderのStreakは、不慮の事故（リジャッジでAC→TLEになったと思っています。全ての提出がACになるバグが起きていた時期と近いので、まとめてリジャッジされたんではないかと。）で切りましたが、それ以外は繋げることができました。
　でもこれは、やる気のない日に競プロから気持ちが完全に離れてしまうことを防ぐためのものという感じですね。

　というわけで、特別な変化はしていません。環境も変えてないです。エディタもまだIDLEを使っているし……。

　なので、一年前に比べてはっきり実力が付いたかというと疑わしい気もするのですが、まあ多少安定感は増した気はします。一年前は、Pythonの書きやすさ等のおかげで青まで来れたけど、実際の実力は色一つ（レート400）分くらい下なのでは？　という気がしていましたが、今はそこまでの差は感じません。たとえばC++でも、（今すぐは厳しいですが）多少練習すれば青パフォは取れる気がしています。

なんで早く到達できたか

こうした、あまり工夫のない方法で黄色まではいけそうだと思っていたし、実際到達できましたが、じゃあ、なんで早く到達できたか、というと、

・令和ABCが始まり、「レーティング更新対象: 0 - 1999」のコンテストが増えた

　ことが大きかったことは間違いないです。

　自分はそれほど令和ABCという相性が良かったわけではないですが、同じくらいのレートだった人がどんどん黄色に上がっていくのは刺激になりました。
　そして、そのせいで黄色になる実力のボーダーはやや下がったと思います。感覚的には大体レート100くらいずれた印象があります。以前のレート2000と同等の実力と主張したいなら、2100にはならないといけない気がしています。

　あと、

・10月から「ちはやふる３」のアニメが始まった

　ことが大きいですね。いや本当に。

　こういうスポコン系のアニメを見ると、「自分も努力しなきゃ」という気になります。本当のスポコンもの、スポーツで努力している作品を見ても、ちょっと遠い世界に思えてしまい自分を省みることが難しいけれど、こういう文化的な匂いがする作品は刺激になる。
 　競プロ界隈のTwitterで「響け! ユーフォニアム」が話題になっていた時期（劇場版公開の頃です）に、「響け! ユーフォニアム」のおかげでやる気が湧いたというツイートを結構見た気がしますが、自分には「ちはやふる」の方が合っているみたい。（「ユーフォ」は好きだったけど、やる気が出るということはあまりなかった）
　いや、「ちはやふる」では、戦略性の高い個人競技で、元々才能がある人たちがさらに努力している姿を見せていて凄く良いと思う。刺激を受けています。（なお、百人一首は覚えていません）

黄色になる目安

さて、ところで。

　基本的には、AtCoder黄色の目安は、「700点まで全AC」（解説ACでOK。もちろん、解説を理解せずにACしたのではダメですが）くらいだと思っています。これでなれなくても、「800点まで全AC」をすれば9割以上の人は黄色になれるんではないか、と。
（Beatmaniaを知っている人向けに。これはSP難易度表の「地力Aや個人差Aのハード埋め」（よくSP皆伝の目安と言われるが、これを達成して皆伝を取れてない人も意外と多い）、と「A+ハード埋め」と大体対応していると思っています。
　個人的には、こういう風に他のゲームなりの経験を当て嵌めて考えた方が、自分の現在位置を把握する目安になって努力しやすいと思う。だからもっと多くの人に、受験勉強やらゲームやらスポーツやらとの主観的な対応関係を語って欲しい）

　実際は、AtCoderで黄色や橙になっている人のほとんど（もしかすると全員？）が、そこまで埋めずに黄色や橙になっている気がしますが、それは、やっている人が優秀だったり、他で数学やらパズルやらの経験をかなり積んでいたりするからではないか、と。

　実際自分も、700点問題はまだ半分も埋めていない（現状24/63）し、Codeforces等でそれを補う経験を積んできたかというと怪しい（Codeforcesでは、難しい問題は解説ACもできていないことが多い）。
　それでも黄色になれたというのは、他の経験が生きたんだろう、と思っています。ただ、自分の経験が多少なりとも役に立つのはこのあたりまで、という気もしています。

上を目指すにあたって

自分がさらに上へいけるか、というのはかなり疑問に感じています。

　そもそも、自分はどの分野でも（音ゲーもそうですが、音ゲーに限らずどのゲームでも、勉強関連にしても）、せいぜい黄色あたりの実力にしかなったことがない。

　競技プログラミングに関しても、自分のしてきたことは、ここか、もう少し上（高々レート2200あたり）を目指す努力だったと思います。もし、今後もっと上を目指すなら、このままではダメなのではないか、何か方針を定めたり、新しいこと（解説記事を書いたり、作問したりはしてみたい！）をしたりしなくてはいけないのではないか、という気がしています。

　ただ、他方では、別に新しいことをしなくても、「誰でも「800点まで全AC」くらいで黄色になれる」のなら、「誰でも「1000点まで全AC」くらいで橙になれる」のでは？　とも思っています。
　しかし、現実には800～1000点あたりの問題は解説（や他の人のコード）を読んでもなかなか理解できないので、容易ではないですね。

競技プログラミングで差が出る部分

唐突ですが、競技プログラミングの実力向上に関して、一番差が出るのは、

・解説を読んで理解する能力の差

　だと思っています。以下、その説明のため、エセ科学みたいな怪しい内容を書きます。

　問題を解くことのみで競技プログラミングの実力を上げる場合、

・問題の練習量

　から、

・忘却量

　を除いたものが実力になると思います。
　なので、同じ問題セットを解くなら、短い時間で解いた方が実力は向上するはずです。忘却量が少ないので。

　ところで、最近、

・一問を解いたときの学習量

　は人によってあまり変わらないんじゃないか？　と思うようになりました。「一を聞いて十を知る」というようなことはない。一問から得られる経験値は誰でもあまり変わらず、もし十を知ったように見えた人がいたならそれは、その人に既に他の知識があり、それと結びつけることができたため十を知ったように見えたんじゃないか、と。
　競技プログラミングを始める前はあまり分からなかったんですが、優秀な人の成長の様子等を見ているうちにそう思うようになりました。

　でも、同じくらいの時間と熱意で努力していても人によって結構差が出るように思えますよね。その差の一番の原因が、

・解説を読んで理解する能力の差

　じゃないかと。同じ問題セットを解いた（自力ACもしくは解説ACする）ときの実力向上はそこまで差が出ないけど、理解するまでの時間にはかなり差が出る気がします。

解説を読んで理解する能力

とはいえ、誰でも、（主に数学関係の）勉強する上で一番苦労するのが、この、「解説を読んで理解する」部分だと思うので、人によってどの程度差があるかはよく分からないんですよね。実力によらず、この部分が苦手だと思っている人は多い気がする（そういうツイート等もしばしば見かける）。

　今の自分の場合、AtCoderの公式解説を読んですんなり理解できるのは400点問題くらいまで。500点くらいの自力で解ける問題でも、公式解説をすぐには理解できないことは結構あります。また、700点～くらいの問題は時間をかけても理解できないことが多いです。

　まあでも、公式解説は結構簡潔に書いてあるし、こんなものか、とも思うのですが、ブログなど非公式の解説で（分かった後に読み返せば）ほぼ行間のないような丁寧なものでも、700点～くらの問題だとその場では理解できないことが結構多いし、理解できたとしても、一時間くらいはかかることが多い。これは遅い方なんじゃないかと。

　多分、この原因の一つは、自分が小説を読むように解説を読んでしまう、というところにある気がします。

　数学的な文章でも、まず小説を読むときのような読み方（緩く全体像を捉えよう、というような）をして、それで分からなかったときに、一行一行を論理を追うような読み方をする。で、論理を追っただけでは理解できず（した気になれず？）それを自分のストーリーに当てはめてようやく理解できた気になるんじゃないかな、と。
　だから多分、二度手間になってるんですよね。最初から数学的・論理的な読み方をして、数学的な理解＝自分の理解となるなら、もっと早く理解できるんじゃないか、と。昔から悩んでいることなのですが、そもそも、頭の中の知識の整理の仕方が、他人と比べて論理的な配置になっていないような気がしているので……。
　理解が早い人は、数学的内容をそのまま（ではなくても、それに近い形）理解していて、そこら辺で差がついてるんじゃないかなぁ……。

解説を読んで理解しなさい

……と、ここまで書いてちょっと放置していたのですが、その間に、いや、さすがにこれは甘えてるのでは？　と思えてきました。

・解説にギャップがあって理解できない
・解説であまりなじみのない概念（データ構造など）を使っているため理解できない

　のは仕方ないと思います。自分は、Union-Findや遅延Segment treeを理解するのに数日～一週間程度かかりました。まあ、そういう（分かってしまえば簡単なものでも）新しい概念を受け入れるのに時間がかかる（もしくは時間をかけても分からない）のは仕方ない。
　また、頭の中のデータ構造（？）に問題があるというのも、（その真偽はともかく）どうしようもない。
　けれど、

・適正問題で、特に未知の概念もなく、ギャップもない解説を理解できない

　というのはさすがにダメでは？

　実際問題として、そういう解説なら、ちゃんと数学書を読むときのように論理を追って読めば、（文体が合わなかったりして、なぜか理解しにくい部分があったとしても）長くとも一時間～二時間程度かければ理解できるのでは？
　そういう問題・解説を結構諦めてしまっていたのは、やる気がなかったからと言われても仕方ない気が。いや実際、論理をしっかり追って読むと疲労するので、途中で寝てそのまま諦めてしまうことも多かったような。

　そして、競技プログラミングでは、ありがたいことにそういう問題や解説を選ぶことができます。（その勉強しやすさこそ、競技プログラミングの一番の良さだと思っています。）
　適正問題かどうかは問題の点数やAC人数から分かるし、（どの問題も、というわけではないですが、1000点くらいまでの問題なら結構高確率で）ギャップの少ない解説を書いてくれている人がいます。

　レート2000前後という自分くらいの段階なら、解説自体が難解なほどの問題（の解説を理解すること）に挑戦する必要はないはず。なので、まずは、理解できるはずの（しなくてはいけない）解説をしっかり理解し、ACすることですね。
　これを繰り返せば700～1000点問題のかなりの部分が埋まるはずだし、それで橙近くまではいけるのでは？

　競技プログラミングに関してこれを今年の目標にします。