ごりちゃんの尺取り法テンプレ
尺取り法といえば、英語だと Two Pointers Technique とか呼ばれているように、lとr 2つのポインタを動かしながら条件に合う区間を調べるアルゴリズムですね。
いろんな人のコードを見るといろんな流派があり、l固定派と r固定派、for-while型と while-while型とか色々です。
理屈を学んでいても、いざ書こうというときに、どう書くんだっけ?となりやすいアルゴリズムでもあると思います(諸説あり)
そこで、筆者ごりちゃんがPythonでいつも使っているテンプレを共有します!
テンプレ
l固定、for-while型です。
何らかの集合に条件を満たす限りA[r]を入れて、条件を満たす区間の数を調べるシチュエーションを想定しています。
ans = 0 r = 0 for l in range(N): while r < N and #「A[r]を集合に入れたときに条件を満たすか」: #「A[r]を集合に加える」 r += 1 #「A[l]を集合から取り除く」 ans += r - l
#で記した3箇所を、実際の目的に合わせて書き換える形になります。
使用例
#SortedSet略 N,D = map(int,input().split()) A = list(map(int,input().split())) INF = 10**18 ss = SortedSet([-INF, INF]) ans = 0 r = 0 for l in range(N): while r < N and A[r] - ss.le(A[r]) >= D and ss.ge(A[r]) - A[r] >= D: ss.add(A[r]) r += 1 ss.discard(A[l]) ans += r - l print(ans)
テンプレと見比べてみてください。3箇所の記述でACしています。
条件を満たすかのところだけちょっとややこしいですが、もちろんwhileの中で判定してもokです。
おわり
尺取り法はどう書くんだっけ?ってなりがちですが、テンプレがあれば怖くない!
みなさんもテンプレを用意して良き競プロライフを!
休職しました
公表しようか迷いました
が、現状と向き合うため、(あと、Xなどで日常生活を呟きたいときに不都合が生じるため)
現状がどうなってるか書きます
実はごりちゃん、2025年末ごろから休職しています。
そろそろ最後に会社に行って1ヶ月になります。
長い長い年末年始です。
オフ会などの会話でも「ごりちゃんも明日も仕事ですよね」と聞かれた時に「実は明日お休みなんですよ〜」と答えていたのですが、心の中では、(実は明日も明後日もずっと休みなんですよね〜)みたいに思って心苦しくなっていました。
何が起こっている!?
症状としては過眠、というのでしょうか。
寝ても寝ても、寝たくなってしまうような感じです。
元々平日も8〜9時間眠りたい、ロングスリーパー気味の社会人だったのですが、それがある時から10時間眠っても疲れが取れなくて、午前中休んでもまだ疲れが取れなくて、結局会社を休んで寝て過ごす、みたいな日が増え始め、いよいよ週2~3しかまともに勤務できなくなりました。
休職して1ヶ月の今もそうなのですが、予定がない日は寝潰してしまいます。
具体的には、朝11時ごろ起きて朝食を食べる、そしてさらに寝て15時ごろに寝て昼食を食べる、さらに18時ぐらいまで寝て、何もせずゴロゴロしたり、夕食を食べたり酒を飲んだりして過ごし、夜12時に寝る、などです。
合計14~16時間ぐらいを寝て過ごし、目が覚めているが横になっている時間も含めると1日20時間を超えます。
逆に、競プロやオフ会、通院など予定のある日はそれに合わせて動くことができています。
(ただその翌日は反動で寝潰すこともしばしば)
どうしてこうなった!?
行きつけのメンクリからは「抑うつ神経症」という診断を受けています。
ネットで調べると、特定の出来事が原因になっていることが多いと書いてあるのですが、直近に心当たりがなくなんでこうなったのかよくわかっていません。
職場の人間関係や仕事内容に不満もなかったです。
ただ、一つ挙げるなら職場には「できる人」が多く、彼らと比べてあまり活躍できていない感じがして勝手につらくなっていたりできない自分にストレスになっていた可能性はあるかも、とか思っています
この辺は仮説であって、なにもわかりません。
ちなみに競プロの成績が振るわないのはなにも原因にはなってないと思ってますw
(仮に緑落ちしても楽しんで続けてそうなので)
復職か?転職か?
まあなんか仮に転職すれば環境が変わって状況が好転するのではないかと1割ぐらい考えました
ただこれはギャンブル要素が強いというか、さらに悪化したら目も当てられないので、あんまりそれは考えられないなあ、という結論になっています
1日8時間が精一杯というかそれだけの労働を確保するのも今の状態だとしんどいので、この記事を公開したらあんまり拾ってくれる会社はない気がします。
かといってフリーランスになるのも時間と身体が資本だからさらに大変そうですよね。。
まずはちゃんと回復してからの復職を目指すことにします。
(こんな状態のごりちゃんでも受け入れてくれる会社があればお話は聞きに行きますのでご連絡ください)
休職の金銭事情
これ、知らない方も多いと思うので触れようと思います
休職中は恐ろしいことに無給なのですよね (それは、そう)
でも家賃や生活費でお金が減っていくので、貯金の少ないゴリはすぐに親のスネをかじることになっちゃいそう!?
そんな人のための救済措置が傷病手当金で、健保に承認されれば月の給与の2/3ほどがもらえるそうです。
支給までに1ヶ月ぐらいラグがあるそうで、もらえるまでつらそうです。
住民税や保険料などの税金はそのまま払わなきゃいけないので、手取り換算だと元の手取りの5~6割になりそうです。
もらえないと困る!のですが、もらえたとしても旅行に行ってやるぞ〜みたいなお金の使い方は出来なさそうです。
質素に暮らします。
あと、傷病手当金は最長で1年6ヶ月までしかもらえないので、いつまでも回復できなかったりして復職出来ないとやっぱり親のスネかじりになるおそれがあります
ここは不安でたまりません
休職中の過ごし方
休職が決まった時、やったぜ〜有意義に過ごしてやるぞ、ぐへへへへ とか思っていました
毎日思い切り精進して競プロ強くなってやろう、とか、好きなだけゲームをしようとか、好きなだけ本やアニメを見ようとか、やりたいですよね
でも、休職してみて、今のところ、日々をほとんど寝ることにしか使えていないので、今は一応病人なんだなと実感する日々です。
好きなことやりたいことがあっても、寝ていたい気持ちが勝ってしまったりして、思うように動けないのですよね。。
まあ病気で仕事を休む人の態度としては休息に努めるのは正しいと思うので、焦らないで動けるようになるときを待ちたいと思います。
AtCoderのない平日は暇がちです。かつ、予定があれば動けるので、近隣で遊んでくれる方などがいたら声をかけてくれると嬉しいです
おわり
以上ごりちゃんのご報告でした。
ここまで読んでくださってありがとうございます
今後も毎週の競プロコンテストや、趣味の競プロオンサイト巡りもできる範囲でやっていくので、変わらない応援を何卒よろしくお願いします
🦍〜
2025年競プロオンサイト紀行
ゴリ〜〜🦍

こんばんは、いろんな競プロオンサイトに出没するゴリラこと、prd_xxxです。
2025年も早いもので終わっちゃうので、どんなオンサイトに行ったか振り返っていきます
(𝕏に食べたもの記録してるはず...遡っていくか...)
(食べ物メインよりの記事です) 去年の記事
参加したものたち
1/5 KUPC(京都)
京都大学での久々のオンサイトで、ゴリは初潜入でした
近くのインドカレーやさん!
ナマステキッチンなう pic.twitter.com/4HriVK5EDp
— ごりちゃん🦍 (@prd_xxx) 2025年1月5日賞状をいただいて嬉しかった!(これは食べ物ではないか)
オンサイトFA取ってたらしくて賞状をいただいてしまった〜! #kupc2024 pic.twitter.com/JLuFpZDWHq
— ごりちゃん🦍 (@prd_xxx) 2025年1月5日おばんざいを食べて帰路に
おばんざいと日本酒でおバンザイ🙌 pic.twitter.com/mT1xIFk2tI
— ごりちゃん🦍 (@prd_xxx) 2025年1月5日帰りは新幹線 (行きは夜行バスだった) 弾丸!
またね! pic.twitter.com/F7Cn6VRv9x
— ごりちゃん🦍 (@prd_xxx) 2025年1月5日
3月はオンサイトラッシュ
- 全部行きました
3月を乗り切れ!3月の有志オンサイトラッシュ一覧!
— 競プロオンサイト情報! (@kyopro_onsite) 2025年3月7日
3/8(土) UTPC (東京大)#utpc2024
3/9(日) TUATPC (農工大)#TUATPC2025Spring
3/15(土),16(日) OUPC (大阪大)#OUPC
3/22(土)〜24(月) ACPC (会津大) #ACPC2025
3/29(土) NUPC (名古屋大)#NUPC2024
3/8 UTPC (東京)
オンサイトラッシュ!耐えてくれよ身体!
- UTPCは食べ物の写真撮ってなかった!残念!
ゴリ〜 (対戦よろしくお願いします) pic.twitter.com/KuqZ8Ef7sL
— ごりちゃん🦍 (@prd_xxx) 2025年3月8日
3/9 TUATPC (東京)
東京農工大学にも初潜入でした!
- 油そば美味しかった 次も行く時は絶対ここ!
北府中、ランチどころなさすぎてびっくりしたけど、キャンパスの方面に近づいたら油そばにありつけた pic.twitter.com/jfJKaAXl7O
— ごりちゃん🦍 (@prd_xxx) 2025年3月9日
3/15〜16 OUPC (大阪)
2days!安くてバスタオルの無いホテルに泊まってABC出て、帰りは快活clubでAHCでてヤコバで帰ったよ!
宿の近くにあったラーメン屋!
むひ いただきます pic.twitter.com/eMXMYysYTA
— ごりちゃん🦍 (@prd_xxx) 2025年3月15日みんなでコメダに行ったよ
コメダで飯!このあと快活club行ってAHC出る!ちょっと遅れるかな pic.twitter.com/w04YQyY0Ty
— ごりちゃん🦍 (@prd_xxx) 2025年3月16日すっかりお気に入りの大衆酒場!安くて早くてうまい!
安くて早いタイプで非常に助かる pic.twitter.com/Hhp1f8F0sT
— ごりちゃん🦍 (@prd_xxx) 2025年3月16日
3/22〜24 ACPC (福島)
わーい!!
赤べこに乗るごりちゃん (食べ物ではない)
わーーーい!! pic.twitter.com/8qVBzXIfhm
— ごりちゃん🦍 (@prd_xxx) 2025年3月22日初ステーキ宮!
さあ,目的地に向かって移動開始だ!とあなたは意気込んでいるところかもしれないが,ちょっと待ってほしい.一つだけ先に忠告しておくことがある.それはこのマス目に潜む謎の人物,ステーキのプロ・ステーキ宮の存在だ. pic.twitter.com/eoMnaWubst
— ごりちゃん🦍 (@prd_xxx) 2025年3月22日喜多方チャーシュー! pic.twitter.com/pGqJGijtH9
— ごりちゃん🦍 (@prd_xxx) 2025年3月22日2日目は普通にガストなんだけど肉厚ステーキ風ハンバーグはうまかったよ
本当はカツのお店に目をつけていたが腹が減ってガストに入ってきてしまった pic.twitter.com/NQHIxcb9d5
— ごりちゃん🦍 (@prd_xxx) 2025年3月23日3日目は目をつけてたソースかつ丼屋さん!
特製ソースかつ丼! pic.twitter.com/hECCaypjMf
— ごりちゃん🦍 (@prd_xxx) 2025年3月24日
3/29 NUPC (愛知)
オンサイトは1dayだけど1泊して翌日遊びました
名古屋駅のラーメン!
名古屋でゴヤゴヤ pic.twitter.com/dFH81A5bTu
— ごりちゃん🦍 (@prd_xxx) 2025年3月29日いつも食べてる直大 (名古屋産)
青復帰するぞ! pic.twitter.com/xsSCbocjm9
— ごりちゃん🦍 (@prd_xxx) 2025年3月29日宿のモーニング
モーニングごりちゃん pic.twitter.com/YXsa01Urkq
— ごりちゃん🦍 (@prd_xxx) 2025年3月29日やばとん美味いよね〜!
矢場とんキター pic.twitter.com/6vYD9ctqbt
— ごりちゃん🦍 (@prd_xxx) 2025年3月30日大須で適当にアウトドア飲酒してた
アウトドア飲酒していくぞ pic.twitter.com/av0B5ie5Fk
— ごりちゃん🦍 (@prd_xxx) 2025年3月30日途中からインドア飲酒になった
腹がいっぱいなのにケバブサンドを諦められなかった男 pic.twitter.com/YpRfRl796e
— ごりちゃん🦍 (@prd_xxx) 2025年3月30日帰りもやってた よく食べたなあ
新幹線のおともだち pic.twitter.com/87H5Axljwu
— ごりちゃん🦍 (@prd_xxx) 2025年3月30日
8/8 モノグサさんオンサイト (東京)
- わーい!ありがとうございます!
卓球台のうえにピザも並べられていました pic.twitter.com/E2diEJHnr7
— ごりちゃん🦍 (@prd_xxx) 2025年8月8日
10/5 MMAコン (東京)
いつもの(いつもの) 調布!!
調布といえばうなぎ!(か、すた丼!)
調布といえば、うなぎですよね〜 ぐへへへ pic.twitter.com/EwFKjoIrDA
— ごりちゃん🦍 (@prd_xxx) 2025年10月5日なぜかその日ワタッコさんと
ワタッコさんと銀だこしてました 楽しかった! pic.twitter.com/NyFDDhAdvz
— ごりちゃん🦍 (@prd_xxx) 2025年10月5日
11/8 STPC (東京)
わいわい!東京科学大学2回目!
- 残念ながら食べ物の写真はなかった!帰りABCに間に合わすためにマックで急いで食った記憶
会場にきた #STPC2025 pic.twitter.com/IWOYrmAhuq
— ごりちゃん🦍 (@prd_xxx) 2025年11月8日
11/16 ITF.PC (東京)
つくばじゃなく東京キャンパス!初来訪!
- 茗荷谷も美味しい洋食があって良いね
洋食やさんの洋食!!! pic.twitter.com/2o4Xck8MBR
— ごりちゃん🦍 (@prd_xxx) 2025年11月16日
開催したものたち
4/26 TOUPC
当日がAHCとかぶってたから問題はテスターをやらせてもらい当日は現地でAHCに出るという良いとこどり(!?)をした
帰りにインドカレーやさん!
うひょ〜!!! pic.twitter.com/p4HGly5Qbn
— ごりちゃん🦍 (@prd_xxx) 2025年4月26日2次会も行ってたね
ABC403.5、開幕です! pic.twitter.com/6L1ERbIlIM
— ごりちゃん🦍 (@prd_xxx) 2025年4月26日
5/31 ゆるふわオンサイト
会社で開催してる競プロオンサイト!いつもみなさんありがとうございます!
- ピザとお寿司!スタッフもいただきました (画像お借りしました)
#ゆるふわオンサイト
— 遠宮歩 / kmmtkm (@ayumu_togu) 2025年5月31日
とてもとても楽しかったですし、いつもの方以外にも、新しく話せた方がいて良かったです!
ランチ組・カラオケ組もありがとうございました!(私は先に抜けましたが、カラオケ組終電を逃したっぽい…?)
また次のオンサイトで! pic.twitter.com/JLgrOyc0dS
(おまけ) オンサイト以外だけど食べたものなど
1/12 競プロ新年会
not オンサイト大会ですが、新年会がありましたね!
着いた!情報です #kyopro pic.twitter.com/HGY8W4M67W
— ごりちゃん🦍 (@prd_xxx) 2025年1月12日
1/15 ユニークビジョンさん懇親会
いつもありがとうございます pic.twitter.com/VDA7USmBcA
— ごりちゃん🦍 (@prd_xxx) 2025年1月15日
2/23〜26 沖縄旅行
オンサイトなしの旅行、レアすぎた
初上陸沖縄!
しかし結局、ホテルにこもってAHCやってたようなw
きたぜ〜〜 沖縄!! pic.twitter.com/DQSKzNpskp
— ごりちゃん🦍 (@prd_xxx) 2025年2月23日
腹がへったので pic.twitter.com/1Z1YB8BTQj
— ごりちゃん🦍 (@prd_xxx) 2025年2月24日
たのしい朝ごはん2 pic.twitter.com/0Dp4rdLCEB
— ごりちゃん🦍 (@prd_xxx) 2025年2月24日
うひひひ pic.twitter.com/qaHQyjAtPa
— ごりちゃん🦍 (@prd_xxx) 2025年2月25日
5/26 競プロ部歓迎会
社の競プロ部の歓迎会だったよ 今年の新卒は競プロerいないな〜って思ってたら、3人も始めてくれた! pic.twitter.com/BTb4hgzLBt
— ごりちゃん🦍 (@prd_xxx) 2025年5月26日
6/7 弟氏結婚式
- 感動した
ムヒヒ pic.twitter.com/uoZYAqrFw0
— ごりちゃん🦍 (@prd_xxx) 2025年6月7日
6/25 BrainPadさん懇親会
情報です #AHC046 pic.twitter.com/HFuU8Nz0X2
— ごりちゃん🦍 (@prd_xxx) 2025年6月25日
7/4 競プロerたちと
競プロerたち pic.twitter.com/1yyLHrGyGo
— ごりちゃん🦍 (@prd_xxx) 2025年7月4日
7/9 ユニークビジョンさん懇親会
ユニビさん 情報です pic.twitter.com/GbYPDkpWwC
— ごりちゃん🦍 (@prd_xxx) 2025年7月9日
7/20 妹氏結婚式
- めっちゃ良き日だった
とてもおいしかったです pic.twitter.com/ZQXPqMYmfr
— ごりちゃん🦍 (@prd_xxx) 2025年7月20日
9/12 会社の歓迎会
- ムヒヒ
会社のお金で寿司食べすぎて爆発寸前のセルになった pic.twitter.com/gWQzHcjaiV
— ごりちゃん🦍 (@prd_xxx) 2025年9月12日
9/21〜22 競プロキャンプ (兵庫)
おはようございます 鈴鹿PAの抹茶そばから朝は始まります #kyoprocamp pic.twitter.com/jJVTJVrSrM
— ごりちゃん🦍 (@prd_xxx) 2025年9月20日
- バーベキューでみんなで飲もうと角瓶を持って行ったらそれよりでかいのを持ってきてる人がいて負けた思い出
よりでかいフリーウイスキーがデプロイされた ごりちゃんは負けた #kyoprocamp pic.twitter.com/QSAXfulOwP
— ごりちゃん🦍 (@prd_xxx) 2025年9月21日
極厚のにくが焼かれている #kyoprocamp pic.twitter.com/ttOJ71IThY
— ごりちゃん🦍 (@prd_xxx) 2025年9月21日
#kyoprocamp 夕食! pic.twitter.com/RL6n232gp0
— ごりちゃん🦍 (@prd_xxx) 2025年9月21日
ちゃんとした朝食! #kyoprocamp pic.twitter.com/DN0OICkN27
— ごりちゃん🦍 (@prd_xxx) 2025年9月21日
むひひひ お昼 #kyoprocamp pic.twitter.com/jKf0oqoBCu
— ごりちゃん🦍 (@prd_xxx) 2025年9月22日
- ここのおでん大根の唐揚げが美味かった
#kyoprocamp 二次会 飲んで食ってばっかだな! pic.twitter.com/7VXsgCPEfA
— ごりちゃん🦍 (@prd_xxx) 2025年9月22日
9/23 競プロキャンプ翌日
姫路駅で!美味しかった!
加古川かつめし!! pic.twitter.com/Mmpz3YuNot
— ごりちゃん🦍 (@prd_xxx) 2025年9月23日例の大阪の大衆酒場
きょうも大衆酒場! pic.twitter.com/PQMvNVdwPT
— ごりちゃん🦍 (@prd_xxx) 2025年9月23日
9/24 ごりちゃん誕生日
- みんな覚えてください!9・24!
誕生日はロイホでディナー これやってるの3年目🦍✨ pic.twitter.com/8PTqqXHlrZ
— ごりちゃん🦍 (@prd_xxx) 2025年9月24日
11/2 地元の友達と
- おうち飲みはいいぞ
地元の盟友をうちに招いて楽しいことしてる pic.twitter.com/DPb3MWwhqW
— ごりちゃん🦍 (@prd_xxx) 2025年11月2日
11/3 弐寺競プロお酒会
- 競プロはやらなかった日
弐寺競プロお酒会のなけなしの競プロ成分 (お店の名前が「たかはし」) pic.twitter.com/upH4CIO7ur
— ごりちゃん🦍 (@prd_xxx) 2025年11月3日
11/25 Polaris.AI さん懇親会
きたー!! pic.twitter.com/Zrv8Q2WjLj
— ごりちゃん🦍 (@prd_xxx) 2025年11月25日
12/13 AtCoder Conference
帰りにみんなでカレーたべたよ pic.twitter.com/yZpnttdKev
— ごりちゃん🦍 (@prd_xxx) 2025年12月13日
12/22 80's競プロer忘年会
- みんなありがとう!!
こ、これは、、!!しゃぶ!!!!! pic.twitter.com/UYvMH2N4rx
— ごりちゃん🦍 (@prd_xxx) 2025年12月22日
おわり
𝕏の画像遡ってて思ったけどサイゼとバーキン好きすぎね。
自炊はよくカレーとペペロンチーノ作ってるね
来年もいろんなオンサイト行っていろんなもの食べられますように
大集合!!!! pic.twitter.com/wjvOs6uO0E
— ごりちゃん🦍 (@prd_xxx) 2025年4月26日
"""The #MMAContest """ pic.twitter.com/iNTas08tZm
— ごりちゃん🦍 (@prd_xxx) 2025年10月5日
ではまた!
1からNまでのnについて、nの約数の個数の総和を求める
ごり〜
こんばんは
高校数学ぐらいの内容ですが、整理していたらいくつか気づきがあったので記します
唐突ですが、「から
までの
について、
の約数の個数の総和」をどう求めるか?を考えていきたいと思います
の大きさとしては
ぐらいのを高速に求めたいです
なお、この記事で約数の個数とは、正の約数の個数を指します
出てくるグラフも を定義域としています
ご了承ください
復習
約数
整数 の約数とは、
を割り切ることのできる整数です
以下、例としてから
までの
について、
の約数を集合で表します
の約数:
の約数:
の約数:
の約数:
の約数:
の約数:
の約数:
の約数:
の約数:
の約数:
約数の個数
約数の 個数 に注目します。一般的な特徴は以下のようになります
1の場合
の
個だけです。
素数の場合
が素数の場合、約数は
と
自身のちょうど
個です。
合成数の場合
が合成数の場合、約数は
と
の他にも
個以上存在します。
特に、が平方数の場合は奇数個、そうでない場合は偶数個となります。
一般の場合
を素因数分解した結果が
(
は素数)として、
の約数の個数は
となります
これを題材にした出題も、ときどき出てくるイメージなので忘れないようにしたいですね! (今日は使いません)
(おまけ) 高度合成数
約数の個数に触れたので高度合成数というものにも軽く触れておきます。
約数の個数が多いやつは高度合成数と呼ばれて、こんな感じです
高度合成数の一覧 | アルゴ式
この辺はキラーケースになることが多いです
反比例のグラフに乗る
の約数は、反比例のグラフ
に乗ります。
を通る格子点の
座標を列挙すると(または
座標でも同じ)、
の約数に一致します。
下の図1では、の例で、格子点の
座標は
となり、
の約数と一致します。

の約数の個数は、
を通る格子点の個数に一致する
というのも、個人的には忘れがち/ 見逃しがちな言い換えな気がします
例えば、の約数は
個 ⇔
を通る格子点は
個
です
本題
「から
までの
について、
の約数の個数の総和」 を求めたいのですが、図にすると以下の図2の赤線の部分 (赤ドットの数)を数えたいです。

理由としては、以下の図3を見てほしいのですが、から
までの
について、先ほどの
のグラフを重ねていくと、
より内側の格子点をすべてもれなくカバーしていることがわかります (図では
)

から
までの
について、
の約数の個数の総和」 とは、
のグラフの内側にある格子点の個数 と問題を言い換えることができました。
Nが小さい場合
まず の場合を考えます。
この場合は、下の図4のように縦に数えるだけで良いです。

が
から
にいたるまで、
を足して行けば良いです (
は床関数、整数切り捨て)
さて、が大きい場合はどうしましょう...???
Nが大きい場合
本題の本題です。 の場合は、先ほどの方法では計算時間は間に合わず、大部分が計算できてないように思われます。
ところが、不思議なことにあとちょっとの工夫で求まるようになります。
キーワードは で分割する です!
個人的に一番わかりやすいアプローチはこれでした。
以下、図をABC230-E kyopro_friendsさんのユーザ解説 より引用しています

① = ② + ③ - ④
ということで、①が求めたいもので、②③④を求めれば良いと言っています。
そして、②と③は「斜めに折り返すと等しい」と書いてあります。
は
と
が対称な形をしており、
がちょうど
と
が等しい部分になります。
そのため、②③のようにで分割すると、漏れなく①の領域をカバーできます。
しかも、対称なので、②を求めて
倍するだけで③を足したことになります!
②の図はが小さい場合のように縦に足していき、
として、
から
までで打ち切れば良さそうですね。
最後に、ダブルカウントしている領域は④の部分だけになるので、ここは単に を引けば良いです。
これでが大きい場合についても、「
から
までの
について、
の約数の個数の総和」を求めることができました!
めでたし!
おまけ
問題リンク
ゆるふわオンサイト#8 Writer記
ゴリ〜

先日はゆるふわオンサイト#8のご参加ありがとうございました!
コンテストサイト
解説スライド
writer記というほどwriterをしてないのですが、A,B問題を作問したので裏話などを書こうと思います
ちょうどゆるふわのゆるふわの部分ですね
第8回はC問題から牙をむいていたのでゆるふわじゃないじゃん!と思った方ごめんなさい
ちなみにゆるふわオンサイトがゆるふわではないというご指摘は方々から頂いております
ちなみにちなむとゆるふわオンサイトの「ゆるふわ」は問題が「ゆるふわ」の意味じゃないよ、というのは釈明しておきます
オンサイトが公式でしか開かれてなかった時代に、予選なしで参加できるゆるふわなオンサイトとして登場したみたいです!
— ももはら (@momohara_kyopro) May 31, 2025
今だと非公式なオンサイトも増えててたくさん参加できていいですね☺#ゆるふわオンサイト https://t.co/vmP9DuxgSI
要は予選を突破しなくても出られるという意味で ゆるふわですよ〜ってことです
いろんな層の人に楽しんでもらえるコンテストを目指しています (本当ですよ!)
準備に割けるリソースとの兼ね合いで、問題数が多くは出せず、崖がどうしてもどこかにできてしまうのはご容赦ください🙇
以下、問題のネタバレを含みますので念のためご注意ください
A問題 Progress Report Decreasing... (200点)
これがA問題で出たのはギョッとしたでしょう!(ごめんなさい)
ギョッとしていただければ幸いです^^
これより前にもう1問簡単なのが入る予定だったのですが準備の都合でカットされました
やるだけを期待していた方(?) すみません、、
準備陣の見立てでは灰diffと茶diffの境目ぐらいを予想していました
文字列でやるのに気づかないと沼ってしまい茶diffもあり得る?とかABCではCぐらい?とか言われていました
0点で帰られる方がもしいたら申し訳ないと思い、せめてもの部分点を入れました
(結果的にBは全員に解いてくださったのでその心配はありませんでした)
作問の経緯ですが、進捗報告の%って失速するよね〜 とか 進捗報告は終盤ほど刻むよね〜 みたいな話題から生まれました
途中まで勢いよく90%までいったのに突然93%みたいに刻んでいくやつですね (社会人になってあんまりそのシチュエーションは見たことないですが、大学の研究室で見た気がします)
で、それを思い出して式をいじってたら面白い式ができたので問題にしました
それを題材にもっとひねることもできたのですが、これはこれで出力だけで問題にしました
出力だけでも地味に面倒な問題だったと思います
ちなみにどうでも良いのですが問題名の頭文字をとるとPRD...になるのお気づきでしたでしょうか
ここはPRDにしたくなってしれっと仕込んだのでした (無意味な自己顕示欲)
B問題 Edible Card Game (200点)
はい、A問題より簡単だった疑惑のある、これです
ゆるふわオンサイトの本当のゆるふわの部分ですね(?)
これ、問題に対して思いつくことが値の大きい方から貪欲に取るぐらいしかなく、かつそれで正しいので、解法で迷うことはなかったんじゃないかなと予想しています
ちゃんと正当性を示すと (それはそうという結果ではあるが) 面白いと思うので、直感で貪欲した方は考えてみてください
少しでも迷ってくれたら儲けもんぐらいの理由で NやAの制約を無意味に小さくしたりして出しました
ちなみに、これの原案自体はN=2で、A問題に置かれるのを想定して作った問題でした
(A問題なのでif文だけで解けるけどやるだけは避けたい、ある程度考えさせたい、という意図がありました)
これを提案したら、一般のNでも同じ性質が成り立つから一般のNで出して、後ろに追いやった方が良いのでは?となり、PRD...より後ろに来ました
実際はN=2でもN<=1000でも難易度はほとんど変わらなかった説ありますね
問題セットが揃ったときに、Aより簡単ではないかという議論はされたのですが、誤差じゃないかということでそのままになりました
(実際どちらも同じ200点をつけています)
なお、原案はカードゲームではなくてAtCoderのレーティング (アルゴ、ヒュ) でじゃんけんをさせるものでした
ちょうど (アルゴ、ヒュ) の2次元の評価軸がある場合の序列について話題になっていたので、それにあやかって、アルゴとヒュの好きな方を先に出せるじゃんけんにしたら面白くね?という提案でした
C以降
他にいくつかABCライクな「やるだけ」問題を書いたりしていましたが今回は採用されませんでした
(自分はやるだけしか書けないので...)
解いててより楽しいのはARCライクな「考察」要素が強い問題だと思うので、そういう問題をできるだけ出そうと準備陣は頑張っていました
アンケートでは実際に好評をいただいた問題が多くて、嬉しかったです
おわり
以上です!
コンテストを楽しんでいただけたなら幸いです!
次回もきっと頑張ります!
2024年競プロオンサイト紀行
ごり~🦍
今年は気づいたらたくさん競プロオンサイトに参加してしまいました、prd_xxx です
競プロの次の趣味を聞かれたら「競プロオンサイト巡り」と答えても過言ではないかもしれません
というわけで、今年参加したオンサイトをまとめていきます!
(食べ物メインよりの記事です)
参加したものたち
1/6,7 OUPC (大阪)
新年から2日制オンサイトで、夜行バス1泊+ホテル2泊の3日間大阪を楽しんだ!
とりあえず寄ってみたかったところ
ごりちゃんの聖地、ごりちゃん pic.twitter.com/DlV88Rsx2C
— ごりちゃん🦍 (@prd_xxx) 2024年1月5日Day.1 のチームメンバーとお好み焼き&もんじゃ!
ゴリ・ディナー! pic.twitter.com/WZ5PkvQnfK
— ごりちゃん🦍 (@prd_xxx) 2024年1月6日Day.2 の昼は阪大のカフェバーガー
うおお!阪大のおしゃれなカフェテリアのおしゃれなバーガー! pic.twitter.com/tr5xSekVRU
— ごりちゃん🦍 (@prd_xxx) 2024年1月7日夜はカロリーを摂った
あの ちがうんです 唐揚げが想定よりでかかっただけなんです カロリーを摂りすぎるつもりじゃないんです pic.twitter.com/JEFNSg8e4Z
— ごりちゃん🦍 (@prd_xxx) 2024年1月7日Day.3 は大阪観光 なんばを練り歩く
たこ焼き!!たこが大粒であるな pic.twitter.com/nz9OSThDof
— ごりちゃん🦍 (@prd_xxx) 2024年1月8日蟹の炭火焼き とてもsakeがほしい... pic.twitter.com/36KZFpkEUy
— ごりちゃん🦍 (@prd_xxx) 2024年1月8日🦍「オレはコイツと旅に出る」
— ごりちゃん🦍 (@prd_xxx) 2024年1月8日
🍶「ワンカップ」 pic.twitter.com/9WtDWaumaV黒毛和牛ゲット pic.twitter.com/SfPPc1eSZq
— ごりちゃん🦍 (@prd_xxx) 2024年1月8日ワンカップくんとは別れを告げて(飲み干して) 串カツのお店にきた! うめえ! pic.twitter.com/8LpD0M1KZ6
— ごりちゃん🦍 (@prd_xxx) 2024年1月8日たつやんさんと合流 すごいお茶やさんとすごい串カツ屋
大阪のロンドンティールーム! pic.twitter.com/4a8ZQ0b96f
— ごりちゃん🦍 (@prd_xxx) 2024年1月8日カウンターから出てくるタイプの串カツ屋!! pic.twitter.com/qZ3z1WGCeK
— ごりちゃん🦍 (@prd_xxx) 2024年1月8日
3/9 TUPC (宮城)
1年ぶり仙台!夜行バス1泊とカプセルホテルに後泊した!
仙台駅の聖地、石にされたアンパンマン
仙台駅を庇い石にされてしまったアンパンマンと、ぬいぐるみにされてしまったごりちゃん pic.twitter.com/tbbYLN8Lmq
— ごりちゃん🦍 (@prd_xxx) 2024年3月8日牛タンを食べられるランチどころをみつけた
ゴリ・ランチ! pic.twitter.com/BSznOYLMDQ
— ごりちゃん🦍 (@prd_xxx) 2024年3月9日翌日はこたつがめさん御用達の「仔虎」という焼肉屋さん。スーパーうまい。リピートあり
うほおおおおお pic.twitter.com/0gmf84KfEF
— ごりちゃん🦍 (@prd_xxx) 2024年3月10日おそうざいの聖地
これの聖地巡礼やる人あんまりおらんやろ pic.twitter.com/m1wjLgyVLt
— ごりちゃん🦍 (@prd_xxx) 2024年3月10日うまかったお土産
えんがわ好きな人はえんがわずしを買って帰れと𝕏で見たのを奇跡的に思い出して買ってきたのだ これうまいぞ! pic.twitter.com/eVobhC76Iq
— ごりちゃん🦍 (@prd_xxx) 2024年3月10日
3/17 UTPC (東京)
MMさんと組んだのにノートPCを家に忘れるというオンサイトで考えうる最悪をしてしまった... (反省)
- 終わった後、ARC前なのに美味しいお店はいっちゃったね
サイゼに行こうとしたつもりが銀座のバー?に入ってしまった ARC間に合うか? pic.twitter.com/jZ4v3QZxhp
— ごりちゃん🦍 (@prd_xxx) 2024年3月17日むひょー pic.twitter.com/CubBZyLYsm
— ごりちゃん🦍 (@prd_xxx) 2024年3月17日
3/23,24 RUPC (滋賀)
立命館大で2Daysオンサイトが復活!コロナ明け数年ぶり!
新幹線で当日入り、ホテル2泊で3日目は観光をした!(有給休暇)
- Day.1 昼 休日で学食が食えるのはありがたい!
が、しかし、学食がやっていた!かみかみかみかみ神 pic.twitter.com/YEyVgsRtLN
— ごりちゃん🦍 (@prd_xxx) 2024年3月23日 Day.1 夜 みんなで立命館大から下山しつつ、立命生おすすめの油そば屋へ入っていった!
わーい pic.twitter.com/qxCZRzzhYT
— ごりちゃん🦍 (@prd_xxx) 2024年3月23日Day.2 昼 近江牛が食べられる焼肉屋がホテルに併設してたので、行かない手はない!
うひょーー 近江牛の焼肉ランチ!! pic.twitter.com/1K6TFEoH1v
— ごりちゃん🦍 (@prd_xxx) 2024年3月24日国宝 彦根城 をそっちのけでひこにゃんを見てテンションがやばくなってた
動くひこにゃん見られてニッコニコになった pic.twitter.com/uWYf469dks
— ごりちゃん🦍 (@prd_xxx) 2024年3月25日Day.3 夜は近江牛の牛すじが食べられる素敵な居酒屋を見つけて吸い込まれた
画像添付わすれたフヒヒヒすみません!!! pic.twitter.com/r8bM57hG5p
— ごりちゃん🦍 (@prd_xxx) 2024年3月25日串カツもきた!! pic.twitter.com/8ieFEmGJe2
— ごりちゃん🦍 (@prd_xxx) 2024年3月25日うおお おでんと日本酒もきた! ごりちゃんは生きててもいいんですか?? pic.twitter.com/wLU8qL5oDR
— ごりちゃん🦍 (@prd_xxx) 2024年3月25日
3/30 水以下コンテスト (東京)
芝浦工大で初のオンサイトに潜入!
- 勝どき駅から歩いて行けるところで人気のまぐろ丼! (結構並んだけどうまかった)
マグロ丼きた〜〜!!! pic.twitter.com/LpE6v9mMyI
— ごりちゃん🦍 (@prd_xxx) 2024年3月30日
3/31 MMA Contest (東京)
3月はオンサイト尽くしでタフな毎日だった!充実しまくり
- 多摩のソウルフード!すた丼!
多摩のソウルフー〜〜〜ド!!!!! pic.twitter.com/Pn9PVBloRI
— ごりちゃん🦍 (@prd_xxx) 2024年3月31日
8/25 MMA Contest (東京)
しばらくオンサイトが開いたと思ったらまた調布の電通大!
nafmoさん皆さんいつもありがとうございます
調布といえば!すた丼!
すた丼!!! pic.twitter.com/57PkW1Go8O
— ごりちゃん🦍 (@prd_xxx) 2024年8月25日同じ種族と初のご対面
となりにデカいゴリちゃんが来た ガルルル〜 pic.twitter.com/e3ZmGwGQoR
— ごりちゃん🦍 (@prd_xxx) 2024年8月25日調布といえば!うなとともある
ARC183 優勝した pic.twitter.com/WgjwyqqNPF
— ごりちゃん🦍 (@prd_xxx) 2024年8月25日
8/31 Maximum-Cup (埼玉)
景気づけにはま寿司
はま寿司なう pic.twitter.com/ijxNTsGSB6
— ごりちゃん🦍 (@prd_xxx) 2024年8月31日コンテスト後にはマクド (ABCに間に合うギリギリだった)
マクドは大変なものを作っていきました pic.twitter.com/jonxkhclqV
— ごりちゃん🦍 (@prd_xxx) 2024年8月31日
9/15 KUDUPC (京都)
京都産業大学で初のコンテスト! コンテスト自体は1日ですが前日のABC、当日の短期AHCに出るためちゃんと前泊と後泊しました
会場に向かう途中、ごりちゃんが行かずして誰が行く?みたいな (失礼) バナナジュース屋さんを見つけた
??? pic.twitter.com/L6bfEtiKq0
— ごりちゃん🦍 (@prd_xxx) 2024年9月15日4代目にごりちゃんの肖像が
四代目 食ってみな・とぶぞう pic.twitter.com/ehrGyXsHv1
— ごりちゃん🦍 (@prd_xxx) 2024年9月15日オープンキャンパスでにぎわってて学食がやってた!カツうま!
迷ったけど食堂にたどり着いた!ふじカツ! pic.twitter.com/DmqQGgzOU9
— ごりちゃん🦍 (@prd_xxx) 2024年9月15日後泊ホテルの朝食
ごりちゃんのおはよう 春巻きは Spring roll だって pic.twitter.com/GpEMCUIpeB
— ごりちゃん🦍 (@prd_xxx) 2024年9月15日伏見稲荷大社に来ました
ゴリ〜 鳥居〜 pic.twitter.com/3w24Lc2YgB
— ごりちゃん🦍 (@prd_xxx) 2024年9月16日京都っぽいものを食べようとして和食屋さんに入りました
やりぃ pic.twitter.com/oQto4WJoOX
— ごりちゃん🦍 (@prd_xxx) 2024年9月16日帰りの便が欠航というトラブルも、無事に帰りの夜行バスを取ってから余裕のおそばです
電源のある場所を探し求めていたらおそばにたどり着いた pic.twitter.com/2h66UHBmIj
— ごりちゃん🦍 (@prd_xxx) 2024年9月16日
10/12 緑以下コンテスト (東京)
青山学院大学での開催は2回目かな?渋谷でぶやぶや!
おいしいまぐろ丼やさん
渋谷でランチといえば!! (たぶんトヨタのときぶりにきた) pic.twitter.com/lYTQInJ0tl
— ごりちゃん🦍 (@prd_xxx) 2024年10月12日帰りはもうやんカレー!すごく久々!
美味しすぎて、もうイヤーン (©️けんちょん) pic.twitter.com/OyHtgXbtWG
— ごりちゃん🦍 (@prd_xxx) 2024年10月12日
11/17 ITF.PC (茨城)
つくば!TXで日帰りで行ける距離なんだけど、去年前泊したら楽しかったので、無駄に前泊と後泊をした!(月曜は有給休暇)
前日夜、おしゃれなラーメン屋! (自転車を借りてたけどちょっと遠かった)
筑波出身の同僚に教えてもらった麺!! pic.twitter.com/nSvuRxf8yy
— ごりちゃん🦍 (@prd_xxx) 2024年11月16日翌日昼、ずっと来たかったとんかつ!!
いいかい学生さん 社会人さん pic.twitter.com/zbUEql6ouF
— ごりちゃん🦍 (@prd_xxx) 2024年11月18日
12/15 TTPC (東京)
TTPCとしてはこれまでは開催されてたけど、東工(科)大の敷地に入ったのは初めて!
大岡山でおおおおお
- 本格的なカレー屋さんでお疲れ!
お疲れ様でした!!! #TTPC2024 pic.twitter.com/vRo2Ygcv17
— ごりちゃん🦍 (@prd_xxx) 2024年12月15日
開催したものたち
ゆるふわオンサイト、を会社の競プロ部でやってます
お越しくださりありがとうございました!!
2/10 ゆるふわオンサイト (東京)
- sushi!! (大好評だった)
控え室の情報です 胃袋の準備は良いか? #ゆるふわオンサイト pic.twitter.com/QhJVfcgFpy
— ごりちゃん🦍 (@prd_xxx) 2024年2月10日なんでまだ控え室にあるの!?!?!?!? pic.twitter.com/yPoxaUrNVb
— ごりちゃん🦍 (@prd_xxx) 2024年2月10日
9/28 ゆるふわオンサイト (東京)
お寿司とピザをとったんですが、画像がありませんでした :pien:
みんな写真撮ってXに投稿して!(お願いします)
最後に
ゆるゆるっとした飯テロ記事になってしまったかもしれません
競プロオンサイト情報というXアカウントをやっていますのでぜひフォローを!
そしてオンサイトの情報募集しています!
オンサイトは良いぞ!
大集合! #MMAContest pic.twitter.com/WDgIqeiN5D
— ごりちゃん🦍 (@prd_xxx) 2024年3月31日
円環ライブラリ??を書いてみました
ごり〜
こんばんは
前回のABC-376 のBやFで、円環を扱う問題が出ましたね
ゴリはB問題の段階で頭を使いたくないな〜と思った挙句に実際に時計回り/反時計回りにwhileで回す というパワープレイでどうにかACを取りました
が、それでも11分ぐらいかかっちゃったので、あんまり頭を使わない方法を考えていました
TLで 円環ライブラリ を作った、とかの声をちらほら見た気がして、どういうのがあれば楽だったんだろうと自分なりにも考えてみました
それを残します
RingCalculator
というのを作りました。
ごりちゃんライブラリにあげてあります →こちら
使い方なども↑を参照して欲しいのですが、
dist_clockwise(x,y) で、xからyまで時計回りで回ったときの距離、
dist_anticlockwise(x,y) で、xからyまで反時計回りで回ったときの距離
がそれぞれ求まるようにしています。
これがあると例えば、xからみて時計回りでyの方がzよりも近いか?(xからyまでの時計回りの中にzが含まれていないか?) を以下のように判定することができます
rc.dist_clockwise(x,y) < rc.dist_clockwise(x,z)
そして、ABC376-B は以下のコードでACできます。提出
何気に1-indexed にも対応してます (デフォルトは0-indexed)
# https://github.com/prd-xxx/gorichan_kyopro_library/blob/main/ring_calculator/ring_calculator.py class RingCalculator: def __init__(self, size, base_index=0): self.size = size self.base_index = base_index def _normalize(self, index): return (index - self.base_index) % self.size def dist_clockwise(self, from_index, to_index): fr = self._normalize(from_index) to = self._normalize(to_index) return (to - fr) % self.size def dist_anticlockwise(self, from_index, to_index): return (self.size - self.dist_clockwise(from_index, to_index)) % self.size N,Q = map(int,input().split()) HT = [input().split() for i in range(Q)] rc = RingCalculator(N,base_index=1) ans = 0 l,r = 1,2 for h,t in HT: t = int(t) if h=='L': if rc.dist_clockwise(l,t) < rc.dist_clockwise(l,r): ans += rc.dist_clockwise(l,t) else: ans += rc.dist_anticlockwise(l,t) l = t else: if rc.dist_clockwise(r,t) < rc.dist_clockwise(r,l): ans += rc.dist_clockwise(r,t) else: ans += rc.dist_anticlockwise(r,t) r = t print(ans)
おわり
これだけでした
ちょっとしたコードだけど多分次使うときにはありがたみを感じてると信じたい!