(cache)けんちょん@競プロ (@drken

11h

同じ ACL 投入アルゴリズムなのに、ガンガン Difficulty が下がっていくセグ木と、一向に Difficulty が下がる気配のないフロー。一体どこで差がついたのか……！！！

いよいよ JAG のフロー三銃士・How to Create a Goog Game ・Longest Shortest Path ・Cost Performance Flow を倒すぞーーー！！！！！！！！！！！

518

Who to follow

数学やプログラミングを頑張る中学生・高校生を応援したい／開成卒 → UT数理情報卒 → 数理システム(顧問)・モノグサ／競プロ (AtCoder highest 2503, 2019年3月)／「けんちょん本」著者／Qiita 5 位／JOI 育成強化委員／ボルダリング／旅好き／ENFJ

AtCoderで解説放送してる人。アイコンは時計になってました。（今はもう動かない）毎日ツイートをしようという気持ちを持つことにしました。

フォルシア株式会社エンジニア。AtCoderに復帰しようと思うかどうかを検討することが目標かもしれません。

みさわさん神すぎる！！！！！フローの理解度めちゃくちゃ上がった！！！！！

Replying to

需要供給の上下限、辺流量の上下限、負辺あり ↓ 超頂点からの辺流量上下限を追加して、辺流量上下限付き、負辺ありの循環流 ↓ 順辺と逆辺のうちコストが非負な方の下限制約(=非正な辺の上限制約)を満たすように予めpushして、負辺無し、辺流量上限付きのb-フローとか帰着するといいかもです。

長方形領域内の点の個数を求める問題は、Yosupo Library Checker にある！！ judge.yosupo.jp/problem/rectan 過去にこれを通しておいたおかげで、Wavelet Matrix を貼るだけで対応できた！！！！！

Quote

けんちょん@競プロ

@drken_procon

Feb 13

Replying to @drken_procon

ARC 214 E - Swap K times（4D、橙色） atcoder.jp/contests/arc21 ・同じ数を複数含むと、数の対応付けが一意でないことに注意・数の対応が偶置換・奇置換の場合の最小swap回数をそれぞれ求めればよい・同じ数値同士のswapを挟むケースの操作回数の増分は「長方形内の点の個数」を求める問題に帰着

精進木、僕も作ろう！

ABC 444 F - Half and Median（4D、橙色） atcoder.jp/contests/abc44 ・とにかくしんどかった・ランテス書いて地道に原因を潰した・「(N+M+1)/2 個の x 以上を総和最小でとって、残りを全部 1 にしても合計が N+M 個に達しない場合はダメ」←激ヤバコーナーケース

Quote

けんちょん@競プロ

@drken_procon

Feb 11

ああ！！！！！！！！！！！苦しかったーーー！！！！！！！！！！ ABC 444 F、やっと通ったあああ！！！！！！！！

ARC 214 E - Swap K times（4D、橙色） atcoder.jp/contests/arc21 ・同じ数を複数含むと、数の対応付けが一意でないことに注意・数の対応が偶置換・奇置換の場合の最小swap回数をそれぞれ求めればよい・同じ数値同士のswapを挟むケースの操作回数の増分は「長方形内の点の個数」を求める問題に帰着

Submission #73264628 - AtCoder Regular Contest 214

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

ABC-like のラスボス（Difficulty：3383）をついに倒して、これで ABC-like が全て埋まった！！！！！

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

H - Shipping

Difficulty 3384 で 4D 付けるのバグかもだけど、でも、5 時間コンテストだったら Difficulty が大きく下がるタイプの問題だとは思う。 ABC F 級問題を 4 つ解かされる感じ！！！

Quote

けんちょん@競プロ

@drken_procon

Feb 13

Replying to @drken_procon

第二回日本最強プログラマー学生選手権 H - Shipping（4D、Diff 3384） atcoder.jp/contests/jsc20 ・実装激重！！・なもりグラフの髭の部分は LCA したり、木上の imos したりで処理できる・なもりグラフのサイクルの部分は、「使わない辺」を全探索する。その際に遅延セグ木を使って差分更新できる

ABC 444 G - Kyoen（5D、Diff 3117） atcoder.jp/contests/abc44 ・初めての ABC 675 点問題完全自力 AC！！・ノルムが N のガウス整数のうち、C で割った余りが A+Bi のものを数え上げる・素因数 P ごとに、e = 0, 1, ..., E に対して P^e × conj(P)^{E-e} を C で割った余りの個数分布を求めて DP

Submission #73147545 - AtCoder Beginner Contest 444

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

第二回日本最強プログラマー学生選手権 H - Shipping（4D、Diff 3384） atcoder.jp/contests/jsc20 ・実装激重！！・なもりグラフの髭の部分は LCA したり、木上の imos したりで処理できる・なもりグラフのサイクルの部分は、「使わない辺」を全探索する。その際に遅延セグ木を使って差分更新できる

Submission #73252023 - Japanese Student Championship 2021

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

【第四試練】セグ木編、遅ればせながら完走できた！

Quote

岩井星人

@yiwiy9

Jan 20

Replying to @yiwiy9

【第四試練】セグメント木（遅延はしないやつ）の徹底練習ジム！（NoviSteps 1Q〜2D） kenkoooo.com/atcoder/#/cont

この傾向が、難易度 1〜9 までは成り立つことを確認していて、難易度 10〜12 は正直に言うと僕はまともに解けないことが多いのだけど、それでもきっとこの法則が成り立つだろうと推測している。　つまり、難易度 12 易しめは 5D、難易度 12 難しめは 6D だろうと思っている。

Quote

けんちょん@競プロ

@drken_procon

Feb 13

JOI 難易度と NoviSteps グレードの対応こんな感じ難易度 6 易しめ → 2Q 難易度 6 難しめ → 1Q 難易度 7 易しめ → 1Q 難易度 7 難しめ → 1D 難易度 8 易しめ → 1D 難易度 8 難しめ → 2D 難易度 9 易しめ → 2D 難易度 9 難しめ → 3D 難易度 10 易しめ → 3D 難易度 10 難しめ → 4D

JOI 難易度と NoviSteps グレードの対応こんな感じ難易度 6 易しめ → 2Q 難易度 6 難しめ → 1Q 難易度 7 易しめ → 1Q 難易度 7 難しめ → 1D 難易度 8 易しめ → 1D 難易度 8 難しめ → 2D 難易度 9 易しめ → 2D 難易度 9 難しめ → 3D 難易度 10 易しめ → 3D 難易度 10 難しめ → 4D

これ、ずらしてしまったのはミスったと少し思っている。 2024 年時点での AtCoder の色に合わせることを優先した結果、JOI 難易度とはズレてしまった。

互いに関連し合ってる 1D 典型たち・LCA ・ダブリング・行列累乗これらを同じグレードとするのはとても自然だと思う！！！

出た！！！！！ 1D 初出の典型！！！！！！！ ABC 212〜318 の 1D 埋めは、こういうの無数に拾えて良き！！！！！！

Quote

りうる/ Un_titled

@masp_3

Feb 13

またこういうアルファベット三文字のでてきた LCAってなんやねん LISみたいな名前しとるし！！！

岩井星人さん、しっかり地力が上がって来ている感じがあって、すごく良き！！！僕も頑張らねば！！！！

昨日 3 時間実装した後、昼休みに解こうとしたら 2 時間かかってしまった…！！！合計 5 時間。 Difficulty 3338 でも個別のステップはすべて ABC-F レベルだった。こういう問題もあるんだね！！！

こういうのが、JOI では難易度 11 が付きがちな気がする。

昨日の ABC-E に触発されて、エラトステネスの篩でできることを特集した記事を書こうか迷ってたら 1 日が過ぎてた…… ・エラトステネスの篩自体・高速素因数分解・高速約数列挙・メビウス関数テーブル・約数系包除原理・添字 GCD 畳み込み辺りの素養を総まとめする記事的なやつ。

Dec 4, 2020

競プロ専用のアカウントを新設してみました。

競プロブログ執筆再開する！！

18 位！！！！！！！！！！ (順位表からわかる情報) 令和 ABC 過去最高順位きたーー！！！！！！！今まで散々早解きダメダメ言ってたけど、やればできるんだーー！！！！！！！！！！！！！！！！

Dec 29, 2020

ガウス整数とか大好きなんだけど、広めるには問題例が少な過ぎる……

競プロerと言えども、(毎週コンテスト出る層で) 平均年収はたぶん 400 万くらいだと思うので、Indeed の示す数値に見慣れてしまうと感覚バグります…

Jan 25, 2021

競プロ界で「知識」と呼ばれるものこそ、歴史的天才たちが挑んできた真の「天才パズル」で、そのパズルを本気で楽しみながら論理地力を上げられる人にとっては、知識獲得志向がなんら弊害にならないのでは…という説

Mar 24, 2022

半年ぶりに何書こうか考えたとき、真っ先に競プロ典型90問が浮かんだ。「とりあえずこれ解くといいよ」と言える問題集があるのって、やっぱりすごくいいよね。

Oct 8, 2021

このアカウント動かすのすごく久しぶりだけど、また競プロのこと書いたり、ブログ投稿したりしていきたい！

From drken1215.hatenablog.com

Nov 16, 2025

ABC 432 C - Candy Tribulation 苦しんでいる方が多そうだったので、久しぶりに詳細な解説記事を書いてみました！！！！ drken1215.hatenablog.com/entry/2025/11/ ポイントは、各人に配る飴の総重量 P を決め打つと、各人に配る小さい飴・大きい飴の個数が一意に決まる、ということに気づくかどうかだと思います！！

中国剰余定理たとえば受験とかで「3 で割って x 余り、5 で割って y 余る整数はなんでしょう」という問題で頻出です。その答えが「15 で割って z 余る数」というふうになることはよく知られています。 (x, y) を決めると、z がただ一つに決まるというのが、中国剰余定理の主張です！！

Jan 3, 2024

REP マクロを取り入れるか迷う。 ● 入れたくない理由解説記事を書くときに、REP マクロを外したコードを書き直すのが面倒 (解説記事のコードに REP マクロはしない) ● 入れたい理由単純にコーディングが早くなりそう

Library Checker で僕史上初めて fastest が取れた！！！問題：Inv of Formal Power Series (Sparse)

昨日の ABC B 問題みたいなやつ、どうしようもなく苦手なんだけど、どうしようもない……

座標圧縮 (座圧) - けんちょんの競プロ精進記録

Aug 9, 2021

はてなブログに投稿しました #はてなブログ座標圧縮 (座圧) - けんちょんの競プロ精進記録

drken1215.hatenablog.com

競技プログラミングで時々問われる「座標圧縮」について簡単に解説します。 1. 座標圧縮とは数列が与えられたときに、それぞれの要素が「全体の中で何番目に小さいか」を求めていく作業を、競プロ界では座標圧縮 (座圧) とよびます。たとえば A = (8, 100, 33, 12, 6, 1211) に対しては、座標圧縮…

Dec 26, 2020

パンケーキ、全探索するだけなんだけど、全探索するだけという視点は、AtCoder だけやっててもなかなか身に付かないかも…… AtCoder だったら、こんだけ意味深な操作を提示していたら、なにかしら操作に関する考察を要求しがちなので、こういうのはそうそう出ないイメージ。

algorithm/Others/acl.cpp at master · drken1215/algorithm

Oct 27, 2025

ABC の過去問を埋める作業をしているけども、D 問題で手こずるケースも結構あって、「あぁ本当に弱くなったなぁ」と「でもこのタイプの問題は別に昔もスムーズに書けたわけではないから、現代の典型について行けてないだけかも」とを実感している。基礎から鍛え直さないと

あまりにも最悪だけど、このリンク先のやつ貼れば、ACL の環境構築をしなくても、ACL にあるものをすべて使える状態になります！！！

赤コーダーでも、(社会人に限定して) 平均年収 800 万くらいじゃないかな。

Nov 17, 2025

ACL と NoviSteps グレード・modint：3Q から・DSU：3Q から・Fenwick Tree：1Q から・セグ木：1Q から・遅延評価セグ木：1D から・Floor Sum：2D から・強連結成分分解：1D から・2-SAT：2D から・最大フロー：1D から・最小費用流：2D から・畳み込み：2D から・Suffix Array：1D から

かつては「けんちょんが Qiita で書いた記事はすべてバズる」とかよく言われていたけど、あんまりそういうの意識するの良くないから、気楽に書くよーーー会社の仕事の一環で書く、くらいの気楽さで書く。

Dec 14, 2020

競プロ、今後の目標を ARC 全完に定めることにした。