競技プログラミング総合スレ 64 YouTube動画>1本 ->画像>3枚

↑2行になるようにする

競技プログラミング、オンラインジャッジ、プログラミングコンテストやCTFに関する雑談スレ
次スレは>>950

AtCoder https://atcoder.jp/
yukicoder https://yukicoder.me/
Codeforces https://codeforces.com/
CodeChef https://codechef.com/
Project Euler https://projecteuler.net/
CLIST https://clist.by/
AtCoder Problems https://kenkoooo.com/atcoder/
AtCoder Clans https://kato-hiro.github.io/AtCoderClans/

※前スレ
競技プログラミング総合スレ 63
http://2chb.net/r/tech/1627477128
VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured

---

VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured

あ、すまん、うっかりテンプレのコマンド部分消してしまったわ
>>950
次スレ立てるときは次のレスのテンプレからコピペしてくれ

コマンド先頭に書こうとしたら弾かれるわ
!extend:checked:vvvvv:1000:512
要は>>950はこれを先頭に２行つけてな
ワッチョイ表示用コマンド、詳細とかはググってくれ

フレームワーク使っていい競技？

数学っぽい問題を解くために一からアルゴリズムのコード書いていくタイプの競技だから、あんまフレームワークを活用できる機会ないかも

そうじゃない
そこはフレームワークなんて使うわけないだろ馬鹿
とか罵るところだろ

どんなフレームワークを使うつもりだったのか聞きたい

業プロの人ってフレームワークとかそういうフワフワした言葉大好きだよね

AtCoderのWebサイトは何のフレームワークで実装されてるんだろう

ここに書いてある

レールは続く】 Ruby on Rails Part21 【これからも
http://2chb.net/r/php/1545146635/103

Rails 製、「爆速すぎて笑う」　表示速度が“異常な”Webサイト「dev.to」　その仕組みは？

BuiltWith で、サイトが使っている技術を調べる

算数パズルにフレームワーク

ライブラリとフレームワークの違いもよくわからんしな

同じdiffでもABCかARCかAGCか、前の方に置かれたか後ろの方に置かれたか、いつごろコンテストが行われたかでだいぶ難易度変わるよな
なんかいい感じの補正できないか

この深層強化学習で行列積アルゴリズムを改善したというnature論文かなり注目されているな
chokudaiもRTしてたし
NNの重み埋め込んで使えば競プロでもウハウハじゃね？って思ったけど、10%とか20%の改善で競プロで劇的に役立つほどの改善じゃなさそう
とはいえ、深層学習とかも中身は結構行列演算だし、人類に相当貢献するアルゴっぽい
https://www.nature.com/articles/s41586-022-05172-4

この論文が特にすごいのは、発見した行列積アルゴリズムそのものよりも、AlphaZeroのやり方で優秀なアルゴリズムも発見できる、ということだけどな

ある工事完了に必要な作業1～6について以下の制約がある。
作業2は作業1が終わるまで開始できない。
作業3は作業1が終わるまで開始できない。
作業4は作業2と3が終わるまで開始できない。
作業5は作業3が終わるまで開始できない。
作業6は作業4と5が終わるまで開始できない。
この工事はT日以内で終えねばならず、各作業iはt_i日かかる。
しかし臨時作業員を雇うことにより作業日数を減らすことができるが、
s_i日よりは少なくはできない。また、1日減らすのにm_i万円かかる。
費用を最小にする作業計画をたてよ。

minimize: 農{i=1}^{6} m_i × (t_i - x_i)
subject to:
x_1 + x_2 + x_4 + x_6 ≦ T
x_1 + x_3 + x_4 + x_6 ≦ T
x_1 + x_3 + x_5 + x_6 ≦ T
s_i ≦ x_i ≦ t_i (i = 1, …, 6)

模範解答では各作業の開始日y_iという変数も考えています。
上の解答は間違っていますか？

合ってると思うぞ
全パスを列挙する必要があるから制約の数が指数オーダーになるが

>>17
ありがとうございました。念のため本に書いてある模範解答を以下に書きます。
minimize: 農{i=1}^{6} m_i × (t_i - x_i)
subject to:
y_1 = 0
y_1 + x_1 ≦ y_2
y_1 + x_1 ≦ y_3
y_2 + x_2 ≦ y_4
y_3 + x_3 ≦ y_4
y_3 + x_3 ≦ y_5
y_4 + x_4 ≦ y_6
y_5 + x_5 ≦ y_6
y_6 + x_6 ≦ T
s_i ≦ x_i ≦ t_i (i = 1, …, 6)

令和のコペルニクス さんによって固定されています
令和のコペルニクス
2 年前（編集済み）
六角アミダって有りそうで無かったので自作しました。xyz空間座標も「６方向」ということで。

ソースコードはこちら。

https://drive.google.com/file/d/1hsFT2F4AMgUv1JHqy0si_7Yj7q7TyHnR/view?usp=sharing

室町時代のアミダくじは円形であること、ベンゼン環の六角構造、赤青緑の三色ダイオードを考えてみた。




令和のコペルニクス
1 年前
地動説をとる人には、地動説をとるのを妨げない。天動説をとる人には、天動説をとるのを妨げない。学説上において人びとの所見を妨げず、かつ実生活においても、「令和のコペルニクス」は決して客観的に善悪正誤など認定しない。

区間最大値の問題解くためにセグメントツリーのアレを書いたら実装に２時間かかったぞこの野郎

じゃあ次はsparse tableを実装しよう

単純な腕力は鍛えて損はない

やはり暴力、暴力はすべてを解決する

明日のARCの配点どんな感じなんだろ
5-7は崖ができやすいので6を増やしてほしい

atcoder.jp/contests/tessoku-book/tasks/tessoku_book_m

この問題の解答として以下のコードを作ったのですが、なぜか小さい入力データに対して
実行時間制限オーバーになってしまいます。大きい入力データに対してはすべてパスしています。

ideone.com/CUJvso

バグを見つけました。

恥ずかしいんだが、競プロ初心者の俺のD問題のコードを見てほしい
bfsを使って解いたんだが、なぜかTLEが出てしまった。
このコードの何がいけないのか有識者教えていただけないだろうか。
次のレスでコードのせます。

import numpy as np
import math

n, m = list(map(int, input().split(" ")))
mapp = np.zeros((n, n)) - 1
mapp[0, 0] = 0

p = []
for i in range(n + 1):
temp = m - i ** 2
if temp < 0:
continue
t = math.sqrt(temp)
if t - int(t) <= 1e-7:
p.append((int(i), round(t)))
temp = []
for a, b in p:
temp.append((-a, -b))
temp.append((a, -b))
temp.append((-a, b))
directions = list(set(temp + p))


def is_inside(pp, qq):
return 0 <= pp <= n - 1 and 0 <= qq <= n - 1


que = [(0, 0)]

while True:
if len(que) == 0:
break
y, x = que.pop(0)
num = mapp[y, x] + 1
for s, t in directions:
yy, xx = y + s, x + t
if not is_inside(yy, xx):
continue
if mapp[yy, xx] != -1:
continue
mapp[yy, xx] = num
que.append((yy, xx))
mapp = mapp.astype(int).astype(str).tolist()

for i in mapp:
print(" ".join(i))

ここにコードを乗せるのは無理があったか

G乱択想定解かー
教育的だね

pastebin辺り使え

>>28
あんま競プロでPython使わないんだけど、まずDってO(N^3)とかO(N^2√M)だから遅い言語だとちょっと定数倍遅いだけで2secで通らなくなるような問題だと思う
そしてそのコードは(x,y)で状態持ってたりしてて定数倍微妙そうなコードだなと思ったな
numpy使ってるってことはPyPyじゃなくてCPythonでしょ？それだとアルゴリズム自体は間違ってなくてもTLEで落ちるんじゃないかな

que.pop(0)ってやってるけど、PythonのlistにFIFOとしての機能あったっけ？
listの内部実装次第だけど、そこで計算量オーダー増えててもおかしくないような
queueを使いたいときにはdequeとか使ってる人が多い印象

suffix arrayってどの色のdiffくらいから前提知識として求められるアルゴリズムなん？

手元のPythonで見てみたけど、listでpop(0)すると配列の長さ分計算時間がかかってそうだから、その書き方だとO(N^4)とかO(N^5)になってるんじゃないかな
ぶっちゃけ別にBFSである必要はないからque.pop(0)→que.pop()でだいぶ早くなるんじゃない？
確かstackとしては使えたはず

深さ優先でも上手く行くんかな

>>35
出る難易度帯からすると青ぐらいの印象
ただ概念的にはそんなに難しくないかなあ（SA-ISというアルゴリズム自体は頭いいけど）
知識的な敷居の高さから後ろに置かれることが多いけど、水色ぐらいでも練習すればACLを活用しつつ普通に解けるレベルの問題も多いと思う

>>29
ちょっと今外で詳しくは見れてないけどこの手のdfsでTLEになるって
deque使わずにキューしちゃったか、訪れ済みのマスを飛ばしてないとかだよ

あ、すまん、ボケてたわ
最短距離問題からBFSである必要はあるわ、忘れてくれ
dequeをcollectionsからimportして、使えばいいと思うよ
あとnumpyを使わずに実装しなおしてPyPyで提出しなおせば

>>38
なるほどありがとう
丁度その手前の帯域にいるからこれを機に勉強してみるわ

>>25
二分探索だけど、ちょうどこの前話題になった「めぐる式」二分探索って実装方針がバグらせにくくておすすめだよ
ググれば出てくると思う

ARCの配点出たのか
この前みたいに5-7で崖ができるとやりにくいなー

>>42
めぐる式いいんだけどこの前のabc269Eみたいな２分探索だと色々バグらん？

>>44
判定関数をf(n) = (1 n 1 Nと入力したときの応答がn-1のときはtrue、nのときはfalse)みたいな風にすればめぐる式でできない？

初期値はok = N, ng = 0で

昨日コードかいたものだけど
サンクス、numpyをやめてqueをdequeにして
python3.8⇒pypyにしたらTLEにならず通った

しかし、python3.8にしたら通らなかった

なんだかな。。言語によっては通らないみたいなのやめた方がいいんじゃないだろうか。。

言語じゃなくて処理系の違いだからセーフ

計算量の見積りは大事な要素だから遅い言語使う方が悪いということになってる
実際Pythonはpypy あるしRubyはCrystalあるからどうにもならないって人はそんなにいないはず
aclがc++にしかない方が不公平に感じる

君もC++で書いて計算量的に数十倍かかるゴミコードでACしよう

CPythonだとC++の10～30倍ぐらいは遅いから、なんでもかんでも確実にCPythonで通るようにtime limit設定するとC++で非想定の悪い解がバンバン通るようになってゲームが成立しなくなる
一方PyPyは確かJavaと同等かちょっと遅い程度だからそれでほぼ通せるはず
言語ごとにtime limit変えるみたいな話もなくはないけど、ちょっと詳しい人なら遅い言語にC++とかのコンパイル済バイナリ埋め込んで通すみたいなことができてしまうし、現行のルールはなるべくしてなったものだと思うよ

そういえばAGCって年6回開催が目標だったけど、今年まだ2回しかやってないのか
一昔前はARC級が全然なくて黄橙がつらい言ってたけど、こっちは順調なペース
WTFもないし、上級者向けコンテストが枯渇してる

りんご時代より大幅に減ってるんだな
Admin無能すぎでは

admin を片手間の学生に任せてるのがおかしいのでは？

>>47
ジャンプの問題かな？
自分も Python & deque で最初は TLE した。
問題の対象性を利用して (i, j) が確定した時に
合わせて (j, i) の値もセットして訪問済みに
したら Python でも通るようになった。
一方で E は PyPy でないと通らなかったわ。

>>55
なんと。。1/2倍にしたっていうことだよね。確かに正方形だしナイトの動きだと思えばi.jも確定するね
定数倍速くするのは競プロ系だとあまり意味ないと思ってた

もうすぐレギュラーだ
A問題だけでもなんとかして解きたい

競プロ初めて2ヶ月、A問題さえ解ければ茶色になれる

よし、気合入れるぞ
A問題に全精力を注ぐ

緑から水色いくのにARCの問題解くのって効果的かな？それともABCの緑以上の問題解いてた方がいい？

a問題でスパゲッティコード書きまくって結局RE
泣きたいですよ

冷えたなー
Cが曲者だった

ARC2、3完安定してきたと思ったら初めて0完して泣いてる

A,Bも解きやすい感じではなかったね

AGC格に持っていけるかどうかは後ろの問題がどのぐらい面白くて難しいかだと思うけど、自分は判定できない
Fがとにかく難しかったみたいだけど
前の方の問題はAGCで出してもいい感じだと思う

Fじゃない、EとFだ

>>60
寒色がレートを伸ばす効果でいえばABCの練習の方がずっとコスパいいと思うから、当分ABCでいいと思う
ただ、暖色になった後も見据えてるんだったら、ARCもちょっとずつ考えてみるのも悪くないかな
あとARCの練習に関しては解説ACはしない方がいいと個人的には思っている

>>63
ワテは0完ボチボチ出すようになってからARC引退した

というかARCタイプだと黄色近い人でも大事故起こすこと結構あるんだな　問題の傾向的にABCで事故ることは少なそうだけど

ARCのA問題は安定して解けるんだけどそれ以降が不安定過ぎていま黄色だけどそのうち落ちそう

ARC低～中難度も努力すれば安定するぐらいの典型性のはずと思っているけど、似ている問題って他だとどのコンテストなんだろうね

>>42
ありがとうございます。
2分探索なんて簡単だなどと思っていても、実際実装しろと言われると何度実装したことがあっても
時間がかかってしまいます。

実装に時間がかからない方法って重要ですね。

>>67
ありがとうございます！
Atcoder自体、数学パズルが好きでやってて暖色後のことも見据えてるのでちょくちょく解いてみます
解説ACはしない方が良いとは自分で充分熟考して、どうしようもなくなったときだけ解説を見るってことです？

>>73
強い人見てると解けなくても数か月間寝かせて後から解き直すみたいなのを繰り返しているから、そもそも解ける前に解説を読まない方がベターなのかも？
知識不足で解けない場合はかなりのタイムロスになっちゃうけど、知識面はABCの問題をたくさん解くことで十分身につくと思う

この俺が解説見るなんて的な負けん気がある人じゃないと強くなれない説

地頭がない人は自力で解こうとしても時間をドブに捨てるだけ

ABCの問題だとさっさと見て典型吸収したほうがいい場合のほうが多そう

二分探索はめぐる式もいいけど、やっぱり解がありうる範囲の幅に着目するのがいいんじゃないかと思う
これはめぐる式ほど何も考えずできるやり方じゃないけど、少なくともバグらない
幅に着目して、毎回幅が必ず半分以下になるようにすれば、無限ループとかも起こらないし
すべての要素が完全に意識内にあるようにできるから、デバッグも簡単

ARCがレート的に事故になるのって何色コーダーくらいから？
あと、緑（欲言えば水色）はABCのE問題まで完だけでなれるもの？

偏見だけどめぐる式使わない人めぐる式書いたことない

片っ端から解説開くタイプだけど暖色にはなれたから、黄色までなら知識偏重でもいいんじゃないかな
赤は知らん

米田の『プログラミングコンテストの鉄則』を読んでいますが、コードが分かりやすくて、バグもないですね。
さすがレッドコーダーですね。

米田は説明とかコードを大分使い回ししてるからこなれてきてるイメージあるわ

>>79
EどころかDまで早解き(30-40分)繰り返してたら絶対に入水できるよ

正しいアイディアが得られてから、素早く実装するにはどうすればいいのでしょうか？
いつも仮に正しいアイディアが得られたとしても、実装でもたついてしまいます。

まず3000acまで精進しましょう
自然と実装が早くなります

>>86
ありがとうございます。気が遠くなりますが、3000までいかなくても、次第に速くはなっていくと考えてがんばります。

>>79
これを見るとE安定（1500pt安定）の人なら水中位は固い
いろいろ噛み合えば青タッチもできるレベルだと思うね
このグラフは他の色についても分析できるから便利
https://twitter.com/kiri8128/status/1561356750355570689
https://twitter.com/kiri8128/status/1576256376518897665
https://twitter.com/kiri8128/status/1566074062786658307
https://twitter.com/5chan_nel (5ch newer account)

AC数800台で黄コーダーになった中学生

実装の速さは紙上デバッグを細部まで終わらせて迷いなく書くことだと思う

実装を速くするコツは２つあると考えてる。
１　思考の手間を省く。
　競プロでは毎回全く違うプログラムってことはあんまりなくて、DFSとか1次元DPとか累積和とか毎回書き方が同じ部品というのは結構ある。
　こういう部品に対しては、事前に書き方を決めておくことで、その部分はもう考えずに書けるようになる。
２　隅々まで理解する。
　複雑な問題を解くとき、なんとなくわかった状態で実装を始めている人は多いと思う。気持ちはわかるし、簡単な問題ならそれでいいと思う。
　でも、実装と深い思考は両立するのが難しい。複雑な思考が必要な問題では、先に最後まで（何行目に何を書くかまで）考えておいた方が速い。

chokudaiが同じ実力でも1年間で50程度レートが下がるみたいな感じの調査を見たって言ってるけど、ソースは何だろう
個人的には大体そんなもんな気がする

https://twitter.com/not_522/status/1580130152482099200?t=aj8v0JeHSojee_MKdb-TTw&s=19
https://twitter.com/5chan_nel (5ch newer account)

>>93
ありがとう
予想するに、logit([AよりBの方が難しく感じる確率]) = β_0 + β_1 [problems上のdifficultyの差] + β_2 [出題時点の差（単位は年）]としてβ_2/β_1 = 50だった的な感じかな
こういう回帰係数って素朴に割り算していいのかわからないけど
[problems上のdifficultyの差]と[出題時点の差]って独立っぽいから多重共線性とかはなさそう

>>90-91
ついつい、あせってアイディアが整理されていなくても書き始めてしまうんですよね。。。

『離散凸解析と最適化アルゴリズム』という本の第1章を読んだのですが、このような
理論的な本は競技プログラミングに役に立つことがありますか？

問題を解くばかりでは飛躍的な上達はなかなか難しいのではないかという気もします。

>>95
atcoderは大人のsapixなので役に立たないです

理論的な本は競技プログラミングに役に立つことがあります

>>95
mas 氏が離散凸を題材に作問されていたね。arc130_f。

凡人は数学の難しい話が役に立つところまでレートを伸ばせない

ABCで黄色以上でた問題は存在しないも同然じゃからのぉ
実務的には調べながら1問に3時間くらいかけて解ければ十分みたいな感じかと

その離散凸解析の本は理論系の中でもかなり競プロに役立つ方の本な気がする
けど、知識をつけて飛躍的に伸びるのはAtCoderの中でもABCで、そのABCで出てくるぐらいの知識なら特別な勉強をしなくても、問題解いて蟻本あたり読んでいれば身につくものという印象（Exは除く）
だから理論系の勉強がコスパがよいかというと微妙
ただ、競プロ抜きにしてもアルゴリズムの勉強は面白い部分があると思うし、そもそも競プロとは独立して価値があるものなので勉強して損はないんじゃないかなと思う

要約すると、理論的な本は競技プログラミングに役に立つことがあります

というのはまあ冗談で、少なくともレート2000以下とかならそんなのいらん
鉄則本や蟻本に習熟して、AtCoderを練習しまくて遭遇した知らなかったアルゴリズムを覚えればいいだけ
ヘタに大学生向けの参考書なんか読むより大学受験レベルの整数問題を解く練習したほうがいいくらい

こどふぉのdiv4難易度の上限がatcoderの500点問題くらいだから初心者にとっては早解きの練習になってありがたい

理論は楽しいから、競プロを手段化することで競プロへのモチベになる

今日も頑張るぞ
今日、ちゃんとCまでは解ければ茶色にはなれる

誤差の問題が出るから整数型でなんとかしよう

こういう重いのやるなら1問だけやれよ、ビギナーで1問70行とか無いわ

AtCoder を始めて10回ぐらい経ちましたが, A問題しか解けない状態が続いてます.
A：簡単
B：いくつかWA→解決できずに終了
といった感じです.
原因はコードを見てWAになる理由（そうなるケース）を見つけられないことだと思うのですが,
みなさんどのように対処されているのでしょうか

Aしか解けない人の気持ちはわからん
なんか計算量とか前提知識が足りてなさすぎる気がするから、AtCodeer本とか読んでみたら？
競プロは問題に書かれたことをシミュレーションするコードを書くコンテストじゃなくて、たくさんのアルゴリズム知識を駆使したうえでの数学のコンテストだよ

唯一、A問題だけはシミュレーションすれば解けるから、競プロ用の知識が足りてないのかなと思った

B問題に関しては計算量解析もそんなに問われないから、計算量の知識というよりはプログラミングコードを書くところとか、問題文の状況を考える基礎力とかかなあ
あんまいいアドバイスできないけど練習あるのみだよ、ABC-Bをたくさんやるのがいいと思う
競プロはよく役に立たないと言われているけど、ABCのC問題までは本当にプログラミングの基礎力と関わってそうだから、できないのなら練習して損はないと思うよ

永続データ構造ってどの色くらいから常識になる？というかどこからそういう知識を身につけてるんだ
あの問題文を読んで木構造を作るぞって気持ちに初見でなれるものなのかな

まあ今日のBはそこそこ解きにくい方だったと思う

おれも永続データ構造は全然知らんけど、木でいけそうだなということにはすぐ気づけたよ

Dまでは早解き安定して出来るけどEから不安定になるから水色以上埋めていくしかないか

>>113
ネットで競プロっぽいこと検索してたら結構出てくる
はまやんさんのブログとかにまとまってるやつオススメ
あれは別に木構造作ろうというよりは、

ページにAのデータ全部コピーするとオーバーヘッドやばい
↓
ポインタアクセスで処理したい
↓
どうせ末尾しか毎回アクセスしないし、linked listっぽくすればよさそう
↓
というか、データ自体は時系列テーブル上に保存しとけばよくないか？

みたいな感じで思いつくのが自然な気がする

テストケースの公開って普段はコンテスト後何日ぐらいで行われるんですか？

>>117
思考過程が分かりやすくて助かるわ　ありがとう

>>118
そんなにすぐじゃないイメージ、今のところ2～3週間遅れぐらい？
https://www.dropbox.com/sh/nx3tnilzqz7df8a/AAAYlTq2tiEHl5hsESw6-yfLa?dl=0
そもそも作業者のAtCoder運営自体がテストケースを直接見てデバッグってスタイルをそんなに好きじゃなさそうだから作業モチベも低そう
ここに貼ってくれれば誰かしらが見て指摘したりはできると思うけど

Ex、問題文がもろにStern Brocot木で笑ったな
Exをガチ目に解きに来る人はみんな知ってるだろ

Stern Brocot木の必要部分だけを取ってきた木の辺の数がf(T)か？
知識一発芸ならもっとたくさんの人が解いてるだろうし、ここからもいろいろ考えなきゃダメそうだな

辺というか頂点か

A問題で初歩的なループや再帰を解禁したの
整数パズルみたいなのよりええな

競プロっぽい問題得意じゃない人からしたら整数パズルより愚直ループのが解きやすいし、整数パズルできるやつからしたらその辺の文法覚えるのは簡単だろうしで、最近のAの難易度からするとループ縛りは実情にあってなかった

『競技プログラミングの鉄則』という本の問題A19のナップザック問題について質問です。
アマゾンのレビューでも指摘がありますが、dp[i][j]に品物1からiまでの中から合計重量が
ぴったりjになるという条件を満たすナップザックへの入れ方のうち合計価値が最大になる
ときの合計価値を入れています。

普通に考えると、dp[i][j]には部分問題の答えを入れると思います。
つまり、品物1からiの中から合計重量がj以下になるという条件を満たすナップザックへの
入れ方のうち合計価値が最大になるときの合計価値を入れるのが普通だと思います。

これはなぜですか？

・計算量的にも実装の複雑さもほとんど変わらない(最後に全体maxをとるかどうかは微々たる差)
・重量合計がちょうどwになるときの最大価値の方が、重量合計がw以下になるときの最大価値よりも得られる情報が多い
・形式的冪級数で定式化したとき少しだけきれい

鉄則本持っとらんけど、このあたりの理由か？
二番目が多分重要で、競プロではちょうどwで書く人の方が多い気がするぞ

昨日初めてコンテストに挑戦しましたが、2問しか正解できませんでした
C++だけじゃなく、もう1個文字列操作用の言語を使った方が良いような気がしました
Perlが理想なのですが、VSCODEでのデバッグ環境の構築方法がわかりません

Perlは遅すぎてc問題でも解けない可能性あるからやめた方がいい
スクリプト言語ならPythonが無難

Rust使えば？

他の言語覚えるより、C++でどうやるか、だけを準備したほうが確実に良いよ

std::stringの機能で競プロのニーズ的には十分な気がするけど

プロは道具にこだわる。

perlってpythonより遅いんですね
とりあえずC++でコンテストに慣れて、それからpythonも使おうと思います

ARC

A問題とけたぞおお

C問題、方針は良かったのにgrundy数の計算を永遠にバグらせてて死んだ

普段と比べると難しい印象はないけど、ARCらしく素直に解けない問題が多かった気がする

無事茶色達成
しかし将棋ウォーズで言えば1級レベルなのか
もっと頑張ります

コドフォdiv. 1も不足してるしAGCも不足してるな
div. 2とかABCレベルが枯渇することはないだろうが、今後高レベル帯では問題を作りやすい実装ゲー、高度知識ゲーが増えていくんだろうか
あるいは新しい分野が開拓されるか

>>139
おめ

>>141

途中送信してしもうた
さんくすうう

デジタル庁が開発エンジニアを募集　任期1年の非常勤　
http://2chb.net/r/news/1666079673/
年収最大1千数百万円　賞与なし

必須スキル
・Webアプリケーション開発経験５年以上
・TypeScript、React、Vue、GitHub等を用いた開発経験２年以上
・DevOpsの設計・開発、アジャイル開発経験２年以上
・C#によるWebバックエンドアプリケーション（MVC、Web API、Entity Framework）開発経験３年以上
・パブリッククラウドサービス（Azure、AWS、GCPなど）でホストするシステムの開発経験２年以上

・データベース設計経験２年以上
・Web・モバイル技術、及び大規模サービスの運用に対する確かな理解と技術を深く掘り下げる能力
・現在においても、開発・実装業務に直接携わっていること。
・複雑で不慣れな実装、及び開発言語にも素早く適応できる柔軟性
・英語で書かれた技術文書を理解できる語学力

場合の数を998244353で割った余りを求める能力だけで雇って欲しい

省庁の予算とかも32ビットで収まらないから998244353の余りを使うようにしよう
商が違っても余りが一致してればまあ合ってるやろ

998244353だけだと不安だから1000000007で割った余りも保持しとこう

エドモンズの花アルゴリズムを使わないと解けない問題はありますか？

あるが一般的なコンテストじゃまず出ない

>>149
ありがとうございました。

ICPC は一般的ではなかった？

スニペットって登録すべき？　今まではライブラリからコピペしてたんだけど

そんなんなんでもよくね
小手先の効率化よりも、考察力を鍛えよう

するだけなら別に手間じゃないしやっとけばいいと思うぞ
決定的に強くなるわけじゃないけどそれで拾えるレートもあるだろう

離散フーリエ変換を知った時は感動した
競プロ界隈じゃ常識かもしれないけど

>>152
Unionfind入れとくとかなり便利よ

FFTは今でこそ半ば常識だけど、蟻本が本の中で扱わないぐらいのトピックだった
形式的べき級数の流行やACLで普及したのかな？
フーリエ変換なんて周波数成分とってきたり微分方程式解いたりするときに使うものという印象だったから、計算量削減に活用できるのにはびっくり

形式的べき級数が流行しているというのは本当ですか？
どうしてですか？
母関数とかと関係がありますか？

FFTについてはCLRSの第3版に分かりやすく書いてあって、読んだのですが、すごいなと思いました。
フーリエ変換とか難しい解析学の話を全く知らなくても大丈夫ですよね。

Nyaan回のABCが形式的冪級数講座と言われる位には出題されてるだろ
立式も高速化も機械的にできて考察部分を減らせるならそりゃ使うわな

形式的べき級数がABCで想定解法の1番目にくるようなことはないと思うし、便利だということに気づけない人も多そう

Nyaan回って何ですか？

形式的べき級数は、Liuの『組合せ数学入門I』とかKnuthの『Concrete Mathematics』に
書いてありますね。

競技プログラミングにどのように役立つのか分かりませんが。

Nyaan回というのはNyaanさんという人がwriterをやっているコンテストのこと
特にABCでは、Exに形式的べき級数の発展的な技法（ラグランジュの反転公式の利用とか）が解法に来ることがあり、解説も丁寧に書かれていてかなり勉強になる

>>164
ありがとうございました。

形式的べき級数の利用法として典型的なのは、数え上げのDP遷移を畳み込みとみなして高速化することかな
FFT使ってO(N^2)をO(NlogN)にする
maspyさんのブログの「数え上げとの対応付け」の記事とかが分かりやすい
同じ形の遷移をＱ回するときとかは、周波数領域表現の方で各点を累乗すればいいとか、DP遷移の「逆変換」を考えたいときがあって、それは逆関数に対応するから機械的な代数学的操作で導出できるようになったり、恩恵はいろいろ

解析学の知識がなきゃ理解できないという部分はなさそう
形式的べき級数の微分とかオイラーの等式とか、基礎的な知識は要求されるけど、高校数学ちゃんとやってきた人なら適宜ググればどうにかなるレベル

形式的べき級数を使って解く問題ですが、なんかアルゴリズムの問題としては特殊すぎませんか？

例えば、プログラミングコンテストに、整数論的なアルゴリズムを使って解くような問題が出たとしたら、
場違いな感じがしますが、それと同じような感じがします。

情報科学の基礎や離散数学的なアルゴリズムが守備範囲のコンテストだから特殊とは思わないかな
学究的な観点ではそれらも十分アルゴリズムのメジャー領域かと

競技プログラミングという名前に引っ張られすぎ
整数論とかも全然メインストリートやで

mod 素数数え上げのときモジュラ逆数を O(logP) で求めるのは整数論的アルゴリズム？だけどそれも場違いだと思ってる？

競プロ全体でもそこそこ整数論を使うけど、AtCoderだと特に出題傾向が高いよな
実装が重い有名アルゴリズムは出さないって公式で宣言してるから、結果的に考察偏重にしようと数学ばっかりになってる

趣味が合わないならコドフォに移るのもあり

学生時代はこんなもんいつ使うんだよｗ
と思ってたのに、仕事でFFT実装する羽目になった
使い道は確かに素晴らしいものの

FFTってライブラリに突っ込むだけじゃないの・・・・

可変長のビット列を扱うにはどうすればいいのでしょうか？

キーエンス産の問題難しいイメージあるから不安

>>176
vector<bool>を使いたいという話？

問題提供キーエンスなのか
社内にこういうのができる人員を抱えてるのはええな

>>178
それだと出力がtrue/falseになってしまうので、01で扱えると嬉しいです

>>180
vectorのboolだけ特殊化されてるのよ

確かキーエンスは、不可能な問題を解決する会社だから、
バリバリ理系のイメージある

Google の面接の難問、
無限格子の桂馬の位置の電気抵抗を求めよとか

キーエンスは営業が強くて徹底的に収益をプランニングするB2Bボッタクリ企業のイメージが・・・

一部の問題提供ってどうせ前半だからあんま関係ないな
前は典型をそのまま出してて噴飯ものだったわ

競プロってなんか意味あるの？
よく知らんけど実務とも学問とも違うだろあれ

パズルゲームだね
こういうパズルゲームを好きな人が競プロをきっかけに興味関心の幅を広げて情報科学の勉強につながることもあるから、役に立たないとは思わないけど、別に好きじゃないんならやらなくてもいいと思う

意味あるからGoogleなんて20年近くも前からコンテストやり続けてるじゃん

Dですが、部分和問題だと気づいたのですが、実装まで行きませんでした。

F、G辺りに置かれてても問題文の主旨自体は簡潔なことって結構あるんだね
普段Eくらいまでしか解けないからそこら辺の問題は歯が立たないのかなって思い込んでスルーしがちだったけど軽いアプローチくらいなら思いつくしもう少し上のレベルの問題も取り組んでいくべきか

ABCだったらExですら知識一発芸が結構出るから、後ろの問題だから考察難しいって感じでもないよ

なるほど
ABCとARCAGCで傾向結構違うのは感じてたけどABC産なら典型寄りだろうし解説見るハードル下げても良さそうな感じか

Fとか脳死で最適化ライブラリにぶっこんで解けるような問題出してほしい

D解かれすぎな気が
部分和とはいえ実装バグりやすいでしょこれ

ナップサックDPはABC中盤に出すぎてちょっとした変形入れてもみんな対応してくるな

>>191
ABCは1問30分ぐらい考えて考察生えなきゃもう解説見ていいレベルだと思うわ
ABCクラスの問題ならAtCoderでもCodeForcesでも無限にコンテストで新問が提供されるし、考える練習はコンテストでやればいい

D問題とけんかった・・・
XとYの行ける位置を全部セットに詰め込んで計算してたけど
4つほど不正解が出る

あと関係なさそうだけど
2 2 1
2 1
が入力としたら答えはNoだよね
同じ位置じゃ線分にならんし、90度も無理あるし

Ex解説見てるけどNimberなんてものがあるのか、知らなかった
というか辞書順比較とロリハって勝手に相性が悪いと思ってたけど、LCP求めて一文字分比較するだけだからロリハでも普通に高速でできるね

>>196
Noだね

LCP求める方法はいろいろあるけど、ロリハにぶたんは直感的にわかりやすくて便利

>>196
どういうこと？Yesでは？

Nimberとかちょっと前に流行った概念Exに出がちだけど次出んのいつやねんという気持ちに

>>200
あ、すまん
A1,A2,A3
x y
の並びかと思った（そんな形の入力ありえんのに）
普通にYesじゃんこれ

あ、、、自分のミスだった
最後のA[N]でジャスト(x,y)にたどり着くのか
勝手に最後だけ距離が未定義だと思ってた
すみませんでした！

>>201
こどふぉで役に立つかも精神で・・・
そういえば、ARCはDEとかで割と高度典型が出現することあるけど、AGC後半ってどのぐらい知識が役に立つ問題出るんだろうね
AGCはアドホックの祭典という評判だけはずっと聞いているが、後ろの問題は手をつけていないので実態は知らない

昨日のC問題が全然わからん😭

親子関係を図で書いていったら何すればいいか見通しがいいと思うよ

日本語が難しかったね
ナンバリングの法則がちょっとイメージしにくかったかも

こどふぉdiv 1だ
少ないと思ったら急にたくさん生えてきた

今日のこどふぉ2連続間隔15分しかないのおかしい　

昨日のABCのD問題、
なんかランタイムエラーが5つ程。
C++でもPythonでも同じ。

配列のサイズを入力した数字の合計(プラスα)から計算した値から定数値に変えたらAC

添え字のチェックして処理を飛ばしてもWAにはならずRE

どんなエラーになったか確認したくて
テストケース欲しい…
けど、社長はテストケース公開消極派なのね。
自分でテストケース作るのは難しい

今だってABCの範囲だと意味があるのは5問目程度までだろうから、せめてサンプル強くして難易度下げるべき

いうて自分でテスト書いて検証する力って、なんなら本旨の算数パズルよりもずっと実務寄りの能力な気がするが

>>210
とりあえず、限界値っぽいのを入れてみたら？

1000 -10000 -10000
10 10 10 10 10 10 10 10・・・1000個分

茶色になったばっかの新人コーダーだが、
土曜日C問題まで解いたけど若干レート下がった
時間一杯までやってしまったこともあるけど、C問題まで解いただけじゃ緑までいけないのか

だいたいcで茶、dで緑、eで水やね

安定して4完できるぐらいじゃないと緑は無理じゃないかな
緑の過去問を解く練習しよう

なんか勘違いしてね？

chokudai視点だとARCもやっぱり典型ゲーなのか

chokudaiに限らず、銅冠以上が解けてない問題を典型って言っちゃうのは、典型とは一体っていう感じだけど

AVL木とか赤黒木辺りの仕組みをちゃんと理解してないと解けない問題ってある？
こういうのってやっぱり競プロ文脈だと自力で実装する必要ないのかな

avl木を題材にした問題は見たことあるけど仕組みの理解が必要かは疑問
せいぜい問題設定の理解が楽になる程度じゃないかなあ

その場でちゃちゃっと機能付け足せるくらい手に馴染んだ平衡二分木持ってると得するっつーか楽できる場面は結構ある

確か赤黒木は、木の再構成を頻繁に行わないように、
木の高さが2倍になった時に初めて、再構成するのでしょ？

確か、Linux のタスク管理などに使われているのか？

この2倍と言うのが、解く問題に影響するかどうか

「ちゃんと理解してないと」って言われても理解の深さにも差があるからなあ・・・
https://judge.yosupo.jp/problem/dynamic_sequence_range_affine_range_sum
こういう問題をサラっと解けるならおれはそこそこ理解してると思っちゃうけど、ライブラリ叩くだけだからこんなんじゃ理解したなんて言えない、と判断する人もいると思う

フェニック木やセグ木以外で、平衡二分木の実装まで要求してしまうとそこそこ重いし、深い理解を要求する問題にはあんまり遭遇しなそう
逆にいうと、セグ木でだいたいなんとかなってしまうともいえる

平衡二分探索木のmerge-split系の操作が難しめの問題で役に立つみたいなのたまに見るけど、その辺り詳しくない
まあ、自作平衡二分探索木があると、std::setにない機能を追加できたり何かと捗るので自分で実装するのも悪くないと思うよ
順位取得とかね
座圧セグ木でもできることが多いけど

オフライン性活かした実装ってダルいからそれスキップできるだけでも強い
永続系も似た用途で使えることあるね

???「赤にいかないうちは、典型も解けていないという証拠なのでどんな問題がでても文句を言わずに解きましょう」

bit系のオリジナルライブラリ作ったけどstdの方が16倍くらい早くて泣いた

charでも使ってんのか

ハードウェアとかコンパイラとか全然知らないのですが、

vector<vector<int>> dp(N + 1, vector<int>(N + 1, 0));

とか初期値を指定して初期化する場合、初期化の処理にΘ(N^2)回の計算量が必要になりますか？

なる

>>230
ありがとうございました。

でも不思議です。
今まで
>>229
のようなコードを例えば、O(n * log(n))の計算量が求められる問題で使用してきましたが、
ちゃんとパスしてきたと思います。
>>229
のようなコードがあるとそれだけでO(n^2)以上の計算量が必要ですよね？
n^2の係数が極端に小さいんですか？

いずれにしても理論的にはO(n^2)以上ということになりますよね？

そう、O(n^2)だよ

当然だけど通るかどうかはNの値による
下のコードをN = 100000で、AtCoderのコードテストやってみたら2453msとかになったから、このサイズだとだいたいダメだろう

int main() {
int N = 100000;
vector<vector<int>> dp(N + 1, vector<int>(N + 1, 0));
cout << dp[0][0] << endl;
}

すまん、2453msじゃない
終了コード9で終わってたからただのタイムアウトだった
まあダメってことだ

>>233-234
ありがとうございました。
今度から意識して初期化するようにしてみます。

vector上の数字を全部0にセットする処理はかなり定数倍軽そうだし、思ったよりも通りそうではある
もちろん無意味なオーバーヘッドを生んでるだけなのでやめた方がいいけど

メモリをN^2使ったら駄目だろ

>>234
タイムアウトではなくメモリの方だね
コードテストだと10秒待ってくれる

>>236
何と比較するかではあるけどメモリ確保は一般には定数倍重い部類の操作だと思う

ああ、たしかにめっちゃメモリ食うやん

でもN^2のメモリが必要な問題もありますよね。
迷路の問題とか。

具体的な問題あげてみなよ

当たり前だけどNの大きさによるので
Nが3000以下とかならN^2のメモリ確保でもどうにかなるし、100000なら無理というだけ

O(N^2)って"高々"N^2の定数倍で抑えられる、だから計算量がNでもlogNでもO(N^2)だし、今回の文脈で使われると典型的な誤用で気持ち悪く見えるな

じゃあΩ(N^2)使ってくか

こことかTwitterとかでやりとりする分には大抵オーダー記法とっぱらっちゃっても伝わるな
誤用よりマシな気がする

>>229,240 を見る限り制約に全く触れられてないので、計算量についてなにか勘違いしていそう

N^2がTLEするようなNの大きさならN^2のサイズの領域確保したらだいたいMLE

基本的にTLEにならないコード書けば自然とMLEも回避できると思ってる

C++のpriority_queueについて質問です。

優先度付きキューに入っているある要素の優先度を変更する方法ってありますか？

高速な方法は、ない

>>250
自分で作るしかないということですか。
ありがとうございました。

古い優先度の要素は残したまま新しい優先度の要素を突っ込んで、
取り出したときに優先度が古ければ無視

で大体なんとかなる印象

ダイクストラのやつね

Fibonacci heapは優先度を変えられるからダイクストラの計算量が落ちるってことだったのか

N^2の計算ができるって、江戸時代からしたらものすごいことなんだけど人類はまだそれでも飽き足らないからすごいことだよね

そこからさらに、並列処理可能にして一気に処理したり
根底から覆す量子コンピュータとか

>>252-254
ありがとうございました。

>>252
なるほど、それでも全く問題ないですね。
気持ち的には、ちょっと気持ちが悪いですが。

自作するとして、元の要素がどれか特定する部分が遅いんだよな
よくある実装だとunordered_map使うから定数倍が重い
acl::maxflowのadd_edgeのように、要素を追加したら後で優先度を変更する際の引換券を返すのが良いのか？

E問題。。。。
t-1回目にどのマスにいるかの確率（というか回数）を出して
t回目にどのマスにいるかを算出すればできるってことはわかってるのに時間が足りない。。

しかしこの考え方ってあってるのかな
dp的にやると100万×動けるマス10マスで1000万だからこのままやっても計算量的にアウトだったんだろうか

実装重いのをCに置くのはほんとやめて

公式解説もNMKだったから一応あってるのか

今回の結果
https://imgur.com/a/C2RD1bF
この間茶色になったばっかりだが、少しでも緑に近づけてることを願う

>>259
あってるぞ、O(NMK)になるからな

https://imgur.com/c9Dco1P
ええ。。
Cを一回間違えてしまったとはいえ4完全したのにマイナス6かよ、、、緑むりげーだろ

>>262
公式見るとあっていたみたいだね。
ただ、低速な言語だと間に合わないで前計算が必要って書いてあったけド、このあたりまだ理解できていないので分数のmodについてちゃんと理解しておくようにする

Eは解説とほぼ同じように作ったのに1時間最後まで合わなかった…むなしい…

でもE問題が射程範囲に入ったのはちょっと嬉しかった。
C問題がかなり苦戦して、どっち方向に直交ベクトルをかけるかっていう部分に関してかなり苦労してしまった。
結局2パターンについてべた書きしてしまった

D問題はメモ化再帰して一瞬だった。
C飛ばしてEに挑戦してればレーティング上がったのかな

>>263
それ前回のパフォじゃん
さすがに今回はレートあがるだろ

>>263
これに表示されてるは前回の結果だよ　コンテスト名を見ればわかる
今回も含めてコンテストの結果は数時間後に出る事が多いから終わってすぐには反映されないよ

>>267-268
ほんまやあああああああああ
サンクス
しかしC問題で一回間違えた(直交方向に足した値が範囲内でおさまってるかの処理を書き忘れた）ので少しそれが心配。。

あとそのレートで4完してるなら今回でレートは100くらい上がるんじゃない？

ac-predictor入れなよ

レートの更新が来てるわね

https://imgur.com/a/5ACK8kd
ほんまやああああああ
緑色がみえてきたあああああああ

E問題まで確実にとけるように頑張りたい

Fって精進すればDP使おうってすぐ見抜けるようになるものなん？

うん

dpのiとjのループの順番を逆にしたら通った…

Fはいつもより典型度高めかな
ナップサックDPをするついでに、選ぶときの遷移と選ばないときの遷移でちょっと処理を変えるみたいなのは結構見る

from functools import lru_cache
pythonってメモ化再帰再帰が標準実装されてるんだ
知らなかった・・
どうやって制御してるんだって感じだが、やっぱり標準モジュール？ってすごいな

実際どうやってんのか知らないけど、メモ化再帰の実装はpythonのデコレータと相性いいと思う

計算時間の見積もりだけど、ラフに計算して10^8以下で平均的な定数倍の重さだったら2 secで間に合うし、普通に想定解になりうると思うよ

簡単にいうと、デコレータで内部的にdictを作って、引数と戻り値つっこんでるだけでしょ
dictより自分でlistを使ってメモ化したほうが高速だし、別にlru_cacheは覚えなくてもいい気がするな

標準実装部分って一度Cでコンパイルされてるから自前実装より速いと思っていたんだけどどうなんだろう。
あとdictってハッシュだから速いと思ってたんだけどlistの方が早いっていうことってあるの？
インデックスへのアクセスがn(1)だとしても再帰関数の場合はインデックスもばらばらだと思ったんだけど

mod逆元なんて意味不明な計算させんでも、誤差を認めた小数でええやん

Pythonの標準実装は、Cで高速化されて優秀なときと生Pythonで微妙な実装が施されていてひどいときの両方がある印象だね
PyPyに至っては最適化の仕方がよくわからないから実際に試すしかない

>>282
ハッシュ化のオーバーヘッドがあるから、とりうる引数の値が小さいんならlistの方が定数倍速いこともありうる
今回はそもそもlistでは対応できないはず

Pythonを使ってた時は自前で書いた二分探索だと通らなくてそこを二分探索のライブラリに置き換えたら余裕を持って通ったことがあったからCによる高速化の恩恵は大きそう

>>283
ターンが進むごとに指数的に減衰していきそうな行動パターンまでちゃんと追跡できてるかを問いたいとすると、mod逆元の方がいいと思う
まあ、小数解答方式でそういうタイプの枝刈りで通せる人はそもそも今回の問題だと問題なく想定解にたどり着ける気がするけど

Ex、ぱっと見Cartesian木で貪欲でいけるんじゃないかと思ってしまうが、そんな単純な問題じゃないっぽい

んー、F難しくはなかった
毎回変なところで失敗するからたどり着けないけど

Eまでは安定するようになってきたけどFが中々安定しない
今回のFは素直なDPで良いって聞いたらすぐだったのに

Cで正方形の定義書いてほしいと思うのは甘え？

GもExも見方によってはLPだし後ろの方はLP回だったのかも

長さが同じっていうだけで判定すると菱形も拾ってしまうよね

直行条件って内積知らないと厳しいと思うけど、やっぱり数学の知識が必要なんだと思った

>>290
部分和をちょうどxにするときに何かを最適化する問題って地味に取れる手立てが少なくて（今回のGみたいに例外的に連続緩和できるとかならともかく）、ABCだったらナップサックDPを出発点に考えても大体外れないと思う

数学から離れて長かったり数学にあんま縁がない人だと、辺の長さが全部等しい四角形が正方形であることの必要十分条件だと勘違いするのはめちゃくちゃありそう

ARCなくね？
AGCない代わりに最近たくさんあるなと思ってたけど、こっちも放出されつくした？

問題の枯渇で純粋なアドホック考察ゲー作るのが難しくなってきて破綻しつつあるから、アルゴの方はABCの延長線上みたいなゆるふわコンテンツがメインになり、AHCに賭けてるんじゃないかとか邪推してしまうな

短期AHC久しぶりだ

2週間前から始めていますが、AtCoderのBeginnerさえ1問しか解けません
復習はしていますが、全然スキルが上がった感じがしません(´；ω；｀)

とりあえず鉄則本やっておけばいいんじゃないかな

Bが解けないとすると、使用言語の文法みたいな基礎事項から勉強しながらやった方がいいかも
C++使いならAPG4bとか
Python使い用のも探せばあると思う

ARCは今年たくさんやったからいいとして、AGCは本当に生えてこなくなったね

AGC少なすぎて赤以上のレートはあまり参考にならんのよね…

頑張って高速化しただけで終わった

出力しないと次の入力を受け取れないシステムになってることを途中から忘れてたの本当にしょうもないミスだ

AHCはみんながガチすぎないことによって、昔のアルゴにあったっぽい良さが保持されている気がする

本当にちょっとした改善（ただし自分では思いつけない）でスコア爆上がりすることをコンテスト後に知るとめちゃくちゃ悔しい

まずは“本当にちょっとした”とかいう歪んだ認知を直すところからやね

短期コンだと本当にちょっとした改善でスコア爆上がりすることが多すぎて辛い
なんで本番中は入力を虚空に放り投げてることに気付けなかったんだと後悔してる

>>300
ありがとうございます、鉄則本頑張ります

問題に付いてるサンプルケースでは正解なのに、ソースコード提出すると他のテストケースで不正解となるんです

おそらくどこかでオーバーフローしていることが原因です

過去のコンテストのテストケースって全部どこかにアップロードされているんでしょうか？

https://atcoder.jp/posts/20
ないものも多いですしテストケースを見ることは推奨されていません
自力でテストケースを作って頑張る方法を身につけるのがいい
参考：https://betrue12.hateblo.jp/entry/2019/09/07/171628

オーバーフローならC++(gcc)だったら-fsanitize=undefinedで見つかるかも

オーバーフローしていることが原因とまで当たりついてるなら、一ヶ所ずつ型変えて提出してみたら

オーバーフローが原因だと分かってるんならもうACはすぐそこじゃないか
頑張れ

>>312
>>313
貴重な情報ありがとうございます

>>314
>>315
unsigned longでもオーバーフローしてしまいます

実はオーバーフローしてないんじゃない？

まさか余りをとる時に負になるケースを考慮していないとか？
ABC-DEFとか

(-m) % n がマイナスの余りになるという仕様になっているのはなぜですか？
((-m) % n) + n とするのが面倒です。

>>299,310,311 が同一人物だとしたら、そのレベルならあらゆるミスをしそうだし、原因はなんともかんとも
愚直で応えるコードを書いてもバグらせそうだし、他の人がACしたコードと比べてみるのがいいんじゃないか・・・

WAの原因なんてオーバーフロー以外にも無数にあるぞ
バグ、mod取り忘れ、コーナーケース、そもそも解法が間違ってる、等

>>319
C++の整数型は(m/n)*n + m%n == mが成り立つことになっていて、除算は0方向に丸めることが規定されているからです（C++11以降）
modintがおすすめ

標準的な型の演算規則ぐらいは身に染み付いてた方が良いと思うので、modintなしで地雷踏み尽くして覚えていくのもありではある

競プロって意味ないって言われてるけどどうなんだろうね？俺は楽しいからやってるけど

確かにこのアルゴリズムを直接的に実務で使うことはあまりないかもしれないけど、バグの発見とかは競プロで鍛えると速くなる気はしてる

まあ高校の数学と同程度には役に立つよ

ようするにめったに使わないし、そんな知識を活用せずに大成功してるひとのほうが多いくらい

脳トレが出来るオンラインゲームみたいなもんだし実生活に役立ったら美味しいくらいの気持ちで良さそう

ABCのD問題までスムーズに解けたらあとは趣味程度に思った方がいいと思うよ
逆にD問題までスムーズに通せるようになることで、ある言語で手早くスクラッチする力や計算量を意識する力はかなり身につくと思う

あと、アルゴリズムに興味を持つきっかけになるかな
スタックがLIFOでキューがFIFOだとか基礎教養でやったとき、正直つまらない暗記対象としか思ってなかったけど、ちゃんと意味があって重要だということが分かった
SQLでB木使うとかも競プロやらなかったら意識しなかっただろうし
ハマる人とっては情報科学の入口として優秀じゃないかな、競プロと相性悪い人はストレートに勉強した方がいいんだろうけど

>>328
おれは先に業務してから競プロやってるけど、RDBでB木使うとかは最初からめっちゃ意識してたぞ
インデックス効かないクエリを実行すると遅すぎてすぐ障害になるからな
そんでRDBだけでは実装が難しすぎる機能とかあったりするから、他のデータ構造も学ぶようになった

競プロはほとんどのひとはすぐ挫折して継続できないみたいだし、どっちのほうが良いかと言うと難しい

>>329
そこは人や環境によるところかな
自分はデータ分析職やってるけど、エンジニア職ではないせいか、ちゃんと理解してる人、意識してる人が少ない
役に立つのに、低レイヤーに触れる文化がないから、自発的にアルゴ勉強する発想が出にくい
あと競プロに相性いいのは、情報系に向いてる人というよりも、元々中受算数か高校数学、高校物理みたいなのがめちゃくちゃ好きとか数オリ経験者みたいなタイプだろうね

割と役に立つこと多いけど数論だけは未だに活用できた試しがない

純粋な離散数学や暗号理論も守備範囲にいれたいとすると、数論みたいな普通のエンジニアリングやデータ解析の範疇じゃ役立てるのが難しい内容も扱いうる
今の競プロの源流のICPCや情オリも、そもそもアカデミックな動機付けでやってるものだし

競プロ初心者でコーダーの俺
こっちの業務の役には立たないと思ってる
情報処理の資格を無駄に取得して給料アップ程度

競プロ面では、素直に実装してTLE連発
こんなガチガチに実装したら仕様変更に耐えられないだろうな
と思いながらAC取りにいく

話題乗り遅れたけど、rustなら x.rem_euclid(m) で余りが常に正になる
みんなrust使おう

ライブラリってデータ構造やアルゴリズムばかり気にしがちだけども細々としたutil系もあると便利よね

>>326
俺も同じような感じだわ。

脳トレで思ったんだけど、脳の老化防止に競技プログラミング!!
とか言って高齢者にプログラム教えたら面白いかもな。
大半はダメポだろうけど、何百人に一人は才能開花しそう。

util系って例えばどういうの？

新しいFizzBazz発見した
面白いように誰もコード書けない

回答見せるとみんな悔しそうな顔をするｗ

はいはい、すごいねー

面接落ちまくりなので、緑で役に立つ宣伝文句教えてほしいわ（´・ω…:.;::..

青でWeb系の就活したけど、競プロだけのアピールはあまり刺さらなかった印象
「自分のレートは上位3%です！」って言っても、はいはいすごいねーって感じだった

Webアプリを作って、見せるようにしたら多少ウケるようになった
いきなりゴリゴリのWebアプリを作るのは難しいから、例えば、競プロでよくあるグラフの入力をペーストすると、
巡回セールスマン問題を解いて、経路を描画してくれるみたいな、そういうアプリを作って、面接で見せれば、
「愚直にやるとO(N!)なんですけど、動的計画法を使うとO(2^N*N)で解けて嬉しいんですよ〜」
みたいなアルゴリズムの能力も見せれて、良いと思うよ

未経験からウェブ系へ転職するなら、Ruby on Rails 一択

YouTube で有名な雑食系エンジニア・KENTA や、RUNTEQ の動画を見ればよい。
KENTAのRailsサロンとか、くろかわこうへいのAWS サロンも良い

理系や競技プログラミングの知識などは、いらない。
文系で、英語・算数だけで十分

Linux, Docker, AWS、データベースなどは必須。
AWS Solution Architect も欲しい

青くらいで競プロアピールしてくるのは地雷臭しかねえ

別に水色ぐらいあれば、世間が競プロerに期待する人材の要件をほぼ満たす
jobsって転がってる求人もそのレベルだし
青以上になると考察力や競プロ過学習の高低の世界なわけで、そこの色の差で評価を変える理由がほとんどの企業では見当たらない
よほどの高知能者をポテンシャル採用したいときぐらいか
青でアピールするのは地雷とか純粋培養こじらせ過ぎだな

世間の大半は競プロerに「FizzBuzzやそれに毛が生えたようなコーディングぐらいならすぐできて、自発的にアルゴリズムの勉強ゲームをやる勤勉な人たち」程度の期待感しか持ってないし、暖色↑で始めてアピールできるようなものだと思ってるようだと、温度差で死ぬ

>>344
むしろその通りだから地雷なのよ

- 競プロ、まあ一応水色ですけど他に専門分野/強みあります

- ガチで競技として取り組んでててICPCメダリストです

アピールするならどっちかのスタンスだと思ってて青で下のパターンで来るやつがいてヤバいという話ね

壮大な取り違えをしててすまんが、青は高すぎて微妙って話か？
いや、まあ高すぎるってほどでもないだろ、って感覚だけど

>>347
理解したわ
そりゃ青の適切な使い方は上だし、メインウェポンに据えてるやつはヤバいだろう

>>349
でもそういう人特にjobs経由だと相当数いて競プロの評判落としてる気がするのよね

企業からしたらjobsは求人サイトの1つでしかないのにレート条件満たしてたらいけるやろと勘違いしてる的な

体育会系の活動は客観的な成果がそんなでもなくてもメインウェポンになる印象だから、青ぐらいでも頑張り度としては認めてほしい気持ちもあるけどねえ
もちろん、体育会系の活動を通じてわかる協調性や重労働耐性みたいなものを競プロじゃ測れないから、同様に評価されるわけはないんだけど

競プロある程度強いって堂々と言えるのはやっぱり黄色くらいから？
そりゃ橙赤の人から見ればまだまだだろうけどABC対象外にはなるし

>>341
競プロって見た目地味だし何がすごいのか横から見てよくわからないのが課題だから、可視化するのは効きそう
N^3をNlogNまで落とした←ほーん、で？
N=1e5だと6億倍の高速化←お？
目に見えるようにするとこれだけ速くなっている←おお！
ぐらいの印象の差が出るんじゃないかと思う

>>352
業界に競プロerがそんなにいなければ、青ぐらいでも強いと言っていいレベルだと思うかなあ
そういうところではむしろ競プロ自体がどうすごいのか伝えるのが課題になってくる
競プロerがたくさんいる企業だとすると、その人たちのレベル感次第では黄色も「頑張ってる」ぐらいの表現で留めた方がいいかもね
赤はさすがに無条件で強いと言っていい気がするけど

黄色が強い方にならない企業ってよほど限られたところだとも思うけど

青黄が社会で自分は強いとプレゼンしてもそんなに問題は起こらないだろうけど、大会でわかりやすいタイトルを取れるほどでもないから(中高生ならJOIでちょっと積めるが)、別のところでのアピールもあった方が無難

競プロってあくまで経験の1つとしてしか見ないよ
仕事でソロの競プロやらせるわけじゃないし…
コミュニケーションに問題ないか、とか開発経験の有無だとか、他にもいろいろチェック項目あるし競プロ以外のことも聞かなきゃならんのよ
競プロしかなさそうだな、ってひとには競技プロの取り組み方とかを掘り下げて聞くけど

まあ、仮に赤あってもほとんどの場合サブウェポンには変わらんと思うぞ

黄色だけどそんな就活の役には立たんかったぞ
それよりは他に普通の開発経験を持ってて、その中で競プロをどう活かしたかの方がウケは良い
が、大抵はチーム開発経験を聞いてきて、そっちが弱いと露骨に微妙な表情するんだよな……あと最終面接で落ちる

ヒューリスティックの実績メインで採用されてるのは結構見るようになったけどね

いくらアルゴリズムに強くても即戦力から遠いからな

普通に自作した小規模の趣味のwebサイト運営してますみたいなパンチはない

webサイトを立ち上げられる　& ノウハウを持っている
セキュリティ意識が高い&ノウハウがある　←　これが一番大事

競プロ出来てもまともにクラスも書けない人
いらんわな～

CTFとかkaggle辺りでの実績ってどういう評価になるんだろう

組合せ最適化第6版の和訳が出るぜ

https://github.com/yosupo06/library-checker-problems/issues/895
ガウス整数環での素因数分解
A+Biとしたときに|A|,|B| <= 10^9でも十分高速でできる
数論の知識が豊富なら再発明は困難でもなさそう、ABC-Gぐらいの問題っぽい？ARC/AGCタイプではない
結構知識を使うので考える過程でいろいろ勉強になった

コルテ和訳助かると思いつつも、17600円となかなか高い
第2版が値下がりしたりしないかな

コルテの本は競技プログラミングに役に立ちますか？

役に立ちます

>>368
ありがとうございます。
高度な本で競技プログラミングにも役に立つというのはいいですね。
高度な内容を理解するのが主目的で、おまけとして競技プログラミングも強くなる。

そうです

昔のARCの問題は正直今のARCの練習には微妙な気がするな
何が一番近いんだ

数ヶ月触って思ったけど競プロって実際の開発には結びつかんね
まぁ割りと勉強的には面白いからいいけど

俺はライブラリとか便利ツール作る過程で色々学んだけど元々開発経験ある人だと逆にそういうことはないか

ARCも昔（3年程度前）の問題やってるとdiff一色分ぐらい今より高く評価されている印象だから、昔の問題解くんなら自分のレート+400～+800ぐらいの問題解いてるとちょうどいい思考練習になると思う

開発って点だと自動judgeツールとか、ライブラリ整備とかは一応スキルアップにつながりそう
さらに突き詰めて、競プロ用にトランスパイラ作ってる人もたまに見る気がする
けど、こういう作業って決定的な競プロの実力向上につながるわけではないので、なかなか微妙な立ち位置だよね
まあ開発方面の技術につながる楽しみ方も一応あるということで

Qiitaに珍しくいい記事があったとしてその人を雇いたいと思えるか？
競プロのレートなんてそれ以下なんだな

>>374
diffの基準が違うと感じることはもちろんあるが、もっと根本的に問題の傾向変わってないか？
writerの差か

さあ、緑をめざすぞ
茶色到達したってことは4完以外だとレート下がるんだろうか

Qiitaで記事書いてるのは社内ドキュメントとか残してくれそうで歓迎

いや、一個前の順列とか知らんし、Dはiが2,3番めだと思ってた。酷いｗｗ
下手したら２完だたｗｗｗ
検索しても全然出てこないからB問題まで解ければ十分だの

Cムズすぎる🥲

久しぶりに順調に6完できた…

C問題は、C++ならライブラリ使えるから簡単すぎるけど、ライブラリ使わない前提とすると、C問題にしてはかなり難しいような

クソインフレおもんねーわ
結局ガキの頃から脳みそ鍛えてないとｃとかで時間とけて終わるな
ワイのレートは頭打ちや

F問題方針合ってたのにBITも有理数用のライブラリも作ってないせいで実装間に合わなかったけどやっぱり作っておくべきか
三連続で有理数ライブラリ使える問題出題されてるし

>>385
BITと逆元使うだけじゃん
そんなもん理屈わかってれば実装簡単なのに何を言い訳してるのやら

この難易度4完で3000位以下って…
しんどいよぉ

Cわりと簡単に解けたけど証明できなかったから提出するとき一番ドキドキしたw

これ意外と非自明な事実かもしれないから書くけど、有理数をmodとって整数で表せって問題は徹頭徹尾有理数を使わないで正しい答えを出せる

一応、素数modであることが必要かな？

>>383
ライブラリなしなら結構頭使う方かもね
ARC-Aとかにありそう
ライブラリ前提の問題として配置したんだとするとちょっと微妙な気がするなあ

>>391
お前らC++使えよ？っていうちょくからのお達しだろうな

>>386
その二つ自体はそうなんだけど、分母はK^2になるから分子の情報だけ持てば良いっていうのを見落としてたせいで有理数の四則演算をしようとして実装が大変なことになったんだよね
初心者ですまん

chokudaiはC#やkotlinも推してるからC++一強がいいとは思ってなさそうだけど、現実的にC++前提の作問が多くなるのはしょうがないところがある
他言語使いも、競プロerがC++でよくやる処理と同等のことができるようなものを用意しておいた方がいいかなあ
逆に、遠慮なく多倍長整数がバンバン出てくるような制約にしていいと思ってるんだけどね

30半ばのおっさんなんだけど初めて数ヶ月、C問題が解けたことが今まで数えるほどしかない(´・ω・｀)
お前ら天才すぎだろ

こんなん安倍晋三でも全完出来るだろ

全完9人しかおらんやないかーい(´・ω・`)

最近c問題むずいね
以前はdiff 200くらいが目安いうてた気がするけど

紙に(1,2,3,4,5)の順列でも書き出してにらんでれば規則性がわかるだろ

Cは普通にむずいと思うよ
進学校で高校数学まともに勉強してた層の中の上の方がコミュニティ作ってるから基準歪んでるけど
競技と言いながらあまり相対評価に囚われちゃいけないタイプの娯楽

まあサンプルが親切だったね
出力例2を眺めてたらわかった

というかコドフォdiv2のA,Bあたりによくある実験してたら規則性が見えてくるやつだからまあ妥当なんじゃないですかね(証明できるとは言ってない)

Gは形式的べき級数で楽しようとして負の二項定理？っぽいところで詰まってしまったから、これも覚えておこう

>>394
たしかに1000ビットとかくらいの整数の演算を要求

>>395
30歳すぎたら酒飲んだりなんか食べながら気軽にやるのが吉

今回のE問題みたいなやつで、解説でDFSじゃなくてBFSが書かれてるのなんで？
最短経路が不要ならDFSでいいと思うんだけど

競プロ力ってWebとかシステムってよりかはゲームとかの方向な気がする。

>>406

DFSでもいいと思うよ
人によるけど、BFSの方が実装しやすいだけ
Pythonなど一部の言語だと、再設定しない限りDFSでは再帰上限でREになるから解説に書きづらいというのもある

本当にどっちでもいいんだけど、おれもこういうときはなんとなくBFSで実装するようになってきたな
そもそも競プロの探索問題だと、DFSよりBFSを利用することのほうが多くて、BFSが手癖になってきたかな

昨日のEx、F2行列操作の高速化か
こういう細々としたテク、ライブラリ化サボっちゃうしコンテスト中に思い出せる瞬発力もないんだよなあ

ARC/AGCが補充されないけど、来月にはさすがにAGC生やすのかな？
赤が競えないサイトってAtCoderの思想的にまずいような
ARCは今年それなりに多かったし、息切れされても困るから無理に生やさなくてもいいと思うけど（そもそも今どういう内部状況か全然知らんけど）

DFSのが書きやすいと思うけど、確かに再帰って言語によって計算コストに癖があるからDFSよりもBFSの方が安定なのかもね
10^6のサイズのグリッドで2次元配列使うから、遅い言語だとやや定数倍気をつけないといけないタイプ

BFSはキューを使います。
DFSは再帰を使わない場合スタックを使います。
再帰を使わないとして、BFSのほうがDFSよりも実装が簡単ですか？

同じです

今回みたいにただ連結判定するだけならBFSもDFSも同じようなもんだけど、木DPでやるような再帰を活かした+αの処理を非再帰化してスタックで実現しようとするとややめんどい

JavaだとDequeとQueueはあるがStackは古の非推奨クラスなのでBFSの方が楽

別解なんていくらでもあるんだから、BFSとDFSの差くらいで
「なんでこっちの解法じゃないの？」なんて悩んでたらすごく楽しいことになるぞ！

Dequeはスタックとしても使えるのでは

どっちみちお尻から取ってくるか前から取ってくるかの違いじゃろい

今日本語圏で一番知見が集積しているのってLibrary Checkerかな
英語圏、ロシア語圏、中国語圏に似たようなものはあるんだろうか

中国語やロシア語には競プロで使うやたらマニアックなアルゴリズムをまとめたページあるよ

中国の方はまとめた辞典みたいなサイトがあったよな
前スレにあった気がする
ロシアの方は知らないんだけど、どんなやつ？

しかし、赤diffとか解いてる感じでもARCは昔の方が簡単な気しかしないんだが、割と違う意見あるんだな

赤になりやすくなったという文脈であれば問題の難易度とはまた別の話だけどな

あるdiff帯に限定して問題を抽出するとすれば、その難易度はそれぞれの問題の出題時期におけるそのレート帯への到達難易度と大体相関するやろ

時代とともに同じdiff帯の問題の難易度が徐々に上がるのは当たり前で、だからといってある色への到達難易度が上がるわけではない、環境だって変わってるんだから

それは同じ傾向の典型問題がずっと出題され続けている場合に適用できる話だが、ARCは傾向が変わっているわけでそうとも言えない
ARCの昔の問題は今となっては典型となっているので、簡単に感じる、という話なら分かるんだが、どうも昔の方がアドホックで難しいと考えている人がいるのが自分の感覚だと意外だったってことが元々言いたかったことだな

まあ、到達難易度に関しては、最大限リソースを競プロにぶち込んだときにその色になれる確率の話か、その色になるための平均的なコストの話か、でも全然違うから、その辺り明示しないと無限にややこしくなりそうだな
典型性が高まってるんであれば、前者の難易度は下がってるかもな

> 昔の方がアドホックで難しいと考えている人がいる

これは俺も同意できないけどソース何？まあ言いたくなければ別にいいけど

ICPC終わったね
MIT強いな
PurdueとSwarthmoreもそれなりの順位につけてるし、アメリカ結構来てる？

ARCが昔と今でアドホックさに変化があるという印象はなくて、これもどちらかというとwriter依存な気がする
少し前のmaroon回はアドホックだったようなイメージ

というかカーネギーメロン大学も強いな

ARCは難易度もアドホックさも時期によってばらばらなイメージある

MITってMYDのワンマンチームかと思ってたから意外や

Benqが次出るときどういうチームになるのか気になるわ

CTFを勉強しようと以前アカウント作ったんだけど、難し過ぎてpicoCTFからやってたら最初のサイトを忘れた。。。
アカウント申請にもサイトを解析しないとダメでそれはクリアしてアカウント作ったんだけどどこか分かる？

>>437
HackTheBoxでした。
スレ汚しすいません。

数列AのLCMを10^9+7のmodで取る問題が有るんだけど、
答えが合わないのは
gcd(l, Ai)とgcd(l % 10^9+7, Ai)は異なるということ？

って自分で確かめれるか。
家帰ったら確かめよ

じゃあレスすんな

ツッコミどころが多すぎるけど例えばl=10^9+8の場合とかを考えてみればすぐ分かるしそのレベルだと高校数学の復習をしてからの方が成長出来そう

gcd(1,2)=1
gcd(1+10^9+7,2)=2

しかし、その部分でひっかけ？をするのと多倍長整数扱わせたい以外の意図を感じない珍しい問題だ

整数をZ/pZで扱うのは一種のハッシュ化だけど、gcdやlcmみたいな数論的性質がうまいこと保存されるハッシュ化ってなんかあるんかね

ふと思ったんだけど、競技プログラミングってすぐに結果が出るじゃん。
だから、出来た!!って達成感がすぐに味わえる。
それに対して、何かをつくるってすごく時間かかるから
達成感を感じるまでにすごく時間がかかる。
FFS理論の拡散性/保存性と関係ありそうだなって感じた。
FFS理論については俺もよくわかんないんで説明しないけど
競技プログラミング好きは拡散性が高く
何かをコツコツ作るのが好きな人は保全性が高い見ないな。

それはあるだろうね
FFS理論はよく知らないけど、自分は刺激がないと興味関心の対象がすぐ移るから、結果やフィードバックがすぐ返ってくる競プロが性にあう

>>443
というかこれおそらくだけどN<=10^5, A_i<=10^9とかで素因数分解させて素数ごとに指数max取らせるのが想定解みたいな問題だろうから、なんかすごい的外れなこと言ってたわ

レベル感的にはA_i<=10^5の方がそれっぽいか

競技プログラミングの鉄則のB07の問題が解けません。
これがなぜ不正解なのかわかる方いらっしゃいますか(ヘッダ省略してます）？
int main()
{
int T; // 閉店時刻、出力行数
int N; // 従業員の人数

cin >> T >> N;

// 各従業員の出勤時刻を入力して、
// 時刻毎の人数差分表を作成する。
int L,R; // 出勤時刻、退勤時刻
int diffList[500009]; // 前の時刻との人数差分リスト
for(int i = 0; i < N; i++) {
cin >> L >> R;
// 出勤時刻には人数が１人増える
diffList[L]++;
// 退勤時には人数が１人減る
diffList[R]--;
}
// 各時刻の働いている人合計を出力する
int total = 0;
for(int i = 0; i < T; i++) {
total += diffList[i];
cout << total << endl;
}
return 0;
}

>>449
配列初期化してなくね
真面目に初期化するかグローバルに置くか static つけるか std::vector 使う（オススメ）か

>>450
配列のみグローバル領域に置いたら正解になりました！！
ありがとうございました！！

5完
F,G無理無理無理

DのWAが１時間以上もとれない、コンテスト難しくなりすぎ・・・

またCとけんかった
自分ではいけたと思ったのに(´・ω・｀)

EとFGで崖ある回キツいわ
Dでバグって2WAした時点で追いつける可能性が大幅に減って困ってた

Aの傾向の変わり具合もそうだけど今日のCって少し前ならDにあってもおかしくない気がするしインフレしてるんだな

競プロ初心者だが、D問題とけなかった。
長くなるが次のコードの何がいけないのか教えてほしい

2回に分ける
n, m = list(map(int, input().split(" ")))
t = {}
origin = list(map(int, input().split(" ")))
sums = sum(origin)
numbers = set()
for i in origin:
if i in t:
t[i] += 1
else:
t[i] = 1
numbers.add(i)
numbers = list(numbers)
numbers.sort()
numbers += numbers
start = 0
goal = -1
now_max = -1
now_sums = 0
last = None

while True:
goal += 1
if goal >= len(numbers):
break
if start is not None and goal - start + 1 > n:
break
mod_m = numbers[goal] % m
if last is None:
start = goal
now_sums = mod_m * t[mod_m]
last = mod_m
elif (last + 1) % m != mod_m:
last = mod_m
now_max = max(now_sums, now_max)
start = goal
now_sums = mod_m * t[mod_m]
else:
now_sums += mod_m * t[mod_m]
last = mod_m
now_max = max(now_sums, now_max)
print(sums - now_max)

見づらいですね。
画像にしました。
https://imgur.com/a/Jy5RJoL

アカウント知られることに抵抗がないなら提出ページのリンク貼った方が見やすいと思うよ
こんな感じに
https://atcoder.jp/contests/abc277/submissions/36407734

>>461
ですね。サンクス
https://atcoder.jp/contests/abc277/submissions/36450032
こちらになります。

>>462
コード全然見てないから見当違いかもしれないけど、自分も殆ど同じテストケースでWAが出てソート済みの数列が全て差分1以内で連続してるパターン(0 1 2 3 4的な)でのミスが原因だったからこのパターンにも対応出来るようにしたらACになるかもしれない

>>460
0からM-1が全部埋まってるときにバグる
あとnow_max = max(now_sums, now_max)のインデントがズレて更新がおこなわれていないとか？

cもdも座圧unionfind で芸のない出題だなと思いました

あーDはunionfindでもできるね
そっちの方が実装方針としては楽かも

ABC-Eってかなりの頻度で頂点を増やして最短経路問題を解く形の問題が出てる気がするね

>>463-464
サンクス

ああああ・・・なるほど

if start is not None and goal - start + 1 > n:
⇒
if start is not None and goal - start + 1 > m:
にしたら通った。。。悔しい。。

>>464
よくみたらnow_max = max(now_sums, now_max)の更新はloop中でちゃんと行われてるね
失礼

33にもなってこんな連投してんのか

D問題、公式解説でO(NlogN)で実行できるって書いてたけど
自分の実装もそうだけどO(N)でできるんじゃないのかな。

>>470
IT初心者で夢中になってるので、すみません。。

2-SATとproject selectionってやっぱ似てるよなと最近思う

座圧でソートが必要なときと必要じゃないときがあるけど、そこがボトルネックで死ぬことは少ないので、あまり気にされるタイミングがない

むしろジジイもキッズも連投しまくれ

Ex、ARCで中盤で出てもおかしくない問題がちょくちょくある気がするけど、ABCで出ちゃったからARCでは一年ぐらいは出なそうだな感もある

Fが水色くらいになるようにしてほしいですね

Fは青ぐらいがよくない？

EとFを同じ配点にするなら、同じdiffを目指してほしい

それも一理あるけど、GとExは同配点ながら明らかに難易度差があるような作りになってるし、配点と難易度を一致させることがマストとは考えられていないと思う
そもそも広く競プロを見れば点数がなくて完数で評価するコンテストもあるし
個人的にはB～Gで灰から黄まで一色ずつ出現するぐらいが丁度いいABCかなあと思っている