JOI 2025/2026 ファイナルステージ(春合宿)に参加しました【15位！】
はじめに
michirakara です。4年目のJOI、高2、最初で最後の春合宿に行ってきました。合宿と言っても宿泊費は会場の最寄り駅まで1時間半以上かかる人にしか出ないので、最寄り駅まで1時間25分かかる私は毎日5時起き6時半出発で必死に会場まで向かっています。
Day 0
交流会をやりました。知り合いがほぼいなかったのでとくになにもありませんでした！！！！かなしい！！！！！！！！！！！！！茨城県の謎競プロ事業でお世話になっているけんちょんさんに挨拶をしました。 その後は春出場者だけ残ってプラクティスをやりました。キーボードがJISなのを失念していたのでUS配列に変更する方法などを確認して準備しました。 帰りに同校の他2人(黄色x2)に Union Find と Segment Tree くらいは書けないとまずいんじゃないかと言われ帰ってから実装を覚えました。Segment Tree はチューターの tatyam さんの2羃にしなくていいシンプルセグ木！
Day 1 52 点 19 位
予選ほぼボーダーで通ったので元より最下位回避くらいで楽しむつもりでしたがさすがに結構緊張します。
お菓子を集めたら競技が開始しました。
伝説の団子食通 (Legendary Dango Eater) 29 点
問題文を読んでまず「甘い団子のスコアを +1 、辛い団子のスコアを -1 としたときに食べた団子のスコアの合計を負にする意味はない」ということに気づけたのでシミュレーションすれば通る 小課題1(6点) を通しました。
一旦別の問題をやってから戻ってきて小課題 2, 3 を考えます。$K\leq 2$ と $K\leq 10$ はまとめていけそうだなあ($O(K(N+Q))$とかで)と考えて DP を思いつきます。$\mathrm{dp}[i][j]$ = さっきの「スコア」$j$ の状態で$i$ 個目から最後まで食べたときのビ太郎が喜ぶ回数 としていったん DP を書きました。
が、よく考えたら累積和的に引き算するときにビ太郎が食べ終わったときのスコアがわからないことに気づきます。仕方がないのでそれはダブリングで全部前計算すると 小課題2,3(5+18点) が通ります。
ここまでで時間切れでしたが奇跡的に満点解法もダブリングだったらしい…(全然使い道は違う(答えを直接特定する方にダブリングを使う))
庭園 3 (Garden 3) 3 点
一旦自明な 小課題1(3点) を通しましたが小課題2がどう見ても遅延セグ木の二分探索なので挑戦します。
ですがDay0に練習したのは普通のセグ木だけ…おぼろげな記憶で 2 時間くらいかけて必死に書きますが残念ながら通らず。
これは終了後に hirayuu_At さんに教えてもらったのですが普通のセグ木でも $(和, 和の最大値)$ を載せれば解けたらしいです…こんな感じ 
マルチコミュニケーション 2 (Multi Communication 2) 15 点
JOI春の醍醐味のコミュニケーション問題です。まずはグラフをそのまま送れば解ける 小課題1(5点) を通します。
小課題2を考えてみますが全然わからず一旦次の小課題を読むとどうやら $N=64$ のグラフを 80 ラウンドくらいで解ければよさそうです。これはプリム法を1ステップに1頂点ずつ増やしていって、まだ木に含まれていない頂点はコストのここまでの和を送らせればよさそうなので実装すると 小課題3(15点) を通すことができました。
なんとこの問題の点数だけで言えば全体の同率3位らしいです。満点の想定解が天才すぎて横転。
ここまでで Day 1 が終了。29+3+15=52 点で 19 位でした。JOI、厳しい…あとは遅延セグ木を書けるように家に帰ってから練習しました。
Day 2 66点 22位
Day 1は眠くはなりませんでしたがそういえば眠気に炭酸水が効くと聞いたことがあったなあと思い出したので炭酸水を買ってから会場入りしました。
カジノ (Casino) 60 点
やったああああああ！！！！！コミュニケーションだ！！！！！！！！と思ってとりあえず問題文を読むと 2x2 のマス目全部が塗り変えられることは無いのでスタート地点がわかればパターン分けでそのまま Chiaro の経路が全てわかりそうだとなったので実装して 16 文字以下、 32点 を得ます。
よく考えてみれば同じことが隣合わせの2マスでもできます(2マス全て塗り変わることはありますが、左下の2マスが片方だけ塗り変わっているかどうかで区別できる)。実装すると無事に 32 文字以下で 60点 を取ることができました。ただこの問題は今回の春合宿で一番簡単だったらしく 2/3 くらいの人が 60 点以上を取っていたので微妙です。
ここからは1マスで1つ情報を伝える必要がありますが全くわからずギブアップ。想定解は checksum を使う方法でした 確かに…
JOI ツアー 2 (JOI Tour 2) 3 点
これ、一見めちゃくちゃ解けそうに見えたんですが不可能枠の問題だったらしく、小課題1(3点)だけ取ってグラフがパスの場合をうんうん考えていた時間は無駄だったようです。なんと最高点も 24 点という虐殺っぷり。
テレポーター2 (Teleporter 2) 3 点
なんか解けそうだなーDPっぽいなーと思いはしましたがいったん 小課題2(3点) を取ります。何故かここから全くなにも思い付かず時間切れ…よく考えたら区間スケジューリング問題なことに全く気付けず悲しい…
Day 2 も終わりましたがこの日はかなりボロボロな結果になりました。Teleporter の言い換えに気づけなかったのが敗因です…Day 2、総合共に 22 位に落ちてしまいました。果たしてここから挽回できるのか！？(タイトルに書いてある)
Day 3 76点 同率9位
問題文が入った封筒が前日よりも明らかに薄いです。全問batch…と思って封筒を開けるとやはりbatchが 3 問ありました。コミュニケーションよりも実力が出やすいので不安でしたがいかに。
三角形降雨 (Triangular Rainfall) 41 点
これは！！結構得意そうな重実装の問題です。数弱すぎて小課題1はわかりませんでしたがとりあえず imos 法で簡単な 小課題2,3(5+5点) が通ります。
次は小課題4を見てみるものの多分これは小課題1の延長だなと思い早々に諦めます。
小課題5,6はどうでしょうか。$X_i=0$ という制約です。正三角形の下の辺が常に同じ高さにあるので、正三角形を直角三角形にして考えると、これは「傾きが同じ一次関数がたくさんあるのでそれに覆われた面積を求めてね」という問題になります。これはがんばれば実装できるのでがんばって実装すると 小課題5,6(10+10点) を通すことができました。
何故か小課題1,4をすっとばして小課題7~9を考えてみますが、小課題5,6でしていたことを 1ステップとして平面走査をすれば解けそうですね。
とりあえず実装してみましたが計算量的にちょっと高速化は必要そうなので一旦お祈りで提出してみます。すると取り零していた 小課題1,4(4+7点) も取ることができました。
こんなに頑張っても 41 点しかもらえないの厳しいな…とか思って嘆いていましたが終わってみればなんと私がこの問題の単独最高得点だったらしいです めちゃくちゃうれしい！
かかし 2 (Scarecrows 2) 4 点
今日のダメすぎ枠はこちらです。一旦自明な二分探索をして 小課題1(4点) を取りましたがここから何も思いつくことができず終了。これも終わってから考えれば括弧列以外の何物でもありません。どうして考えられなかったのか…
スタンプラリー 5 (Collecting Stamps 5) 31 点
まず $N\leq 3000$ の 小課題2,3(7+10点) は普通にDFSをすれば通すことができます(なんか 小課題1(3点) も通った)。
そして 小課題4(11点) も左右からの到達時間を引いたスタンプの設置時間を持っておいてセグ木を書けば通すことができました。ここまでで 31 点…Triangular Rainfall の部分点と重み違いすぎない…？
Day 3 も終わってしまいました。今日は Triangular Rainfall で最高点を取ることができたのもありなんと Day 3 だけで見ると 9 位、総合は 19 位まで戻ってくることができました。しかも総合 11 位からの差が 30 点とかなり点差が詰まっています。これは最下位回避どころか真ん中より上(15位)もあるんじゃないか…？と思い始めてきました。果たして最終日の結果やいかに！？
ところで Day 2 の Teleporter、Day 3 の Scarecrows 2 がどちらも Monge を使って解けるという噂を聞きさすがに勉強しとくか…？と思い帰りの電車の中で tatyam さんのスライドで Monge、monotone minima、LARSCH などを習得しました(伏線)。
Day 4 73点 12位
ついに最終日です。15位以上を目標として頑張ります！
パン職人 (Baker) 50点
とりあえず問題文を読むと制限時間が後の人から順番に配っていくのが最適だとわかるのでそれで 小課題1,2(8+12点) を通します。
別の問題をやって帰ってきました。小課題3ですが、ごちゃごちゃ図を書いて考えると「単調増加のグラフでのある傾きの接線の接点を求める」問題に帰着することができました。これは今考えると CHT でしかないのですが、$A_{i,j}=T_i+L-ij$ の表を書いて考えていたので何故かこの表が Monge であることに気づきました。嘘だろと思いながら他の表も書いてみますがどうやら本当に Monge であるようです。となればこれは monotone minima そのものなので書いてみると通ってしまいました。 小課題3(30点) を通すことができてしまいました…
↑たしかによく考えてみたらそれはそうだ…
JOI 国のお祭り事情 3 (Festivals in JOI Kingdom 3) 13点
シミュレーションの 小課題1(6点) を通して、小課題2を見るとなんと $k$ 番目の値を取得できる set が必要な問題です。いやいやいやいやまさか…と思いますがどう見てもそうです。解き方は分かっているので思い出した座圧してセグ木でカウントして二分探索するやつで実装して通すことができました。 小課題2(7点)
電圧 2 (Voltage 2) 10点
この問題は得意なコミュニケーションだったものの何もわからず…小課題1(10点) だけ通しました。後から考えると確かに二分探索だ…
全日程が終わって総合では 15位 でした。最初で最後の春合宿として悔いがないわけではありませんが想像以上に戦えて満足しています。楽しかったので来年も出たい…え、ダメ？ダメなんですね…
次回予告
全問 upsolve してみた(いつまでにやるとは言わない)
JOI 2025/2026 セミファイナルステージ(2月1日(日))に参加しました(コードゴルフもあるよ)
予想：23点
- まずはこの画像を見てください。
これでファイナル狙うのはいくらなんでも舐めすぎなので高2の最後に半分引退試合のつもりで行くことにしました。
中1のときに AtCoder を始め、中2で初めて JOI に出てそこから努力はしてきたつもりでしたが毎年本選(セミファイナル)敗退でした。
まさかね〜〜〜〜〜さすがにどう見てもこの人落ちるでしょ〜〜〜〜〜〜〜wwwwwww
開始前
茨城県のド田舎高校なので東京まで結構かかるので、早めに家を出て東京で昼を食べることにしました。
一蘭食べて満腹になって眠くなりそうだったのでコーヒーとガムを買います。 11 時過ぎくらいに会場入り。始まるまで $n$ ヶ月ぶりの競プロをしてウォーミングアップ&環境の確認をします。前日にあった ABC443 のD問題を解こうとするが、普通に解けなくて焦ります。これは終わったか…？
E問題は無事に解けたので一安心して(D解けなかったのは本当にマズいが)いると結構すぐに開始時間になってしまいました。全然対策していなかったのに結構緊張してきます。手汗ドバーで焦っていたら最初で最後の "JOI セミファイナルステージ" が始まってしまいました。
開始
とりあえずA問題を見ると左から $n$ ペア、右から $m$ ペアを配置すればよさそうなので右から順番に $1,3,5, \dots, 2n+1$ を順番に見て行って左からの累積 max を取ったら AC。(A 100点 0:07:14)
B問題がぱっと見解けなくて焦るが一旦部分点 2, 3, 4 は取れそうなので解いてみる。イベントソートして時間 1 ごとに更新したら通る(B 61点 0:26:54)
よく考えたら客を累積和にすれば↑の更新が $O(1)$ でできるので直して提出(B 100点 0:40:14)
C問題を見るが全くわからない。一旦小課題 1, 2 を場合分けでむりやり通す(C 20点 1:05:48)
順当に小課題 3 を見て考えると最大でも $\log_2 (23-\rm{max}(A))$ で通ることがわかるので一旦通す(C 35点 1:18:06)
小課題 3 ありがとう…全探索で通ることに気づいて実装しようとするが結構手間取って時間がかかる(C 100点 2:32:49)
ここで一安心して一息ついてゼリーを食べて気分転換。Dも見に行ってみる。小課題3が虚無だったので通す(D 7点 2:48:19)。よく見たら小課題4も虚無ですね(D 18点 2:52:47)。
E,Fも見てみたが全くわからずここからかなり行き詰まる。結構無理そうなので D の小課題 1 を筋肉全探索で通す(D 31点 3:56:12)←これ奇跡すぎる。
結果
331 点、 暫定ボーダー324点ギリギリ通過です(普通にボーダー370くらいだと思っててびっくりした)
おまけ(本題)：AとBのコードゴルフをしよう
A問題(64byte)
まずはやることを疑似コードにしてみます
n, a = 入力を受け取る
l = 左から奇数番目の要素の累積max
出力(max(
for i in 0..n:
a[i*2]+l[i]
))
とりあえずPythonで書いてみました。(125byte)
Submission #72953663 - JOI 2025/2026 セミファイナルステージ 過去問
from itertools import* n,*a=map(int,open(0).read().split()) print(max(sum(i)for i in zip(accumulate(a[::-2],max),a[~1::-2])))
itertools.accumulate() と入力がちょっと長いのがよくないので変えてみましょう 。
→ awk を使えばいいですね(？？？？？)
awkは入力がデフォルトで変数に入っている($1, $2, $3, .... と単語ごとになってる)のでこんな感じで書くことができます。(64byte)
Submission #72995210 - JOI 2025/2026 セミファイナルステージ 過去問
{for(i=NF;i>1;i-=2){m=m>$i?m:$i;a=a>m+$(i-1)?a:m+$(i-1)}print a}
できました。
ちなみに現時点での shortest は Uiua(初耳) の 37byteでした。
Submission #72955309 - JOI 2025/2026 セミファイナルステージ 過去問
B問題(191byte)
解法はいろいろありますが、短く書くには累積和を取るのがよさそうです。
とりあえず Python である程度短く書いてみます。 (191byte)
Submission #72995700 - JOI 2025/2026 セミファイナルステージ 過去問
t=8**7;a=[0]*t;b=[0]*t;(n,*_),*o=[map(int,i.split())for i in open(0)] for l,r,c in o[:n]:a[l]+=c;b[r]+=c for i in range(t-1):a[i+1]+=a[i];b[i+1]+=b[i] for s,t in o[n+1:]:print(a[t]-b[s-1])
shortest取れちゃった… まあこれでよしとします。
おわり
ファイナルマジでがんばります
PythonでPythonを実装する
exec(input())
日本に三年ぶりに行った
日本に三年ぶりに7/5~7/22にかけて行っていたのでやったことなどを書きます
7/6~7/9 東京
これはサンフランシスコ国際空港です
飛行機に乗るぞ〜〜！！！の前にラウンジでコーヒーではなくコーラを飲んで休みます（ガキ）
飛行機に乗りました
カメラがついてるんですね 面白い
離陸〜〜〜！！
機内食〜〜〜！！
飛行機の中で見た映画の感想（小学生並）
- ゴジラ-1 白黒映画が新鮮でよかった。カラーの映画より想像が膨らむのでむしろこっちのほうが好きかもしれない。 ストーリーも面白かった。
- すずめの戸締まり 絵がきれい（とても）
- Dumb Money こういうジャンルの映画はあまり見ないが、これはこれでありだなと思った。どきどきしたのでよかった
着陸〜〜〜！！
（ここまでで9時間くらいかかっています）
Welcome to JAPANがありました
この日は特に何もせずに人形町付近のホテルに行きました 晩ごはん何食べたんだっけ
7/7
今日はいろいろまわるぞ〜〜〜と意気込んでまずは渋谷に来ました
ハチ公を発見
スクランブル交差点を発見
実はここ、あの大人気ソシャゲブルーアーカイブにも登場します
ここにもブルーアーカイブの聖地が
渋谷も適当に散歩したので新宿に行きます
あれ、山手線で来たのに駅で迷子になって出てきたら京王の駅から出てきた...
ヨドバシカメラの本店を発見 ウインドウショッピングをしてきます
生ゴミが肥料になる機械とか４つしかキーがないキーボードとかいろいろありました あとトラックボールのマウスがほしいです
東京都庁を発見
ブックオフに寄って本をゲット いい本は中古でも高いんですね〜〜
新宿駅を出発して秋葉原に行きます
つきました ブルーーーーーアーカイブ！！！
ブルアカグッズをゲット
秋葉原ですね〜〜〜〜 アトレでアイマスグッズを見ていました
ここであちゃぴと合流(Twitter: achapi_kyopuro) プロフの写真撮るのを忘れてました
ラーメンを食べます うめーーーー
完食
アニメイトでブルアカグッズを買いました 怖
人生初AC音ゲーです 難しすぎないか
ここからしばらく音ゲーをして解散 楽しかったです あと財布をゲーセンに忘れかけて焦りました
夜宇沢アイスを入手 おいしい
7/8
次の日は用事があったのでそこまでいろいろしていません 家族と行動しました
昼に天ぷらを食す うめーーーー
これは文房具屋にあった200色どころじゃない白
これは夕食のもんじゃ どんなもんｊ（（（（
7/9
飛行機で大阪に行きます
隣に修学旅行帰りの女子高生が乗っていて、Linux の本を読んでいたらすごいねって言われました
7/9~7/14 大阪
ＳｋｙってあのＳｋｙですか ABCやってたあのＳｋｙ
空港で担々麺を食べる おいしかったです 写真が下手
7/10
7/9と7/10は親戚の家を回っていたので写真がほぼありません
7/10の昼のそばの写真 十割そばでした 美味しかった
夜はしゃぶしゃぶに行きました（写真無い）
7/11
妹が散髪に行っている間に一人でカラオケに来ました
1000年生きてるなどを歌いました これ人間が歌う曲じゃないな
ここから日本橋に地下鉄でワープ 昼食は地下街の適当な店でちゃんぽん麺を食べました
なんばグランド花月を発見 吉本新喜劇じゃぁないですか
でここから道具屋筋を通ってオタクロード方面に向かいます
途中で食品サンプルの店とか居酒屋の入口にぶら下がってるような提灯屋があったりして面白かったです
オタクロード手前で家族と解散してオタク活動をしに行きます
アニメイト、らしんばん、メロンブックスが入っているビルを発見 一周ウインドウショッピングを楽しみました
道を歩いていたら声を掛けられ、ナンパ！？！？とワクワクしながら会話をしていたらメイドカフェ興味ある？と聞かれ、ド鬱に...
デジットを発見 電子部品系のお店です
白黒の液晶とか7セグディスプレイとか色々おもしろいものが売られていました
UFOキャッチャーアーム！？
￥1000の文字につられ危うく購入するところでしたが物欲キャンセルに成功
物欲キャンセルキャンセル対策で上の階に逃げます
しかし上の階にはさらなる試練が待ち受けていました
なんとラズパイ+ACアダプタが合わせて￥3000！？ぐわあああああああああ購入！！！！！！
7/12 伊根へ日帰り旅行に行こう！
この日は一人で遠出をします バカ遠い京都府伊根町まで行きます
どのくらい遠いかというと このくらい遠いです
なおかつ夜までには大阪に帰ってこなくてはいけないのでがんばります
今回のルートはこんな感じです
早速出発です
5:30くらいに宿を出て石橋阪大前駅から阪急電車に乗ります
うおーーがんばるぞーーーーー！！！！
、と意気込んだのは良いのですが2駅目で降ります 川西能勢口です
少しペデストリアンデッキを歩くとJRの川西池田駅に着きます
6:16発の普通福知山行の宝塚線に乗って8:19に福知山につくまで電車に揺られます
電車はボックスシートだったのでくつろいでゆっくりTCP/IPの本を読んでいました
のーどか〜
谷川駅で加古川線を発見
ところでずっと雲行きが怪しいです 果たしてどうなるのか！？
福知山駅に着きました 写真取ってねえ...()
乗り換えまで36分あるので少しゆっくりできそうです
改札を出てすぐの場所にあるセブンイレブンがあったので朝食を購入
実はここからの京都丹後鉄道宮福線は特急に乗っちゃいます
ということでラーメンの食券機みたいな券売機で特急券も購入！これが人生初特急です 楽しみ〜〜
思ったより安いですね 700円でした
それから用を足してホームに向かうともう特急列車が到着していました
かっこいい！KTR8000形というタイプの車両らしいです
ちなみに二両編成でした 特急にしては短い？気がしますね ローカル線はこんなもんなんでしょうか
わくわくしながら入口に足を踏み入れます
うおおおおおおおおーーー！！！！！ かっこいいーーー！！！！！
おっしゃれーーー！！！！！！！
あまりにもおしゃれすぎないですか？まだ発車まで時間に余裕があったのでちょっと中を見て外で待っているつもりでしたが、あまりにもおしゃれすぎたので出発までは隣に止まっていた普通列車に乗る乗客に「俺は特急乗るんだぞいいだろ〜」とアピールしながらドヤ顔で外を見ながら座っていることにしました
そうこうしているうちに電車が駅を出たのでセブンで買った朝ごはんを食べます
うっめーーーーーーー！！！！！景色を眺めながら食べるおにぎりは最高ですね
ついでに特急券も食べます
というのは嘘で車内改札に車掌さんがきました
これ乗車券と特急券を両方買ったのは、京都丹後鉄道ではICカードが使えないからです 乗る人は気をつけてください
駅員さんに聞くまで知らなくてヒヤッとしました 多めに現金を持っていてよかったです
やっぱり特急は速いですね 車窓を眺めているうちにあっという間に30分くらいで宮津駅までついてしまいました
名残惜しいですが今回の目的は特急ではなく伊根町なので気を取り直して頑張っていきます
ここからは路線バスです 駅前のロータリーでバスを待ちます
少し時間があったので駅前の通りを歩いていたのですが美味しそうな喫茶店がありました
もう少し時間があったら行ってみたかったです
と、バスがやってきました
ガラガラです 私以外には地域住民らしきおばあさんが一人二人乗っていただけでした
朝早いとはいえこんなに空いてるのかと不思議でしたが、しばらくすると天橋立付近でたくさん人が乗ってきました
まあそれはそう
ところでバスの停留所にゲートボール場前とかいう年寄り感がすごい場所があって面白かったです
ついに海が見えました すっげー曇ってるが。
あれはかの有名な伊根の舟屋！？もうそろそろ到着です
8割くらいの乗客は伊根で降りていきましたが私は一つ奥の道の駅船屋の里伊根まで乗ってから降ります これには理由があります
ちなみにバスの運賃は400円が天井らしく天橋立くらいからはどこで降りても一緒の運賃でした 良心的！
運賃を払ってバスを降りました 時刻はちょうど11時を回ったころです
停留所から海見えないんかーい
このあたりです
まあこれはこれでいい景色なのでOKです バス停から無駄に200mくらいある縦に長い駐車場を通って道の駅に行きます
道の駅なのに何も見ずにまっすぐ二階に上がっていきます 一体お土産も買わずに何をする気なんだ...
...
...
...
海鮮丼だ〜〜〜〜〜〜〜〜〜〜〜〜〜！！！！！！！！！！！！！！！！！！！！！！！！！！！
いただきま〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜す！！！！！！！！！！！！！！！！！！
うっめ〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜！！！！！！！！！！！！！！！！！！！！！！！！！！！
ごちそうさまでした〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜！！！！！！！！！！！！！！！！！！
いい景色だ。※急に落ち着くな
海鮮丼めちゃくちゃおいしかったのでもし伊根に来ることがあれば食べてみてください
腹ごしらえもしたところでここから観光していきます
道の駅は高台にあるので海の高さまで行くことのできる小さな階段を通って下まで降りていきます
この階段本当に小さいので見逃さないように気をつけてください
ワクワク ついに海か〜〜ってなんだあの青緑
なーんだ空の色か〜空にしてはずいぶんきれいな色でｓ...！！？！？！？！？！？！？！？海だ〜〜〜〜〜〜〜〜〜！！！！！！！！！！！！！！！！！！！！！！！きれい〜〜〜〜〜〜〜〜〜〜〜〜〜〜！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
海だ海だ海だ〜〜〜〜〜〜〜〜〜〜〜！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
きれいだ。※急に落ち着くな
すごい、きれいな海ってこんな色だったんですね 曇りでここまできれいなら晴れていたらそのままダイブしてウニを取って食べてたかもしれません 曇っててよかった〜
ここから海沿いを観光しようと思います
ですが、伊根は小さな町で観光するのはほぼ海沿いの一本道とはいえ端から端までは3kmほどもあるので流石に歩くのは大変です
もしこんなときに自転車に乗れたらな〜〜〜乗れたらな〜〜〜〜
乗れます。しかもタダで。
伊根町の観光案内所で無料で（保証料として2000円預ける）自転車を借りることができるのです 神 ありがとうございます
早速観光案内所に急ぎましょう 時間は待ってくれません
必殺オタクダッシュ
※この写真撮る暇あるってことは別に急いでないだろって そのとおりです
着きました 自転車を借りたいと言ったら今大人用のが無くて子供用のならあるんですが...と言われました
仕方ないから子供用の自転車を借りようと思ったらちょうどよく大人用の自転車が帰ってきました
よかった... もう少しで子供用自転車に背中を丸めて乗る異常オタクになるところでした
自転車をゲット(ゲットではなく、レントでは？)
まず向かったのはここです
到着〜〜
なんとこの伊根町、あの！大人気ソシャゲブルーアーカイブのイベント「夏の特殊作戦！RABBIT小隊と消えたエビの謎」の舞台なのです！！！！！！！！！
「ここ」がブルアカなんだな〜と感心しました（小学生並の感想）
ちなみに流石に他には金曜にここまで来るほどの熱心なオタクはいませんでした ちょっと残念
せっかく伊根の端の方まで来たので一番端まで行ってみようと思います
あれ、ゆっくり自転車を漕いでいるといつの間にかほんのすこしだけ青空が！ 運が良いですね 日頃の行いが出ています
端まで来ました
カンジャガハナ灯台という危ないクスリみたいな名前の小さな灯台がありました これが†エモ†...
雲の隙間から見える青、また違う海の青、山の緑が灯台の鮮やかな赤に映えています
満足したので反対側に進んでいきましょう
これは家と家の間に海の水が入ってきていてなんかこうめっちゃいい感じなやつ
これはヒトデ ヒトデがいるの！？
これはかわいい苔 かわいい〜〜〜
これは道の駅にもう一度寄って家族＆親戚に無難そうなお土産を買う図
うーん、自転車を漕いだり階段を登ったり降りたりして疲れてきました
こんなときにおいしいアイスを海を見ながらウッドデッキで座って食べられるステキなカフェがあればなぁ...
あります
INE CAFEです
ここです
アイスを買いました
インスタ映えするジャーン インスタやってないけど
せっかくなので味は伊根産そばにしてみました
食べてみます なんかもっと変なのを想像してたらめちゃくちゃおいしかったです オヌヌメ！
うおーーー！きれいすぎる！！！！！
野生のカキとウニ！？！？！？！？！？！？！？！？！？！？！？！？
海にさわれそうでした 足濡れたらいやだからさわらなかったけど
エモエモで草
これ今回のベストショット説があります
おいしかった〜まだまだ観光するぞ...と言いたいところですがなんと滞在時間2時間半の超過密スケジュールを組んでいるのでそろそろバス停に向かって歩いていかないといけません
西に向かってゆっくり歩いていきます
港を発見したのでちょっと降りてみました
おお、水がきれい
道路はこんな感じの一本道がずっと続いています 昔ながらな感じでいいですね
左（海側）の家と家の間から海が毎回見えてめちゃくちゃきれいでした
お、地域の売店っぽいところでTシャツを発見 私の衣服はほぼお土産で構成されているため補充しようと思います
買ったTシャツがこちら
「いイネ！👍️」です サムズアップの拳から覗く魚がキュートでとてもいイネ！ （？）
そうこうしていたら帰りのバス停に着きました
帰りは平田から帰ります
うわーーーん さらば伊根〜〜〜〜〜楽しかった〜〜〜〜！！！！！！！！
バスで宮津まで帰ってきました...
ですが電車までかなり時間があるので海辺の公園まで行ってみようと思います
もしかしたら天橋立が見えるかもしれません
見えた〜〜〜〜！！見えたけど！！！微妙すぎる...
側溝でカニを発見しました かわいい
よくわからん絶妙に美味くも不味くもないジュースを自販機で購入 100円だったので後悔はしてないです
帰りは福知山まで普通電車で帰ります 普通電車も結構かっこいい
中もボックスシートで快適でした
運賃箱とかモニター（テレビくっつけただけみたいなやつ）とかがローカル線っぽくてよかったです
行きの二倍くらいの54分をかけて福知山に到着 実はここから特急に乗ります！！！！行きに宝塚線に乗ったルートを特急こうのとりで一瞬で帰ります
しかしまだ時間があるのでセブンイレブンでアイス２つとぼざろのクリアファイルをゲット ぼざろ見たこと無いけど
ところで本当にこういうのって商売が上手いですよね 普段買わないけどギリギリ食べ切れるラインの物を買わせてくる
アイス２つとか
特急に乗りました
顔の写真取ってないな アイスを食べます
うめーーーーー ぼざろの味！！（そんなものはない）
冷たいアイスが疲れてきた体に染み渡ります
お気づきの方もいるかもしれませんが実は今日伊根でもアイスを食べています
なのでアイス3個目 厳しいって
こうのとりの英語の車内アナウンスがイギリス英語でびっくりしました
こういうのって大体アメリカ英語じゃない？
まじで一瞬で宝塚に着きました 1時間10分くらいしかかかっていません
行きは2時間かかっているのに...さすが特急速いですね
あとは特に何事もなく阪急で宿に18:30ごろに到着 長かった一日もこれでおしまいです
完走した感想ですが、もう少し時間に余裕を持って行動すべきですね
伊根がいい場所すぎたので一泊して帰りたかったです
まあでもレンタルサイクルと町の小ささのおかげで２時間半でも端から端まで探検できたので大満足です
またどこかにこういう限界日帰り旅行をしに行きたいです
限界日帰り伊根一人旅おわり
7/13
次の日です
箕面山に行きました
紅葉（もみじ）ってその字の通り紅葉（こうよう）しているときが一番綺麗なのだと思っていましたが青々としている夏のモミジも同じくらい綺麗ですね
途中昆虫館に寄って蝶を見てきました きれい。
フリスクのジュースを発見したので購入 まずいですねこれ
最初の一口はスースーしていて結構アリなのですが、二口目からだんだんしつこくなってきます
ヤクルトくらいのサイズで売ってるならアリだなと思いました それでもわざわざ買いはしないと思うけど
モミジの天ぷらを発見
甘くてサクサクしていておいしかったです（粉みかん）
道の終わりの滝で柚子味のソフトクリームを食べました
しかしここで事件が起きました
柚子味のソフトクリームを略すとどうなるかわかりますか？
そうです、「ゆずソフト」です 某えっちゲームメーカーと全く同じなのです
それに気づかずうっかり「『ゆずソフト』食べたいな」と口に出してしまい人生が終了しました
と思いきや、ゆずソフトを知っているほど人生が終了しているオタクはハイキングに来ないのでセーフでした（失礼）
夜は旧石器時代の太鼓の達人がおいてある温泉に入ってビュッフェを食べて帰ってきました
↓ビュッフェで作ったおそらく世界一下手なソフトクリーム
7/14~7/19 静岡
7/14
朝から移動を開始します
大阪から静岡なのでもちろん東海道新幹線...では移動しません
せっかくなので一人で東海道本線で移動してみようと思います
家族は東海道新幹線にのってのんびり来るらしいです
大阪駅で京都線新快速に乗って野洲まで行きます
新快速、速いですね 1時間もしない内に琵琶湖の端まで来ました
しかし新快速もここまでで、野洲からは全部普通列車です がんばりましょう
野洲からは米原まで琵琶湖線に乗って行きます これ琵琶湖線は愛称で正式には東海道本線らしいですね 知らなかった
野洲〜米原間は近いので10:44発の電車に乗って11:18に着きました
米原では次の電車まで12分あるので急いでコンビニでおにぎりを買いました
コンビニが改札にめり込んでいて改札内からも改札外からも買い物ができるようになっていて面白かったです
急いでおにぎりを買ってもう到着している次の電車に乗りに行きま...って駅弁売ってる！？！？！？！？！ 気づきませんでした...
駅弁にすればよかったなと思いつつ時間がないので次の大垣行き東海道本線に乗ります
大垣までは34分です その間にクロスシートの車内でおにぎりを食べました
窓の外を見ながら食べるおにぎりは格別です
しかし東海道本線、ここまで来てしまうとどうやっても迷いようがありません
乗り継ぎ駅では必ず隣のホームに次の列車が止まっていてそこにまっすぐ入るだけです
同じように大垣、豊橋、浜松でも乗り換えるとあっという間に静岡駅に着きました
ところで浜松からの列車でトイレに行ったときに水の色が緑色だったのですがあれは何なのでしょうか
調べてみたらどうやら消毒液の色らしいです 小さい方はそのまま消毒して循環させてトイレの水として使っているらしいです
当然トイレの水の中の小さい方の割合がどんどん増えていくので最初は青なのがだんだん緑→黄色と変わっていくらしいです
嫌だな...
乗っていた列車は緑だったのでまだまだ水は変えなくてもいいのかな？
7/15~7/18
静岡の祖父母の家でダラダラしていたので特に書くことが無いです...
生しらすを食べました おいしかったです（小並感）
黒はんぺんを食べました おいしかったです（小並感）
食べ物の写真だけ
丸源のラーメンです おいしかった 安いしいいですね
魚河岸という寿司屋の寿司です めちゃくちゃうまい！！！うますぎ！！！！
7/19~7/22 東京
7/19
朝から移動を開始します
静岡から東京なのでもちろん東海道新幹線...では移動しません
せっかくなので一人で東海道本線で移動してみようと思います（コピペ）
１つ目の列車は熱海まででｓ...！？どうやら熱海東京間の列車が横浜駅で電車の窓が割れた（どういうこと？）影響で遅れているらしいです
はてどうしたものか このまま行っても行けなくはなさそうですが遅れているとなると多分混んでいるんですよね
満員電車に乗るのは楽しくないし到着時間はどうでもいいのでせっかくならと沼津で急遽別の路線に乗り換えることにしました
元の予定が赤ルート、青ルートに変更しました
沼津、ラブライブ!サンシャイン!!の聖地なんですね
かわいい
かわいい
かわいい これ端から端までラブライブのポスターでした
いい感じな写真.png(jpgかも)
で、そうです！沼津からの乗り換えについてです 沼津で乗り換えるのは御殿場線です
イケイケの東海道線から急にド田舎っぽい電車になります（？）
こんな感じの山奥をずっと走り続けます 車窓の景色がずっと綺麗でよかったです こっち乗って良かった
途中で終業式が終わったらしき高校生が大勢乗り込んできました
ホームを眺めていたら他の同級生を見送りに来たらしい高校生と目が合って手を振られたので手を振り返しておきました なんかいい瞬間ランキング優勝
次の乗り換えは松田です こんなところに何があるんだ...
と思って出てみると意外にも栄えている駅前でした 乗り換えるのは横断歩道を渡ったところにある小田急です
この写真なんか良くないですか 晴れてて。
新宿行きの急行だったか快速急行だったかに乗り換えました
速いですね 一瞬で新宿に到着
ところで途中下北沢を通ったのですが下北沢ってぼざろの聖地だということ以外特に何も無いですよね <おっそうだな(適当)
このとき時間はもう13:30です
流石にお腹が空いてきたのでご飯を食べに行きましょう
コメダコーヒーを発見したので入ってみます コメダコーヒー実は初めてです
新宿中央通りを見下ろせる席に案内されました
カツカリーサンドを頼みました 1000円ほどしたのでなんだか高いなぁ物価高かなぁと思っていたのですが
クソでかいカツカリーサンドが届いてビビり散らかしました そりゃ1000円するわけだ
あと謎の豆のお菓子美味しかったです
完食
おいしかったです また食べに行きたい
腹が膨れたので散歩をしましょう
Apple Storeを発見
Vision Proが売られていました ほしい〜〜〜〜〜
次に来たのは紀伊國屋ビルディング 紀伊國屋の本店です
でかい書店に来ると気分が上がりますね
ゼロからのOS自作入門とRustで作るプログラミング言語を買いました
次にやってきたのは浜松町 なぜなら近くに宿があるからです
周辺を探索してみます
芝大門と東京タワーを発見 近そうなので東京タワーまで歩いていってみます
てくてく 途中でルフトハンザのビルを発見 以前ドイツ乗り継ぎでフランスまで行ったときに乗りました
到着しました
で、でけーーーー さすが東京タワーです
333mはでかいですね 私の195倍の高さです
なんかぼっちざろっくやってました
お土産を見て涼んだので芝公園を歩いてみようと思います
伊能忠敬の石碑を発見 隣でカップルがイチャイチャしていて気まずい感じになりました
私は気づいていないふりをしてその場を去りました ざまあみろ
古墳を発見
その後芝大神宮にお参りしてきました
よるはやきにく（煩悩カンストの枕草子）
大本山増上寺で盆踊りやってました 地蔵盆とかいうやつらしいです
寺 盆踊り 東京タワー いかにも日本でいい感じですね
踊ってきました 一体何年ぶりかわかりませんが楽しかったです
7/20
今日は東京をぐるぐるする日です
土曜朝9時、人の少なさレベル×景色の良さレベルが一週間の中で最大になる時間帯にやってきたのは東京駅です
後ろでビルの工事をしていますね 何を建てているんだろうと思って調べてみたのですが八重洲エリアの再開発が行われているらしいです
多分Torch Towerという名前のビルだと思います
ところで今日の服見てください 推しのTシャツです おそらく日本で一番推されているキャラだと思います
私は別に大丈夫ですが同担拒否の人大変でしょうね〜 あっそういう人が脱税すｒ（
次に来たのは東京駅のすぐ隣りにある丸善の本店です コンピュータハイジャッキングを入手 やったね
これはカメラの画角に収まりきらないくらい高いビルを眺めてたまげている図
お、皇居じゃん どこもかしこも工事やってるな 今日はそういう日なの？
皇居の堀の外を半時計回りに60°くらい歩いたところ（わかりにくすぎる例え）で曲がって神田神保町方面に向かいます
集英社を発見 こんなところにあるのか
目印は隣りにある怪しい宗教団体のビルです
古書店が立ち並ぶ通りを発見 何も知らない古い本を買ってみました
３年分のお年玉を親戚という親戚からもらった今の私は最強なので何でも買えます
この本昭和28年の本らしいです すげーー おれの4倍以上生きてる
時間はそろそろ11時です 東京駅から神田まで歩いてきたのもあってお腹が空いてきました
神保町ブックセンターというカフェ＆書店に入ってみます おしゃれすぎる
おしゃれすぎるのでコンビーフサンドイッチを頼みました（コンビーフサンドイッチはおしゃれなのか？）
優雅にコーヒーとランチと本を楽しみます うおーーーーーー楽しいーーーーーー！！！
楽しかったので次は秋葉原に向かって歩いていきます
見つけたのは三省堂書店の本店 中を見てきます
今年の本屋大賞だったらしい成瀬は天下を取りに行くを購入 ハッピー
途中でファミマに寄ってポッキーを二箱買って雀魂のトリプルロンクリアファイルをゲットしました
そうこうしているうちに秋葉原に到着
この辺からの景色、ジ・秋葉原（正しい発音）という感じで良いですね
ブルーアーカイブじゃん 終了したイベントの広告ってしばらくそのままなの？
次は御茶ノ水に向かいます あの有名な聖橋（ひじりばし と読むらしい）にやってきました
電車がたくさんいました 有名なんだなあとおもいました（小学生）
東京メトロ丸ノ内線？が二両同時に通っていた図
中央線？が奥から来た図
ところでここ写真左側の道から来ると階段を登らないと橋を渡ることができないので気をつけてください
暑くてひからびました 暑くてひからびるといえば！ 実はここブルーアーカイブの聖地です
奥の方を反転するとぴったり！
あとすずめの戸締まりの聖地でもありますね まあ有名なので他の作品でも結構登場していそうではあります
ところで流石に暑すぎます 聖橋、遮るものが周りに何もなさすぎるのであまりにも暑いです これはやばいので電車に乗って逃げようと思います
中央線で新宿まで行って最強（埼京）線に乗り換えてやってきたのは池袋です 埼京線、新宿出たら次は池袋なんですね 便利
そしてここはジュンク堂本店です
買ったのははらぺこあおむしのエコバッグ（！？！？）
朝一に丸善でもらったレジ袋に荷物が収まりきらなくなってきていて、ちょうどよく親が好きそうなエコバッグがあったので買いました
あとで親にあげたのですがスマホを入れるポケットがある！サイズがちょうどいい！と大好評でした
夜はいかめし（食いしん坊の枕草子）
7/21
今日はつくばに行って学校の競プロerに会ってきます
朝9時につくば駅前集合とアホすぎる約束をしてしまったので朝7:30に宿を出ました
ブルーアーカイブのキャラクターたちは日曜の朝8時前だというのに元気に広告をしていました かわいそう かわいい
つくばに約束通りについて無事合流...のはずが一人寝てたのでとりあえず三人でボウリングに行きます
@nouka28 (←黄コーダー！ すごい！)と@rotti_coderで boring の対極の ボウリング で遊びます！！！！！！！ギャハハハハハハハハハ！！！！！！
ん、ダブルスコア 心安らかなり
(最終的にちょっと追い上げた いや、追い上げてないな、点が離されるペースが遅くなっただけ)
3ゲーム遊んで満足したので丸亀に行きます ここでもうひとりも合流 うどんうまい
次はカラオケです †娯楽†すぎる
今回の最高得点はみちらから歌唱茨城県民の歌92.362点でした え
楽しかったので次はゲームセンターに行きます（！？） 音ゲーをたくさんやる回
疲れたので晩ごはんを食べに行きます
銀だことか海鮮丼とかそれぞれ思い思いの食べ物を食べます
もう午後七時！？ 早すぎる 帰らなくてはなりません
帰ります
最後にブルアカグッズ見て帰ろうと思ったら閉店してました かなしい
7/22
最終日ですがまだまだ遊びます この日は父親以外の家族と行動します（父は仕事があったらしいです）
藤子・F・不二雄ミュージアムに行くことにしました 都営大江戸線〜千代田線（小田急直通）で登戸まで行ってシャトルバスに乗ります
登戸でバスまでに時間があったのでFUGLEN COFFEE ROASTERSというカフェに行きました フルーツのような味のコーヒーがあって美味しかったです
今まで酸味のあるコーヒーは苦手だったのですが美味しいコーヒーだと酸味があるやつでも美味しいんですね これはこれでありという気持ちになりました
中は展示物の撮影が禁止だったので写真を一枚も撮っていません 禁止じゃないところで、撮れよ
まあ楽しかったのでOKです ミニシアターとか原画とか藤子先生が西部劇にハマっていた話とかいろいろあって面白かったです
遅めの昼食は登戸駅の日高屋で食べます 安くね！？安いのにちゃんとおいしかったです今度から定期的に行くようにするか（今度（日本に帰ってから））
帰りはせっかくなので別の路線で帰ってみます 南武線〜横須賀線で帰りました
乗り継ぎの武蔵小杉駅の南武線ホームから横須賀線ホームまでがあまりにも離れすぎていてウケました
多分普通に10分くらいはかかります おかしいって
なんともう帰る時間です 早くないですか？ 悲しい...
空港に到着...
ラウンジでうどんを3杯食べました
飛行機が何故か一時間遅れたのでブルーアーカイブのメンテが終わって遊べるかなと思ったらブルアカもメンテ延長で結局遊べませんでした
さらば日本！！！！！！楽しかった！！！！！！！！！！！！！！！！！！！！！！！
たのしかった！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
うわ————————————！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
楽しかったーーーーーーーーーーーーーーーーーーーーーーー！！！！！！！！！！！！！！！！！
楽しかった
楽しかった
楽しかった！！！！！！！
おわり
13000文字以上あるらしいです 最後まで読んでくれてありがとうございました
入水したのでうれしいなと言う
入水しました
中三水コーダーのみちらからです。前回のARC162で入水したので記事を書きます。
うれしいな
うれしいです。AtCoder始めたときに知ってた強い人（今はやっていない人）が水コーダーだったので驚いています。水コーダーは上級者のボーダーだと感じていたので感慨深いですね。（ちなみに黄コーダーは人外ボーダーです）
やったこと
実は緑コーダーの間に解いた問題数は少ないのですが、高めのdiffの問題を多く解いていたので緑、茶diffは大体一瞬で解法が浮かぶようになりました。精進って大事ですね。
あとC++に移行しました。きっかけはJOI本選です。入緑まではPythonを使ってAtCoderの問題を解いていたのですが、JOI本選ではC++しか使えなかったのでかなり結果はボロボロでした。それが悔しかったので次のABCから急にC++に使用言語を変えました（は？）。今はC問題まではPython、D以降はC++で解くスタイルになっています。C++の魔改造テンプレートやマイナーデータ構造ライブラリを作ったことにより、Pythonより速いスピードでコーディングができるようになりました。例をお見せしましょう
int main(){ INT(n,k,q); vl a(n,0); Treap<> ps; rep(i,n){ ps.insert(0); } while(q--){ INT(x,y);x--; ps.erase(a[x]); ps.insert(y); a[x]=y; print(ps.query(n-k,n)); } }
これはABC306のE問題です。ライブラリ、テンプレートは省略しています。 とても短いですね。どれくらい短いのかというとC++の解説コードは65行もありますが、このコードは15行しかありません。つまり1/4以下の記述量で問題が解けるということです。うれしいね。
いろいろなデータを見る
パフォーマンスのグラフ
パフォーマンスのグラフです。相変わらずパフォーマンスが不安定ですね。
一度灰perfが出ていますね。本当に水コーダーか？
割と水perfが安定してきているような気がしないでもないのでこの調子で頑張りたいです。
Heatmapのmax difficulty
ちょうど真ん中までが茶コーダー時代、それ以降が緑コーダー時代です。
明らかに水や青の量が多いですね！えらい！
精進グラフ
赤コーダーです！やったね！！（うれしくない）
コードゴルフ楽しいよという話
コードゴルフに少しハマってshortestを30個くらい持っています。 Pythonメインでやっているのですが、Pythonの謎記法やCythonのfor文の仕様を知ることができたりしてABC前半の早解きにもかなり役立っている気がします。最初のshortestから100byte近く更新できることもあってすごく楽しいです。ぜひコードゴルフをやってみてください。でも私のshortestは更新しないでくださいお願いします何でもしますから
目標
今年中に青コーダーになりたいです。
これまでの色変は全て半年おきに達成しているので青にも半年でなりたいですね。
それでは12月、入青記事でお会いしましょう。ではまた！
Mo'sの計算量を考える
まえがき
前回のABC293-GでMo's Algorithmを学んだのですが、計算量が直感的にわかりにくいと思ったので備忘録として書きます。
そもそもMo'sってなに
概要
- 範囲
の中の
形式のクエリが
個与えらる問題
とか
とかにする操作が軽い(
くらいまで)
- クエリがオフラインで与えられる
問題を、ずらす操作の計算量をとしたときに
で解くことのできるアルゴリズム
やること
を
とする
- 次の法則でソートする
が小さい順にソートする
でソートする(
- あとは最初のクエリから順番に尺取り法のようなことをして処理していく
コード
ほとんどei1333さんの実装を写経しました
ごめんなさい
Mo mo(n)で範囲がの構造体を作る
mo.add(int l,int r)でmo.build(add,erase,out)クエリの幅を一つ伸ばすときの関数add、縮めるときの関数erase、クエリに保存する関数outを与えたら全部やってくれるmo.build(add_left,add_right,erase_left,erase_right)左右に伸ばすときや縮めるときの関数が違うときにどうぞ
struct Mo{ int n; vector<pair<int,int>> lr; explicit Mo(int n):n(n){} void add(int l,int r){/*[l,r)*/ lr.emplace_back(l,r); } template<typename AL,typename AR,typename EL,typename ER,typename O> void build(const AL &add_left,const AR &add_right,const EL &erase_left,const ER &erase_right,const O &out){ int q=lr.size(); int width=n/min<int>(n,sqrt(q)); std::vector<int> order(q); std::iota(order.begin(),order.end(),0); std::sort(order.begin(),order.end(),[&](int a,int b){ int a_block=lr[a].first/width,b_block=lr[b].first/width; if(a_block!=b_block)return a_block<b_block; return a_block%2==0 ? lr[a].second<lr[b].second : lr[a].second>lr[b].second; }); int l=0,r=0; for(auto i:order){ while(l>lr[i].first)add_left(--l); while(r<lr[i].second)add_right(r++); while(l<lr[i].first)erase_left(l++); while(r>lr[i].second)erase_right(--r); out(i); } } template<typename A,typename E,typename O> void build(const A &add,const E & erase,const O &out){ build(add,add,erase,erase,out); } };
本題
合計で個のクエリがあり、クエリがソートされた時の
は毎回高々
しか動かない(幅
ごとにソートされているので)。
なのでを動かすのは合計で
回。
分母と分子にを掛けると
になるので結局ずらす操作を
としたときに
になる。
次はについて考える。
各ブロックごとに高々回しか移動しない。
ブロックは個あるので、ずらす操作を
としたときに合計
になる。
すげー(小並感)
あとがき
なぜ本題の方が短いのですか
ありがとうございました。
