競技プログラミング総合スレ 64
レス数が1000を超えています。これ以上書き込みはできません。
↑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
https://mevius.5ch.net/test/read.cgi/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 【これからも
https://medaka.5ch.net/test/read.cgi/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) https://youtu.be/7DbdPKWhrpY
令和のコペルニクス さんによって固定されています
令和のコペルニクス
2 年前（編集済み）
六角アミダって有りそうで無かったので自作しました。xyz空間座標も「６方向」ということで。
ソースコードはこちら。
https://drive.google.com/file/d/1hsFT2F4AMgUv1JHqy0si_7Yj7q7TyHnR/view?usp=sharing
室町時代のアミダくじは円形であること、ベンゼン環の六角構造、赤青緑の三色ダイオードを考えてみた。
令和のコペルニクス
1 年前
地動説をとる人には、地動説をとるのを妨げない。天動説をとる人には、天動説をとるのを妨げない。学説上において人びとの所見を妨げず、かつ実生活においても、「令和のコペルニクス」は決して客観的に善悪正誤など認定しない。 区間最大値の問題解くためにセグメントツリーのアレを書いたら実装に２時間かかったぞこの野郎 明日の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)) >>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)みたいな風にすればめぐる式でできない？ 昨日コードかいたものだけど
サンクス、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問題さえ解ければ茶色になれる 緑から水色いくのにARCの問題解くのって効果的かな？それともABCの緑以上の問題解いてた方がいい？ a問題でスパゲッティコード書きまくって結局RE
泣きたいですよ ARC2、3完安定してきたと思ったら初めて0完して泣いてる AGC格に持っていけるかどうかは後ろの問題がどのぐらい面白くて難しいかだと思うけど、自分は判定できない
Fがとにかく難しかったみたいだけど
前の方の問題はAGCで出してもいい感じだと思う >>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までいかなくても、次第に速くはなっていくと考えてがんばります。 実装の速さは紙上デバッグを細部まで終わらせて迷いなく書くことだと思う 実装を速くするコツは２つあると考えてる。
１ 思考の手間を省く。
競プロでは毎回全く違うプログラムってことはあんまりなくて、DFSとか1次元DPとか累積和とか毎回書き方が同じ部品というのは結構ある。
こういう部品に対しては、事前に書き方を決めておくことで、その部分はもう考えずに書けるようになる。
２ 隅々まで理解する。
複雑な問題を解くとき、なんとなくわかった状態で実装を始めている人は多いと思う。気持ちはわかるし、簡単な問題ならそれでいいと思う。
でも、実装と深い思考は両立するのが難しい。複雑な思考が必要な問題では、先に最後まで（何行目に何を書くかまで）考えておいた方が速い。 chokudaiが同じ実力でも1年間で50程度レートが下がるみたいな感じの調査を見たって言ってるけど、ソースは何だろう
個人的には大体そんなもんな気がする >>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問題までは本当にプログラミングの基礎力と関わってそうだから、できないのなら練習して損はないと思うよ 永続データ構造ってどの色くらいから常識になる？というかどこからそういう知識を身につけてるんだ
あの問題文を読んで木構造を作るぞって気持ちに初見でなれるものなのかな おれも永続データ構造は全然知らんけど、木でいけそうだなということにはすぐ気づけたよ 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が無難 他の言語覚えるより、C++でどうやるか、だけを準備したほうが確実に良いよ std::stringの機能で競プロのニーズ的には十分な気がするけど perlってpythonより遅いんですね
とりあえずC++でコンテストに慣れて、それからpythonも使おうと思います C問題、方針は良かったのにgrundy数の計算を永遠にバグらせてて死んだ 普段と比べると難しい印象はないけど、ARCらしく素直に解けない問題が多かった気がする https://i.imgur.com/Q53m3ww.jpg
無事茶色達成
しかし将棋ウォーズで言えば1級レベルなのか
もっと頑張ります コドフォdiv. 1も不足してるしAGCも不足してるな
div. 2とかABCレベルが枯渇することはないだろうが、今後高レベル帯では問題を作りやすい実装ゲー、高度知識ゲーが増えていくんだろうか
あるいは新しい分野が開拓されるか デジタル庁が開発エンジニアを募集 任期1年の非常勤
https://hayabusa9.5ch.net/test/read.cgi/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で割った余りも保持しとこう エドモンズの花アルゴリズムを使わないと解けない問題はありますか？ スニペットって登録すべき？ 今まではライブラリからコピペしてたんだけど そんなんなんでもよくね
小手先の効率化よりも、考察力を鍛えよう するだけなら別に手間じゃないしやっとけばいいと思うぞ
決定的に強くなるわけじゃないけどそれで拾えるレートもあるだろう 離散フーリエ変換を知った時は感動した
競プロ界隈じゃ常識かもしれないけど >>152
Unionfind入れとくとかなり便利よ FFTは今でこそ半ば常識だけど、蟻本が本の中で扱わないぐらいのトピックだった
形式的べき級数の流行やACLで普及したのかな？
フーリエ変換なんて周波数成分とってきたり微分方程式解いたりするときに使うものという印象だったから、計算量削減に活用できるのにはびっくり 形式的べき級数が流行しているというのは本当ですか？
どうしてですか？
母関数とかと関係がありますか？ FFTについてはCLRSの第3版に分かりやすく書いてあって、読んだのですが、すごいなと思いました。
フーリエ変換とか難しい解析学の話を全く知らなくても大丈夫ですよね。 Nyaan回のABCが形式的冪級数講座と言われる位には出題されてるだろ
立式も高速化も機械的にできて考察部分を減らせるならそりゃ使うわな 形式的べき級数がABCで想定解法の1番目にくるようなことはないと思うし、便利だということに気づけない人も多そう 形式的べき級数は、Liuの『組合せ数学入門I』とかKnuthの『Concrete Mathematics』に
書いてありますね。
競技プログラミングにどのように役立つのか分かりませんが。 Nyaan回というのはNyaanさんという人がwriterをやっているコンテストのこと
特にABCでは、Exに形式的べき級数の発展的な技法（ラグランジュの反転公式の利用とか）が解法に来ることがあり、解説も丁寧に書かれていてかなり勉強になる 形式的べき級数の利用法として典型的なのは、数え上げの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求めて一文字分比較するだけだからロリハでも普通に高速でできるね LCP求める方法はいろいろあるけど、ロリハにぶたんは直感的にわかりやすくて便利 Nimberとかちょっと前に流行った概念Exに出がちだけど次出んのいつやねんという気持ちに >>200
あ、すまん
A1,A2,A3
x y
の並びかと思った（そんな形の入力ありえんのに）
普通にYesじゃんこれ あ、、、自分のミスだった
最後のA[N]でジャスト(x,y)にたどり着くのか
勝手に最後だけ距離が未定義だと思ってた
すみませんでした！ >>201
こどふぉで役に立つかも精神で・・・
そういえば、ARCはDEとかで割と高度典型が出現することあるけど、AGC後半ってどのぐらい知識が役に立つ問題出るんだろうね
AGCはアドホックの祭典という評判だけはずっと聞いているが、後ろの問題は手をつけていないので実態は知らない 親子関係を図で書いていったら何すればいいか見通しがいいと思うよ 日本語が難しかったね
ナンバリングの法則がちょっとイメージしにくかったかも こどふぉdiv 1だ
少ないと思ったら急にたくさん生えてきた 昨日の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問題まで解いただけじゃ緑までいけないのか 安定して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倍くらい早くて泣いた ハードウェアとかコンパイラとか全然知らないのですが、
vector<vector<int>> dp(N + 1, vector<int>(N + 1, 0));
とか初期値を指定して初期化する場合、初期化の処理にΘ(N^2)回の計算量が必要になりますか？ でも不思議です。
今まで
>>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にセットする処理はかなり定数倍軽そうだし、思ったよりも通りそうではある
もちろん無意味なオーバーヘッドを生んでるだけなのでやめた方がいいけど >>234
タイムアウトではなくメモリの方だね
コードテストだと10秒待ってくれる
>>236
何と比較するかではあるけどメモリ確保は一般には定数倍重い部類の操作だと思う でもN^2のメモリが必要な問題もありますよね。
迷路の問題とか。 当たり前だけどNの大きさによるので
Nが3000以下とかならN^2のメモリ確保でもどうにかなるし、100000なら無理というだけ O(N^2)って"高々"N^2の定数倍で抑えられる、だから計算量がNでもlogNでもO(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万だからこのままやっても計算量的にアウトだったんだろうか 公式解説もNMKだったから一応あってるのか
今回の結果
https://imgur.com/a/C2RD1bF
この間茶色になったばっかりだが、少しでも緑に近づけてることを願う https://imgur.com/c9Dco1P
ええ。。
Cを一回間違えてしまったとはいえ4完全したのにマイナス6かよ、、、緑むりげーだろ >>262
公式見るとあっていたみたいだね。
ただ、低速な言語だと間に合わないで前計算が必要って書いてあったけド、このあたりまだ理解できていないので分数のmodについてちゃんと理解しておくようにする Eは解説とほぼ同じように作ったのに1時間最後まで合わなかった…むなしい… でもE問題が射程範囲に入ったのはちょっと嬉しかった。
C問題がかなり苦戦して、どっち方向に直交ベクトルをかけるかっていう部分に関してかなり苦労してしまった。
結局2パターンについてべた書きしてしまった
D問題はメモ化再帰して一瞬だった。
C飛ばしてEに挑戦してればレーティング上がったのかな >>263
それ前回のパフォじゃん
さすがに今回はレートあがるだろ >>263
これに表示されてるは前回の結果だよ コンテスト名を見ればわかる
今回も含めてコンテストの結果は数時間後に出る事が多いから終わってすぐには反映されないよ >>267-268
ほんまやあああああああああ
サンクス
しかしC問題で一回間違えた(直交方向に足した値が範囲内でおさまってるかの処理を書き忘れた）ので少しそれが心配。。 あとそのレートで4完してるなら今回でレートは100くらい上がるんじゃない？ https://imgur.com/a/5ACK8kd
ほんまやああああああ
緑色がみえてきたあああああああ
E問題まで確実にとけるように頑張りたい Fって精進すればDP使おうってすぐ見抜けるようになるものなん？ 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で良いって聞いたらすぐだったのに GもExも見方によってはLPだし後ろの方はLP回だったのかも 長さが同じっていうだけで判定すると菱形も拾ってしまうよね
直行条件って内積知らないと厳しいと思うけど、やっぱり数学の知識が必要なんだと思った >>290
部分和をちょうどxにするときに何かを最適化する問題って地味に取れる手立てが少なくて（今回のGみたいに例外的に連続緩和できるとかならともかく）、ABCだったらナップサックDPを出発点に考えても大体外れないと思う 数学から離れて長かったり数学にあんま縁がない人だと、辺の長さが全部等しい四角形が正方形であることの必要十分条件だと勘違いするのはめちゃくちゃありそう ARCなくね？
AGCない代わりに最近たくさんあるなと思ってたけど、こっちも放出されつくした？ 問題の枯渇で純粋なアドホック考察ゲー作るのが難しくなってきて破綻しつつあるから、アルゴの方はABCの延長線上みたいなゆるふわコンテンツがメインになり、AHCに賭けてるんじゃないかとか邪推してしまうな 2週間前から始めていますが、AtCoderのBeginnerさえ1問しか解けません
復習はしていますが、全然スキルが上がった感じがしません(´；ω；｀) Bが解けないとすると、使用言語の文法みたいな基礎事項から勉強しながらやった方がいいかも
C++使いならAPG4bとか
Python使い用のも探せばあると思う ARCは今年たくさんやったからいいとして、AGCは本当に生えてこなくなったね AGC少なすぎて赤以上のレートはあまり参考にならんのよね… 出力しないと次の入力を受け取れないシステムになってることを途中から忘れてたの本当にしょうもないミスだ AHCはみんながガチすぎないことによって、昔のアルゴにあったっぽい良さが保持されている気がする 本当にちょっとした改善（ただし自分では思いつけない）でスコア爆上がりすることをコンテスト後に知るとめちゃくちゃ悔しい まずは“本当にちょっとした”とかいう歪んだ認知を直すところからやね 短期コンだと本当にちょっとした改善でスコア爆上がりすることが多すぎて辛い
なんで本番中は入力を虚空に放り投げてることに気付けなかったんだと後悔してる >>300
ありがとうございます、鉄則本頑張ります 問題に付いてるサンプルケースでは正解なのに、ソースコード提出すると他のテストケースで不正解となるんです
おそらくどこかでオーバーフローしていることが原因です
過去のコンテストのテストケースって全部どこかにアップロードされているんでしょうか？ オーバーフローなら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
俺も同じような感じだわ。
脳トレで思ったんだけど、脳の老化防止に競技プログラミング!!
とか言って高齢者にプログラム教えたら面白いかもな。
大半はダメポだろうけど、何百人に一人は才能開花しそう。 新しい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やそれに毛が生えたようなコーディングぐらいならすぐできて、自発的にアルゴリズムの勉強ゲームをやる勤勉な人たち」程度の期待感しか持ってないし、暖色↑で始めてアピールできるようなものだと思ってるようだと、温度差で死ぬ - 競プロ、まあ一応水色ですけど他に専門分野/強みあります
- ガチで競技として取り組んでててICPCメダリストです
アピールするならどっちかのスタンスだと思ってて青で下のパターンで来るやつがいてヤバいという話ね 壮大な取り違えをしててすまんが、青は高すぎて微妙って話か？
いや、まあ高すぎるってほどでもないだろ、って感覚だけど >>347
理解したわ
そりゃ青の適切な使い方は上だし、メインウェポンに据えてるやつはヤバいだろう >>349
でもそういう人特にjobs経由だと相当数いて競プロの評判落としてる気がするのよね
企業からしたらjobsは求人サイトの1つでしかないのにレート条件満たしてたらいけるやろと勘違いしてる的な 体育会系の活動は客観的な成果がそんなでもなくてもメインウェポンになる印象だから、青ぐらいでも頑張り度としては認めてほしい気持ちもあるけどねえ
もちろん、体育会系の活動を通じてわかる協調性や重労働耐性みたいなものを競プロじゃ測れないから、同様に評価されるわけはないんだけど 競プロある程度強いって堂々と言えるのはやっぱり黄色くらいから？
そりゃ橙赤の人から見ればまだまだだろうけどABC対象外にはなるし >>341
競プロって見た目地味だし何がすごいのか横から見てよくわからないのが課題だから、可視化するのは効きそう
N^3をNlogNまで落とした←ほーん、で？
N=1e5だと6億倍の高速化←お？
目に見えるようにするとこれだけ速くなっている←おお！
ぐらいの印象の差が出るんじゃないかと思う >>352
業界に競プロerがそんなにいなければ、青ぐらいでも強いと言っていいレベルだと思うかなあ
そういうところではむしろ競プロ自体がどうすごいのか伝えるのが課題になってくる
競プロerがたくさんいる企業だとすると、その人たちのレベル感次第では黄色も「頑張ってる」ぐらいの表現で留めた方がいいかもね
赤はさすがに無条件で強いと言っていい気がするけど 黄色が強い方にならない企業ってよほど限られたところだとも思うけど 青黄が社会で自分は強いとプレゼンしてもそんなに問題は起こらないだろうけど、大会でわかりやすいタイトルを取れるほどでもないから(中高生ならJOIでちょっと積めるが)、別のところでのアピールもあった方が無難 競プロってあくまで経験の1つとしてしか見ないよ
仕事でソロの競プロやらせるわけじゃないし…
コミュニケーションに問題ないか、とか開発経験の有無だとか、他にもいろいろチェック項目あるし競プロ以外のことも聞かなきゃならんのよ
競プロしかなさそうだな、ってひとには競技プロの取り組み方とかを掘り下げて聞くけど まあ、仮に赤あってもほとんどの場合サブウェポンには変わらんと思うぞ 黄色だけどそんな就活の役には立たんかったぞ
それよりは他に普通の開発経験を持ってて、その中で競プロをどう活かしたかの方がウケは良い
が、大抵はチーム開発経験を聞いてきて、そっちが弱いと露骨に微妙な表情するんだよな……あと最終面接で落ちる ヒューリスティックの実績メインで採用されてるのは結構見るようになったけどね いくらアルゴリズムに強くても即戦力から遠いからな
普通に自作した小規模の趣味のwebサイト運営してますみたいなパンチはない webサイトを立ち上げられる & ノウハウを持っている
セキュリティ意識が高い&ノウハウがある ← これが一番大事
競プロ出来てもまともにクラスも書けない人
いらんわな～ CTFとかkaggle辺りでの実績ってどういう評価になるんだろう 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問題は、C++ならライブラリ使えるから簡単すぎるけど、ライブラリ使わない前提とすると、C問題にしてはかなり難しいような クソインフレおもんねーわ
結局ガキの頃から脳みそ鍛えてないとｃとかで時間とけて終わるな
ワイのレートは頭打ちや F問題方針合ってたのにBITも有理数用のライブラリも作ってないせいで実装間に合わなかったけどやっぱり作っておくべきか
三連続で有理数ライブラリ使える問題出題されてるし >>385
BITと逆元使うだけじゃん
そんなもん理屈わかってれば実装簡単なのに何を言い訳してるのやら この難易度4完で3000位以下って…
しんどいよぉ Cわりと簡単に解けたけど証明できなかったから提出するとき一番ドキドキしたw これ意外と非自明な事実かもしれないから書くけど、有理数をmodとって整数で表せって問題は徹頭徹尾有理数を使わないで正しい答えを出せる >>383
ライブラリなしなら結構頭使う方かもね
ARC-Aとかにありそう
ライブラリ前提の問題として配置したんだとするとちょっと微妙な気がするなあ >>391
お前らC++使えよ？っていうちょくからのお達しだろうな >>386
その二つ自体はそうなんだけど、分母はK^2になるから分子の情報だけ持てば良いっていうのを見落としてたせいで有理数の四則演算をしようとして実装が大変なことになったんだよね
初心者ですまん chokudaiはC#やkotlinも推してるからC++一強がいいとは思ってなさそうだけど、現実的にC++前提の作問が多くなるのはしょうがないところがある
他言語使いも、競プロerがC++でよくやる処理と同等のことができるようなものを用意しておいた方がいいかなあ
逆に、遠慮なく多倍長整数がバンバン出てくるような制約にしていいと思ってるんだけどね 30半ばのおっさんなんだけど初めて数ヶ月、C問題が解けたことが今まで数えるほどしかない(´・ω・｀)
お前ら天才すぎだろ 最近c問題むずいね
以前はdiff 200くらいが目安いうてた気がするけど 紙に(1,2,3,4,5)の順列でも書き出してにらんでれば規則性がわかるだろ Cは普通にむずいと思うよ
進学校で高校数学まともに勉強してた層の中の上の方がコミュニティ作ってるから基準歪んでるけど
競技と言いながらあまり相対評価に囚われちゃいけないタイプの娯楽 まあサンプルが親切だったね
出力例2を眺めてたらわかった というかコドフォdiv2のA,Bあたりによくある実験してたら規則性が見えてくるやつだからまあ妥当なんじゃないですかね(証明できるとは言ってない) Gは形式的べき級数で楽しようとして負の二項定理？っぽいところで詰まってしまったから、これも覚えておこう >>394
たしかに1000ビットとかくらいの整数の演算を要求してたまにはC++erを殺してほしい >>395
30歳すぎたら酒飲んだりなんか食べながら気軽にやるのが吉 今回のE問題みたいなやつで、解説でDFSじゃなくてBFSが書かれてるのなんで？
最短経路が不要ならDFSでいいと思うんだけど 競プロ力ってWebとかシステムってよりかはゲームとかの方向な気がする。 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の差くらいで
「なんでこっちの解法じゃないの？」なんて悩んでたらすごく楽しいことになるぞ！ どっちみちお尻から取ってくるか前から取ってくるかの違いじゃろい 今日本語圏で一番知見が集積しているのって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
配列のみグローバル領域に置いたら正解になりました！！
ありがとうございました！！ 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) >>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中でちゃんと行われてるね
失礼 D問題、公式解説でO(NlogN)で実行できるって書いてたけど
自分の実装もそうだけどO(N)でできるんじゃないのかな。 >>470
IT初心者で夢中になってるので、すみません。。 2-SATとproject selectionってやっぱ似てるよなと最近思う 座圧でソートが必要なときと必要じゃないときがあるけど、そこがボトルネックで死ぬことは少ないので、あまり気にされるタイミングがない Ex、ARCで中盤で出てもおかしくない問題がちょくちょくある気がするけど、ABCで出ちゃったからARCでは一年ぐらいは出なそうだな感もある EとFを同じ配点にするなら、同じdiffを目指してほしい それも一理あるけど、GとExは同配点ながら明らかに難易度差があるような作りになってるし、配点と難易度を一致させることがマストとは考えられていないと思う
そもそも広く競プロを見れば点数がなくて完数で評価するコンテストもあるし
個人的にはB〜Gで灰から黄まで一色ずつ出現するぐらいが丁度いいABCかなあと思っている Fは個々のステップ自体は難しくないから素直にやれば青でもできるものだと思うが、橙diff出た要因はなんだろうな
TLが若干厳しかったのが効いてるんだろうか 自分はすぬけ君の地下鉄旅行を思い出すのに時間がかかって間に合わなかった 確かにハブ的なものを作って辺の数のオーダーを落とすという典型は微妙に有名じゃないのか Cの嘘解法、これを思い付くほうが想定解思い付くよりずっと難しいだろみたいなところがあるな Cの嘘解法、これを思い付くほうが想定解思い付くよりずっと難しいだろみたいなところがあるな ARCも入ってるし、ICPC終わってエンジンかかってきたな 今年で3回目のAGCか
だいぶ開催数減ってきちゃったね 一時的なもので外国人に協力してもらえばなんとかなるのか、本当に問題が枯渇してこれからどんどんAGC作問が厳しくなっていくのか気になるところ こどふぉdiv.1ははなんだかんだ生えてるがインドは生えなくなったしどこも問題枯渇してるんだろう opencupとかどういう質の問題が出てくるんだろうね
漏れ出てくる話を見る限り、割と知識バンバン使いそうな印象でAGC的な感じじゃなさそうだけど
AGC的傾向が唯一のものではなくて、そこで問題を食い合ってたら大変だなと Dまでにダイクストラを使った問題を2年くらい見てない気がする。やるだけになりがちなので出ない。 そりゃ直球でダイクストラをやる問題なんて中々出ないでしょ ダイクストラに一手間加えたものは結構DEくらいで見かける気がするけど opencupはかなりあらゆる問題が出るし難易度が高すぎて質とかよくわからん E問題
やり方思いついたけど時間間に合わんかった
マジで悔しい 同じく。Dまでが難しく時間かかるから解けそうでも足りない。
問題数増やすなら通りやすくしてほしい。 6完
G真ん中先にとって対称に取れればいいけどそうじゃないときが分からん B問題を読み間違えたのもあるけど一時間使ってしまった😭
Cが定型問題っぽかったのに残念すぎる… ちなみに俺が考えたE問題の解き方として
横移動するときに、移動前の列と移動後の列の差分を計算して行くっていうやり方なんだけど
これじゃアウトなんだろうか。300っていう制約があったから計算量的に足りる気がしたのだが Grundy数と真似っ子の複合でなかなか教育的な問題 https://imgur.com/a/Q2WBP15
Dまではノーミスでできた。
緑に近づけていたらいいな Fまではだいぶ素直でABCらしい回だった気がする
問題文やたら長かったけど EとFの難易度が釣り合ってたのも久しぶりな気がするな
数ヶ月前のD辺りに似たような問題あった気がするし逆に置かれてたらFの方が解かれてそう >>508
ちゃんと実装すればいけるんじゃない？
計算量増やさないようにする縦移動が少しめんどくさいので、二次元累積和の方が実装は簡単な気がする ってか競技プロって実務で役立つ説ってどうなんでしょう
atCoder初めてはや３ヶ月だけど、
IT業界２年目で実務で、皆が重いって言ってる内容とか全然重く感じない
競プロによる基礎体力があるからでしょうか（願望） Fは素直だったね
確かにABC-Fはたまにかなり素直なDPが来る印象 プレッシャーの中で頭使いながら速くコード書く練習してるから基礎体力をつける的な意味では十分役に立つんじゃないの？って思うね だよね
ただ、それ以外のサーバー知識とかlinux周りとかはやっぱり経験者の方が強いわ
でも、10年以上IT業界にいる人よりもSQLをかけたりするんだよね
こういうのって、職人の世界で言ういわば力持ちで、広く浅い（？）知識もってる人より偉くなりにくいのかね？どうなんだろう >>514
BからC問題くらいまで解けるようになる価値はめちゃ高くて最も役に立つ帯域だと思う >>514
おれも業務経験ガッツリ積んでから競プロやってるけど、競プロの知識が業務に役立つことほとんどないよ
例えばデータベースでは全レコード数をNとして、検索速度はO(logN)やO(1)らへんに落とし込むのがもともと当たり前だし、役立った気はしない
強いていうなら実装から見積もりができるようになったから、計算量やばいコードの見分けがつきやすくなったぐらいだけど、そんなことが役に立つ機会ほとんどない
なぜかというとオンメモリにたくさんデータを入れることがないからだろうな。1台の計算機でがんばるよりも、どうやってスケーラブルにするかってのが重要だし
アクションゲームのフロントエンド側とかだったら、オンメモリでいろんな幾何学的処理するからもっと役に立ちそう
どの問題が重いって言われてるのか知らんけど灰や茶が重いとか言ってもアテにならんし、ABCは他の競プロコンテストと比較すると圧倒的に実装が軽いしどういうことだろうな？ >>520
514だけど、重いって言ってるのは実務でだよ
かなり細かい場合わけが必要だから時間がかかるっていう実装を頼まれて、3日とか想定してたのを30分くらいで終わらせた
スケーラブルにするのも大事だけど、細かい部分を見る目は大事なんじゃないかね？って思う時はある
今elasticsearch触ってるけど、細かいスコア計算の部分とかそういうのを把握するっていう意味で理数的な競プロの考え方はすごく役に立ってると感じる >>521
やめろおおおおおおおおお
俺のやり方が間違ってたって思えれば時間間に合わなくてもあきえあめがつくのに。。
やっぱりそうか。。。
悔しい 基本的にはオンラインパズルゲームでしかないから競プロが実生活に役立ったら美味しいくらいに捉えて楽しむのが賢明で、役に立つことを期待して取り組むもんでもないってずっと言われてると思う
まあABC-B、Cくらいの指示に従って愚直にコードを書く問題は業プロの基礎体力に直結する気がするからスラスラ解けるのと解けないのでは全然違う気もするけどね >>522
たしかにソロバン経験があると暗算が早くなるのと似たような感じで
競プロやってれば数学的/論理的な思考はだいぶ早くなるだろうね >>524
業プロにワロタ
いやさ、今メンバーをプロジェクトにアサインする問題が会社にあって、
該当メンバーがコードの読み書きが全然できないって客先から怒られてたりするんだよね
だから、競技プログラミングのA問題を解けるかどうかで判定してみるのはどうだろうっていうことを提案しようと考えてた
解けるかどうかっていうよりもそれを解くときの姿勢とか、調べる気持ちとかがあるかどうかってそこで見極めることができる気がする
B問題でもいい気はするけどB問題以降はガチ勢っぽいイメージ俺は持ってるからメンバーのアサイン判定には不向きかなって ABC-Cあたりがごく普通の業務で出て来る可能性があり、なおかつかなり個人差がある領域だと思ってるけど、そこが速いと捗る
その部分が進捗のボトルネックになってしまう人もいるので 自分は競プロできないからどうのみたいな考え方はそんなに好きじゃないけど、さすがにプロのプログラマーだったらABC-Aは解いてほしいかなあ >>526
なんか普通にやたらレベルが低そうで笑えないな
とりあえず学歴フィルターしたら？ 思うんだけど、
競プロって計算量オーダー云々っていうよりも
データの構造とかハッシュテーブル的なものをちゃんと理解しているかどうかだと思う
そういうあたりを正確に理解してれば、計算量なんて悪いパターンになることを知ってれ場何とでも対策できる
プログラム書く上においていろいろな構造を正確に頭の中で描けるかっていうことを図るいみで競プロは非常に有効だと考えてる 愚直に(全探索とかをして)コードを書いても制限を超過しないっていう点でABC-B(と一部のC)くらいまでは確実に業務に直結すると思うよ
たまにプログラミング関係なしで簡単な算数・数学っぽい問題も混じってるけど >>529
俺自身が29歳までトラック運転手の高卒だし、学歴フィルターはできない
アサインチームがOJT目的であまりにもポンポン案件入れてしまうので、業務チームが火を噴いていることは事実
だから、A問題を解いてみてが一番いいと思う >>530
そうだね、情報系学科を卒業してないなら、教養としてせめて競プロ経験しててくれ、って感じはあるかもしれない 頭の中で、配列、ハッシュテーブル、stack、queueのイメージぐらいできてもいいかもね
std::setは平衡二分探索木を忠実にイメージしようとか考えだすとめんどくさいけど >>531
算数・数学も最低限の教養として必要だと思う
そもそもにして式を立てられないんだったら数字を使う業務にアサインできないと思うし、統計的な考え方ができるかできないかも大事だと思う
競プロで出てくる数学ってD問題までに限って言えば高くても高校レベルだから、漸化式を立てるとかそれくらいはやってほしいって思う Ex、解けてるの一人だけか
相変わらずNyaanさんの解説は読み応えある A, Bが解けねえ奴には流石に知的労働は即座に辞めろと言わざるを得ない(´・ω・`) >>532
ABCコンテストで試すより、それだったらPASTかPaizaのほうがいいかもね Wとw間違えて3分ぐらい無駄にしたんだけどおすすめのフォントない？ problems見たらEが緑下ってコンテストのレベル上がった気がする。灰色コーダーは普通に優秀。 Cが灰色で慣れてればなんでもないけど、グラフの教科書通りリンク行列とか作ったりしちゃったらメモリが全然足りないとか 一昔前の茶が灰上位ぐらいになってて、灰上位の能力があれば十分通用する職場がたくさんあるのは事実な感じがするわ 今レート590なんだけど今日のARC問題、挑戦したら事故る可能性高いかな
A問題だけのみ完だとレート下がるんだろうか とりあえずやってみたらいい
心配なら過去問もあるし
そのレートなら失うものはないと思うが ARCはABCほど過去問を解いたからと言って解けるようになるとは限らないけどな！！！ Arcはせめて水色以上じゃないと0完がデフォになる
俺は緑だけどarcの茶diff が解けないこと多い
同じ色でもabcとarc だと難易度違うんだよ コードの書き方とかアルゴリズムの基礎とかはJOIの過去問とかでもかなり良いよ
難易度によって変わってくるけど 初挑戦だけど参加者が思ったよりハイレベルでビビった
Dまで解いて半分よりちょっと上程度なのか
そりゃ上位人にはかなうはずもないけどまさか底辺までここまでやるとは AHC Nが小さい方が点数が大きくなるの見落としてて悲しい 参加者の属性で一番多いのが東大やからそりゃレベルは高い A問題、解き方はすぐにわかったけど、実装でかなり苦労したな
1時間以上かかった
B問題は問題読んでそっとじ
A問題、俺は端から一個飛ばして、数字毎に一個飛ばしっていうやり方をとってACしたけど
これが本当に一番最悪のケースっていうことって数学的に証明できるんだろうか >>561
埋めていったときに空き区間の長さの最大値の最小値が1以下にするようにって感じだけど、確かに証明はめんどくさそう
直感的には明らかなんだけど BもCもエスパー効かなくて崩れたやつ多そうだな
ARCっぽい感じだった Bとかパッと見かなり簡単そうなのに始点が同じ場合だけ考えれば良いことに気づけないと沼にハマって詰む ABCの過去の問題見てると昔は簡単だったんだな。
C問題くらいまででも今のBより簡単じゃね？と思える 教材の充実や競争の過熱で、同じdiffでも今の方が難しくなってる傾向はあるよ C++使いが問題作ってるから若干C++に有利だな
専用のライブラリが使えたりするし再帰呼出しとかのC++が苦手そうなやつはスタックオーバーフローしない回数になってるし 横レスなのだが、
C++って割とstack over flowには強いんじゃないの？
興味ある
C++が優遇されているのは同意
もう少し、Pythonの人へ配慮を… 常に問題の制約が64bitが前提になってるのがまずけしからんわけだ
64bit整数が扱いやすいなんてC/C++、JavaやGo、みたいなコンパイル前提の言語ばっかじゃん
たまには150bitらへんを制約にするとか
正規表現使えば楽勝みたいな問題をもっと出すべき >>569
スタックオーバーフローしない回数なんじゃなくてatcoder上でオーバーフローしないってだけじゃないの
atcoderはスタックサイズ上限無制限にしてあるからmemory limit超えない限り落ちない ノートPC持ってる人多いのか？
仕事はノートPCだけど会社から貸与されてる仕事用のものだから私用に使えないし、
自分のPCは基本的に自宅でしか使わないからデスクトップで十分だしスペック的にもデスクトップがいい
わざわざPC2台持たないし ガイジガイジガイジガイジガイジ
ガイジガイジガイジガイジガイジ
ガイジガイジガイジガイジガイジ
ガイジガイジガイジガイジガイジ
ガイジガイジガイジガイジガイジ デスクトップPCはかなり機能強めのものを買って機械学習専用機にしていて、出先とかでも使える用のミドルスペックノートPCを普段使いにしているよ 競プロやるかーって思ってたけどなんかいまいち評判よくない感じなので見送り気味。プログラミングする人間に頭でっかちはちょっとダメ＞＜ なんだこいつちょくだいかよって思ったらちょくだいだった D問題、普通に数学解けないと解けない問題が出てきたな
AC出来たからいいけど
A～Cまでは普段と比べてめちゃくちゃ簡単だと感じた
E問題は問題の意味が分からず、残り２０分でようやく意味が分かって時間的に足りないと思ってそっ閉じ >>581
今日プロ始めたばっかのころ（ここ４カ月以内）
DがとけなくてEが解けたっていういこと一回だけあった
それ以来E一回も解けていない
Eに手が届くレベルまで早くいきたい D、最適化ライブラリでどうしても10^-3までしかあわないまま80分とかしてダメ元で投げたら通った・・・ >>584
python?どんなライブラリなのか教えてほしい d問題で最小値を求めるべき関数、ほんとだったら下に凸なことを証明しなきゃいけないんだろうけど、「導関数が0になるとこ一ヶ所しかないからここが答えやろｗ」って解答しちゃった >>586
俺も
高校時代だったらすぐに証明できただろうけど
わからなかったからmatplotlibで関数の形見て下に凸だって決めつけてしまった １年ぶり位に復帰したけどインフレやば過ぎワロタ
三分探索が茶とかもう無理ゲ 手計算したくないから、回答と少し違うwolfram先生の解析解の周辺の最小値でやったけど、最後のサンプルがどうやってもあわなくscipyに。実務家的ｗには脳死でoptimize一択。 Dで10^18制約で誤差10^-6無理じゃね？と思ったら絶対誤差または相対誤差って書いてあることに気付いた
ひょっとして今までの問題も全部そうだったのか Python しか触ってないからわからないんだけど
他のCとかだと誤差が大きくなって3分探索とか使わないといけなくなるもの？ >>592
微分して0になる点の整数インデックスさえ求められれば
そこからプラマイ5くらいずらして最小値を求めてばいいと思うけど
俺はPythonでインデックスとインデックス＋1の最小値で求めることできたけど
ってか代数的に解ける問題が出てくるんだなってびっくりした せっかくデ/アのスキルを磨ける競プロをやってるんだから、代数解法よりも三分探索を使って解いてほしいところ
まあ競技的にはとにかく解ければ勝ちなんだけど >>595
計算量を考察する箇所でも代数的な考察するし
代数だけではどうしようもないということを頭でしっかり認識してからパズル的に解くのが醍醐味だと思うんだけど >>593
想定解法であれば、3分探索で絞り込むのは「操作回数」だから、誤差が代数解法よりも小さくなるわけではないよ そうだね、そら何にしても数学は使うよ
デ/アはそもそも数学が下地にあるからね >>597
誤差の部分よくわからんのよね
どのくらいの誤差が起こり得るのかが
コンピュータの深い部分か何かしらの知識があればわかるんだろうけど
FFTで誤差が出ないから、とりあえず実用範囲で小数計算の誤差は考慮してないな
それだけPythonが数値計算で有能なのかも知れないが >>599
きみは何らかの代数ライブラリを使ったのかもしれないけど、おれが「代数解法」と呼んだのは公式解説にある「解法2 微分」のこと
「解法1 三分探索」でも「解法2 微分」にしても、どちらにしても最小値になる回数を見つけてからの計算方法はほぼ同じだから、同じ精度で答えが出力される
よって誤差は関係ない
>>600
データ構造とアルゴリズム >>601
俺は微分したけど、3分探索はわからないけどLogNとかになるのだとしたら微分したらO(1)だと思うからそっちの方が速そうだけどな
データ構造／アルゴリズム
→わからんかったよ。。 >>603
解説聞いたらわかったけど、初見じゃわからんかったよ すまんな、競プロの界隈だとデ/アってよく使うから当たり前に使っちゃうわ 数学が下地にあるのは確かだけど、日本の学校教育では出てこないようなパズル問題が出てくるところが競プロの好きなところ >>605
常識だったのか。スラッシュあまり使わない俺はあまり馴染まないかも知れない(と言って1週間後使ってるかもしれない)
競プロ初心者高卒だから、そういう界隈の言葉どんどん教えてくれると嬉しい いや、ただのTwitterスラングやで
わからんくて当たり前 まあプログラマーは一応理工系技術職だし、高校理系標準レベル微積ぐらい扱えた方がいいと思うぜ ワテが3分探索を使わない理由は
・最適化の本で見たことがない
・多次元に拡張できない、教プロ特有な気がするので学習モチベがわかない
こんなところか・・・ 今回は入力が整数だから二分探索のが分かりやすい気がした
めぐる式でf(x)とf(x+1)を比較して大きいならok、そうでなければng
最後にf(ok)を出力するだけ >>608
コンピュータサイエンス用語でもない競プロスラングなんだからわからんのが当然だとは思うけど、「競プロの界隈だと」と言ってるのに高卒だからと関係ないことを言い始めるあたりの理解力はちょっと怖い 無学なものですが、的な表現なんじゃないか
そういう卑下は別にせんでいいとは思うがな
大卒でもプログラミングも競プロもずっと分かってないやつ五万といると思うわ >>615
高卒の俺でもある程度頑張ってるよって言いたかっただけ
あと、高卒ってベースとなる知識が圧倒的に少ないと感じてるからスラングでもなんでも、そういう中に考え方が潜んでるからそれを学びたいっていう気持ちがあっただけだよ 二分探索って初期値(左と右の)の設定難しくね？
279_dは解の範囲考えてるときに微分すること思い付いた。
1/(n+1)の微分をググったのはちょい恥ずかしい 計算がおかしくならないならでかい値でもよい
難しい考察なしで0からAにしてAC AGC、12月25日に入ったね
それ自体はめでたいことだけど、もうちょっと間隔をバラした方がありがたいような
そしてクリスマスという 実際クリスマスだからといって何か予定入れることあるかね？ ギャグ抜きにして海外勢も予定入ってるやつ多そうだし、正直どういう判断でクリスマスに入れようと思うのかよくわからんわ ようやく問題が揃ったってだけじゃね
寝かせてると他で使われちゃうから新鮮なうちに出さないと >>621
下に凸ということがわかれば二分探索で解けることは明らかなんじゃね
接線の傾きが右上がりもしくは水平になる最小の値を調べればいい
つまり右下がりなら前半を捨てて右上がりなら後半を捨てるの繰り返し
初期範囲は0からAで行けるしその倍でも比較が一回増えるだけ クリスマスって年間のイベント日の中でも tier 高いんですか？祝日ですらないけど 自分は傾きでなくマイナス1とプラス1の値で比較したから合わなかったんだな
gの変化が1ずつだからってそれでは駄目なんやね
3分探索も知らなかったけど色々勉強になって面白かった AGCを積極的に求めてる程競プロに入れ込んでる層はクリスマスなんかに予定が入ってるわけないだろうと足下を見られてるな 日本ローカルな有志コンならともかく、数少ないグローバルなAGCがわざわざXmasに重ねられてるのはちょっとどうかなという気はしちゃうな
AtCoder側の都合はしらんけど、欧米圏だと24日は仕事は早くあがって、クリスマスマーケットも終わって、25日はゆっくり過ごすだけの祝日と相場が決まってる 海外勢にこそアピールしたいAtCoder最高コンテンツのはずのAGCとクリスマスコンテストを同列に語られても 問題が爆破されないように、という理屈は理解できるが、3週間寝かせるだけで問題が爆発されるようなシビアな世界なのか？というのも気になるな
ARCならまあありそうだが ABCのC問題
ST各行の・の数だけカウントして比較してるだけで正解なの何でなん(´・ω・｀)
転置して文字比較じゃないと題意を満たさないと思うんだけど 誤った解答というのは「ST各行の・の数だけカウントして比較」の話ね マルチテストケースにしてNが小さいところは全部入れれば簡単にテスト強くなるけど
AtCoderはやらないよね >>635
転地しないと駄目なのはaftercontest 追加されてたけど
点の数だけで通るってマジ？ いつも思うんだけど、そういう作問の不備らしき問題ってどこに通報すればいいの？ マジでTwitterくらいしかないよね
外国の人かわいそう 解説と同じアルゴリズムだと通るのに愚直に解くとWAになることがあって悩んだことがある
TLEならともかくWAになるはずなかったんだがなあ
なにせ1000000007で割った余りを書きましょうという問題で全部BigDecimalで計算して最後に一度だけ割る解法だったし 質問するならコードを貼れ
通らないならどっか間違ってんだろとしか言えん AIに問題文投げただけで正答のコード返してくれるようになったら競プロは終わるのか？ クリスマスにちなんだスペシャル問題が出るんだろうな。 A:やるだけ
B:累積和をやりながら差をやるだけ
C:Sの先頭から見てTと違う文字が出てきたところが答えになるだけ。Sの末尾になんか$とかみたいな1文字を追加しておくと簡単
D:素因数分解して素数ごとに、Nが最低でいくつ以上になるかを二分探索によって求めるだけ
E:f(x)=1 + P/100 * f(x-2) + (100-P)/100 * f(x-1) みたいな計算をメモ化とかDPとかしてやるだけ
F:BFSして訪問するごとにどこからどこへ行けるのかUnionFind使ってマークし、コストをポテンシャルとして記録する。あとから違う値でポテンシャルを更新できる場合はUnionFindのその集合はinfになるとわかる。答えはUnionFindと、ポテンシャルの差を見るだけ
G:Fまで早解きすればパフォがカンストして2400になるから賞金どうでもいいなら解かなくていいので無視するだけ
Ex:無視するだけ Fで無駄にLCA持ち出して距離を求めようとしたせいで時間浪費したのマジで勿体無くて泣ける
LCAの項が打ち消されるのに C簡単すぎてびびったわ(´・ω・｀)
Dは素数の問題だとわかったが何故かいつまてまでも数個ACせんかった(´・ω・｀) 今回はFまでの早解き回だったね 自分もカンストしてみたかった 重み付きUnionFindってなんだろう
しらんけど同じようなことをおれは実装してたのかな 小数点以下が切り捨てられて表示されていて実際の提出時刻は22:40:00を僅かに過ぎていたのか
あるいはコンテストの開催期間は[21:00, 22:40)だったのか これってカンニングやり放題だと思うんだけど意味あるの？
昔は会場で受けてた？ 転職の武器になるかな？って思って調べるけどよくわからない
ここのスレ見てても転職できたという報告は全然ないね
募集枠はあるけど採用されないように見えるね 遊んでた結果副次的に転職出来たらラッキーくらいに思っておくのが賢明でそもそも転職目的で取り組むものじゃない定期 ChatGPTが解けてるのはただ単に問題文覚えているからだと思うが、AGCの新問を解けるようになったら革命起きそうだな 1万文字をcinで入力して、文字列長を調べたら4095と表示されてしまいました
何故でしょうか？(´；ω；｀) 昨日の問題EのcriticalHitがよくわからないんだけど
解説にatcoderのincludeファイルがあるんだけどなんだこれ？
PとQ求めたらこのファイル使うと勝手に計算してくれるの？ それはAtcoder LibraryっていうAtCoderのジャッジで使えるライブラリなんだけど、初心者には明らかに説明不足だね・・・ >>671
つまり、高速でPとQを解かせるのが本題で、
mod計算はライブラリがあるからそこで時間つかうなよ！って事かね？
使わないと困るケースがあるんだろうけど...理解せずに脳死で覚えた方が良いんかな？ この手のDPにACLの出番あるのかと思ってみたけど、modintか >>672
別にACL使わなくても自分でスクラッチしてどうにかなるレベルだけど、負になったときの処理とかがめんどいから使った方が楽って感じのノリ そうだなあ
ACLで実装されてるのは有名アルゴリズムばかりで、ABCでもよく出題されるの多いからライブラリで実装されてるものは理解したほうがいい
ACLは使ってもいいし、使わなくてもいい
まあ、とりあえず問題が解ける程度には理解して使えるようになることをオススメしておくか
特にmodintは便利だと思う
ACLをローカルにインストールすれば、自分のパソコンからも使えるよ ちなみにおれはC++使ってないし、そういうライブラリは一通り自分で作ってる 休日でぼーっとしすぎて頭が痛い
何かしらウォームアップするか、逆に仮眠取るかしないとAGCやばい気がする >>677
休日の片頭痛は、だいたいカフェイン不足が原因だろうから、カフェイン摂っておけば治るというのが自説 モンスター爆飲みやなー
翌朝の予定とかもう関係ないね 分数をmodで表現する方法が分からなくて解説見に来た人が何も分からないままだから、「modでの計算はたとえばACLを使うことで求めることができます」みたいな一文とともにACLドキュメントへのリンク欲しいね
そもそも新しく入ってきた人はACLの存在知らないだろうし 小数点の既約分数表現だか、理解するモチベーションが全然わからない 分数のmod表現は最初は数字が非直観的で戸惑うかもしれないけど、やってることは全然難しくないからACL使用前提じゃなくて普通に理解すべき
逆元と繰り返し2乗法理解してれば一瞬で書けるし >>667
>>668
普通のコードです
std::stringでも同じ結果になったため、charにしてみました。
#include<iostream>
#include<string>
#include<string.h>
using namespace std;
int main()
{
char S[500009],T[500009]; // 変更前文字列、挿入後文字列
// 入力
cin >> S;
cin >> T;
// 変更後文字列の長さを求める
int len = strlen(T);
// 開始位置は先頭
int start = 0;
// 終了位置は文字列の最後
int end = len-1;
// 以下省略
return 0;
} >>684
intって32ビットですよね？
でしたら足りてます >>683
ちゃんと10000って表示できるよ
https://ideone.com/cjnxWH#stdout
だからコードじゃなくて、コマンド操作の方法に問題があるんでしょ >>686
ありがとうございます
>>687
サクラエディタで１万文字を２行分書いて、それをCtrl＋Aでコピーして
VSCodeに右クリックでペーストしました
この作業で文字がカットされている可能性がありますね
ありがとうございます！！ 期待値の問題ってワンパターン過ぎじゃ、、？
単に水色だとこんなもんで青黄の期待値問題はもっと複雑なの？ 同じ二完でも遅いと全然パフォ伸びないな
絶妙な解きにくさで、ああAGCだなと思った >>690
そもそも水diffのDPは丁度EDPCで見るようなレベルだから、実際パターン少ない
もちろん上のdiffで典型度低くて難しい期待値問題はたくさんある Aみたいなのは発想でどうにかするより逆順で実験する方が安定するよ 期待値という概念の扱いに慣れてない低学歴が引っかかるから簡単でもdiffは上がる 青上位 青上位 赤 銅 銀 AC0
は草
もうレーティング対象青からでも良いんじゃないか atcoder jumperは下回ったな
A問題最高diffはならず 配点からしてAがむずかしめなのは予想できたし、まあ
水色くらいの人たちならそんぐらい自己判断できるし、まあ水色以上Ratedで良いと思うけどね
それよりARCを3200くらいまでRatedにしてあげたら？って気がしちゃう 操作を繰り返して全て同じにしたいときに隣接要素が異なる箇所の個数の変化を考えるのは典型な気がする
Bが重くてつらかった それは考えたけどほぼ常に2個ずつ減らせるとはわからんかった 下界/上界が必ず達成できる典型という奴だな
自分はABCABC型が3回で揃えられることすら見逃してたせいで詰んでた 異なる文字同士が隣接している部分の特徴量として使おうってのはまあすぐ思いつくしそれはそこまでの発想じゃないと思うが、ABCABC三回とかがコンテスト中だと意外とソラで気付けない
そうこうしてるうちに別の方針に飛んだりしてかなり時間食う
一方Bは下界と上界がすぐ見えるし、700点問題にしては木となもりの関係性と似ていることに思い至るまでにそんなに飛躍はないように思う
実装パートの方がつらい
その結果が正答数逆転だわ わかるわ
B発想の割に普通に実装が重い
時間経過でどんどんAC数増えるのも納得 愚直コードを書いてパソコンに実験させるのが良かったんだろうけど、これくらいの問題なら紙に書いて実験するので大丈夫だろうと高をくくって最小回数を勘違いしてたせいで一生WAが出て地獄だった
パソコンに実験させる習慣が未だにつかない 自分もどちらかというと移動中の微妙なスキマ時間に競プロの問題を考えることが多いから、実験はそんなに得意ではないかなあ
高難易度ほど予想解きスキルが必要そうだから、ARC/AGCで戦うのなら練習した方がいいかもね AGC、診断人氏が0完とか、もう一般的にかなり優秀な人ですら出れるレベルじゃないのかｗ 水色の底辺なら0完でも温まってるから、逆にレート低いほど出るべき 昨日みたいな簡単な問題が無い回だと本書いてる人や赤コーダーみたいな高レベルの人でも0完しちゃうことあるんだなってびっくりした AもBも感覚だと普段のABC-Gより難しかったから、0完でも凹まなくていいと思うよ 赤の0完は流石に戦略やろ
一定時間かけてダメだったら後ろに賭けるしかない
まあ赤でも瞬殺できるわけではない問題だったのは確かだが 赤からすると、終了30分前にA問題解いたとて、って感じだろうからな
最後のギリギリまでC以降に賭けた方がいい 0完で水パフォってところから、AGCのrated制限ってかなり絶妙に設定されてると思ったね
年6開催のころに仮に同じ難易度、all ratedだったら、参加し続けることで一年すべて0完でも緑ぐらいには行きそう そういえば、この前のAGC-A、最初解法ガチャでMoじゃないか？とか考えたんだけど、それでもできるのかな MoチラついたけどA問題でMoが想定解なわけないしな……って思ってすぐ却下しちゃった
テストケース次第では間に合うのかな 想定解を知ったあとだとMoでACできる遷移はすぐ作れる気がするが、それって本質的にMoのおかげで解けたことにはならないんだよな
てかその遷移に思い至るんならMo使わんやろっていう 昔直大が998244353なら使えるアルゴリズムが1000000007で使えないことがあるのでメタ読み対策で998244353使う的なこと言ってた覚えあるけど具体的に何があるの？
998244353使ってる問題解いてて気になった >>950
!extend:checked:vvvvv:1000:512
!extend:checked:vvvvv:1000:512
テンプレからコマンド消えてるのでテンプレに追加してください >>722
畳み込み演算を高速化するFFTの亜種で、数論変換というのがある
普通のFFTは複素数を使うけど、数論変換はずっとmod pで計算するから精度上の問題が生じないのがメリット
p-1 = 2^m * dみたいな形で書いたときにmが大きいpほど扱いやすく、998244353は大きくて、1000000007は小さいから、そこで数論変換を使うかどうかがバレやすい的な話 >>719
やっぱ一回は思い浮かぶよね
そんなに単純な解だと思わなかったし そもそも1クエリ固定の場合を解けないと話にならなくて、セグ木やらMoやらを考えるのはそのあとでないか 解既知区間を左右に1伸長したときにまた高速で解を求められれば一クエリでも多クエリでも対応できるから、そこに絞ってまず思考してみるというのも戦術としてはあるだろ
帰納的に考える方が多くの場合少ない思考リソースで問題解けたりするし 言ってることようわからんが結局1クエリ解くことから始めてない？ その1クエリを解くにあたり、Moで多クエリでも高速で処理することを見据えて、1クエリの解を伸長で構成することを試してみるって話
一方、セグ木で解くことを見据えるなら、モノイド性をどこかで見出して区間を併合しながら1クエリの解を構成できないか考えてみるというアプローチになる
メタ的には、多クエリで高速で解ける以上は、1クエリの解き方も限定されてくるだろうって考え方だな
別に数学的知見じゃなくて、ただの問題解く手順のお気持ちみたいなもんだから、わからないんならわからんでいいよ 前回のAも、「多クエリを高速で処理できるんだから簡単な区間の特徴で1クエリ分解けるだろう（そもそもAGC-Aだし）」で想定解に至った人も割といるんじゃないか思っているが、発想的にはそれと似たようなものだと思うわ 区間の伸長が高速にできるなら、解が自明な長さ0や1の区間から始めるだけでは 自分がMoを考えたと言ったのは、1クエリ解くにしてもDPみたいに漸化式作れたらやりやすそうだからと思ったからかな
もちろん最初のクエリの答えは自明な区間から出発するよ なおだいブログ曰くchatGPT使っていいらしいな
Cまでしか解けないしなんか問題文を変換しなきゃいけないらしいから茶以上だと意味ないけど 適当に自動化してA、B、CをChatGPTに瞬殺してもらって良いってことなの？ 3問目まで自動で解いてくれるなら5分ぐらいは節約できるし多少はパフォ上がるかな twitterから拾ってきたやつだけど
・英語版の問題文を与える
・数式等をTeXで書く(A_i, 10^2など)
・入力と出力の例を与える
・AtCoderの問題であることを教える
・Pythonで書かせる
必要があるっぽいから普通に解いたほうがいい気がするな まだ発展途上とは言えイラストAIもあっちゅう間だったしな。
もう俺みたいな底辺は解く楽しさしか残らねーわ。 >>737
TeXへの変換規則さえちゃんと考えてコーディングしておけば、後は自動化できそうな感じもするな これからはAIをうまく使う力が重要なのであれば、練習としてそういう解き方を研究するのもありだと思ってるわ それってデータエンジニアじゃん！
Kaggleじゃん！ kaggle定期的にやりたくなるけど競プロ諸々との両立が難しくて毎回挫折する Kaggleって機械学習モデルの精度競争的なイメージが強いけど、AIツールを活用した作業効率化みたいなイメージで話してた ChatGPTをAtCoderのコンテストで使用することが認められるならコンテスト出ないって人を見かけたけど、いまはまだ茶色程度の実力だけど、
仮に暖色程度の実力を備えた競プロAIが登場したとして、AtCoder公式から使用を認められたら、どう反応する人が多いか気になる まだ未参加なのですが過去問ABCのABまでしか解けないとして参加する意味ありますか？
あとABだけ解けて茶色行けますか？ コンテストになれば普段より集中して問題に取り組めるので参加する意味はあります
また参加回数が少ないとレーティングに補正がかかって低くなる仕組みもあります
ABだけでは茶色にはなれません >>748
英検とかと違って無料で参加できる実戦だから、練習になるし意味あるよ
強いひとはAtCoder以外にもいろんなコンテストに毎週たくさん参加してたりするよ
ABだけで茶色は無理かな
茶色にいくならCまで余裕もって解いてくださいな >>747
https://www.businessinsider.jp/post-263042
この前こんな記事読んだんだけど、やっぱりChatGPTは「考えて答えている」んじゃなくて「それっぽい文字列を吐いているだけ」みたいだから、これからよほどのパラダイムシフトがない限り暖色程度の実力を備えた競プロAIは無理じゃないかな
まあそのパラダイムシフトに立ち会ってみたい気もするけど
>>748
本番の時間制限あるなかで考えるのも楽しいし、やってみればいいと思うよ >>749-750
ありがとうございます
練習で参加してみます ABしか練習してなかったけどCまで解けて、
DはWAが少し出て時間切れでした残念。
でも緊張感あって楽しかったです。 D難しくなりすぎ・・・・。もらう方でやってバク取れず。２重dpでうまくいかない事に気づくまで40分。 D解けた人の境界見たら、1245位だったのでかなり難解だったんですね。
ダメ元でサンプル通ったから提出したら当然WAでしたが解説見てもさっぱりでした。
少しずつアルゴリズムというものを勉強したいと思います。 editor使わず糞アットコの糞サイトbuiltin editorだけで書いてみた
やっぱり全然だめだな(´・ω・｀) 総和が○○のときの△△を求めよ、みたいな形はナップサックDPであることが多いね 同じ問題のレートが１年で50下がってるんだから、Dは茶色下くらいを目指そう よかった
俺の調子が悪かったわけじゃないのか
三重ループまでなんとなくわかってたけど実装が複雑になりそうでできなかった Ex見てるがやっぱり分割統治FFTいつまで経っても慣れんな 愛知ループは三重の三倍難しいと言われてるからな。。 DPや二次元配列などでarray型の生配列を使う例が多いのは慣習的なものですか？
処理が速いとか利点があるのでしょうか？ arrayより楽な選択肢なんかある？
arrayじゃダメなときは当然そっち使うにしても 青安定のために参戦を決めていたのですがぐっすり寝てしまい出れなかったであります🤓 >>766
デバッグしたい時などにあれこれ配列の中身除くのにｖｅｃｔｏｒ配列の方が扱いやすいなと思って使ってました
解説でもDPでvector使ってることもあればarray配列使ってたりと別れるので好みとは思うのですが
何かarray型を選ぶ利点があるのか素朴な疑問でした
>>arrayじゃダメなときは当然そっち使うにしても
array使ってる例が多い気がしたのでvectorからarrayに変更して試してたのですが
vectorに慣れすぎていて逆に使いづらいと思ってvectorに戻しました
ダメな時に結局vectorにするのでそれなら最初からvectorで統一しようかなと
まだ経験少ないので試行錯誤してみます 特に多次元にしたときに顕著だけどarrayの方がvectorより速いし省メモリ 初期値をINFで埋めるとかしたいときは vector でコンストラクタ使うかな それ以外は生配列
array は使う機会ない map の key にする時なんかはvectorよりかarrayのが早いパターンが多い気がする >>769
多次元、速い、省メモリ
試行錯誤する時に意識して使い比べてみます
>>770
int a[100] 例
生配列とarray型を混同してましたが生配列の方です
確かにわざわざarray型を宣言して初期化することは無いですね
ありがとうございました 2次元までの配列ならvector 使うけど3次元以上になると生配列使う
宣言や初期化で文字数が増えるのが嫌 そもそも std::vector と std::array って比較するようなものじゃない気が…… 自分はもっぱらvectorで、生配列もstd::arrayも競プロじゃほとんど使ってないけどそれでTLEやMLEしたことはないし自分が使いやすいほうでいいよ マラソンは定数倍高速化した分だけループ回数増えてスコア伸びるからじゃね
アルゴなら5msのACも1900msのACも変わらんし、AtCoderでC++使っててarrayならギリギリ通るみたいなのはそもそも他の何かが間違ってると思った方がよさそう 定数倍高速化してギリギリ通るの、平方分割的な半分嘘解法など？ ミラー・ラビンとかポラード・ローを使った高速な素因数分解アルゴリズムって競プロでの使用頻度どれくらい？
昨日のこどふぉのCの問題設定が微妙でこの高速な素因数分解アルゴリズムじゃないと計算量的に怪しかった(実際は√nの素因数分解アルゴリズムを定数倍高速化するのでも通るっぽい)んだけど存在を忘れてたせいで解けなかった 自分も解けなかった
自分が解いてきた限りではミラーラビンやロー法じゃないと解けない問題は見たことない
なぜ10^6にしなかったのか謎 高速素因数分解が前提の問題は普通にあるけど AtCoder の rated コンでは出なさそう
Codeforces も基本出さない方針な気がするけど writer の次第だからわからん こどふぉ来週の月曜日までほぼ毎日コンテストあるんだけど過密すぎるでしょ 蟻本4.4章の巡回スケジューリング問題(円環上での区間スケジューリング問題)のソートを除いたO(N)解法って何？
円環を切って2つ繋げて区間にして考えるのかなって思ったけど上手くいかない気もするし元の問題が見つからないから確かめることも難しい 各区間を頂点として、蟻本の解法の中で構築してるnextを辺としたグラフを考えると、なもりグラフになっててサイクルをちょうど一つだけ含む
答えはこのグラフ上のパスで表せる
サイクルに含まれない頂点を含む解を考えると、パスの始点と終点を一つ進めたものも有効な解であることが示せるので、
全ての頂点がサイクルに含まれるようなパスだけ考えればいい
あとはサイクルの上でしゃくとり法みたいなことやればできそう
で合ってるかな……？ しゃくとり法しないでもサイクル上の適当な頂点から始めて極大な解を一つ取れば大丈夫か >>785
確かにグラフ上で考えると求める区間の選び方はサイクルに含まれることが必要で、辺の数=頂点の数と全ての頂点の出次数1から全体としてはなもりグラフ的な感じにはなりそうだからだいたいその方針で良さそうっぽいな
ありがとう D通ったけど難易度高すぎ。E,Fの位置にしとけと。 つーか、Dって
連結がない頂点がある場合、答えは0じゃないよね？
追加したら二部グラフになりえると思うんだけど
このケース考えて完全に迷走した E全域木になるの言われたらそうなんだけど見えなかったし精進が足りて無いのかな
Dは数ヶ月前だったらEに置いてあった気もするしインフレしすぎ >>792
そうだよ
例えば辺が0個のグラフが与えられたとすると、答えはN*2になる D問題
やり方として
・まずは連結グラフに分解する
・連結グラフが3以上だった場合は無理判定をする
・そして各連結グラフ毎に
とりあえず各頂点に黒と白を割り振って、
このグラフそのものが2部グラフになっているかを判定する
2部グラフになっていた場合に、各連結グラフごとに自信が持ってる
反対の色の頂点数-頂点数をanswerに足していく
そして、各連結グラフについては
グラフ1の黒数×グラフ2の黒数
グラフ1の黒数×グラフ2の白数
グラフ1の白数×グラフ2の黒数
グラフ1の白数×グラフ2の白数
の4つを足す
っていう解法を思いついたんだけど、グラフ問題といたことなかったから、各頂点がどの気に属しているかっていう判定ができなかった
俺のやり方、・まずは連結グラフに分解する
さえクリアできテレバこのやり方であっていた？ cまでは10分ちょっとでクリアできるようになったけど、
ｄがここ一か月難しい気がする
酒のみすぎかしら >>796
そう思ったけど、解説にはその点が触れられてない いや、それがあのBとWの入れ替え関数式か。
D解けた人良くここまで計算し切ったね
グラフの計算に二部グラフの計算加えて、
さらに計算式も考えるとかやりきれんよ。 自分は余事象じゃなくて普通に足し合わせたけど、二頂点が異なる連結成分にある場合は後から色を合わせられるから全通りOKっていうのを最初は見逃してた グラフの分解ってどうやるのがいいの？
普通はdfsでグラフは見ていくんだろうけど、
for分で回すのも違うと思うし、unionFindとかで調べることになるの？ おれはUnionFindつかってないよ
まあ使ったほうが見通しが良いなら使ってもいい
2部グラフとして考え、連結成分ごとに2色に塗り分けて、色ごとの頂点の数を数えて、組み合わせを計算して足し合わせた
これだけ 青の人が３完だったらしーからD解けなくても全く問題ない気がする グラフの分解は、
visited[v]: 頂点vを訪問したか
を用意して、for (int v=0; v<N; v++) で visited[v]がFalseなら、
そのvからbfsをして、visitedを更新しながら、色々やる
という方法でやってる
二部グラフ判定なら、visitedは頂点の色の配列で代用できる Nが最大で2*10^5だから、たぶん解法はO(N)だろうとあたりをつける
つまり、おそらく「頂点iから伸ばしてもいい辺の本数」を定数時間で求めさせるのが想定解だろうと予想できる
色々考えると「頂点iから伸ばしてもいい辺の本数」は
(頂点iと同じ連結成分に属している、頂点iと違う色の頂点の数) - (頂点iの次数) + (頂点iが属していない全連結成分の頂点数)
だと求まるから、この総和が答えって感じで解けた >>806
3つ以上あると駄目じゃない？
連結グラフA,B.Cがあったとして
AとBはつなぐことできてもCは繋がらないから全体として2部にならない
って言おうと思ったけど問題文に「追加して得られるグラフ」は
ってあるね
ここも組み合わせが必要になるのか
20万頂点全部が独立したグラフだったら(M=0と書いてるし）
20万×19万9999/2になりそうだな
その場合どうやって回避してるの？ >>808
なんか勘違いがありそう
そもそも連結じゃなくても二部グラフと呼ぶよ みんな当たり前のように解いてて凄えわ
まずは3完出来るようになりたい 今回のはDにしては難しかったし、あんまE問題ぐらいの難度だと認識してよさそうではある
2部グラフの特徴を考えつつ、場合の数を立式して計算しないといけないから、
自分で解いてても、「Dでこんなややこしいことしないといけないの？ 方針ミスったか？」って不安になりながら解いてた Cがたまに解ける程度の参加数回の灰色です
全探索とbit全探索はたくさんやったので次に何をやったら良いか
最初に覚えるアルゴリズムのおすすめを１つか２つくらい教えてください
ちなみにDPは10問くらいやってみたのですが理解が進まず一旦保留してます
DPの初見問題だと何を当てはめれば良いのか分からずコピペ出来るようなものしか正解出来ません >>809
各独立した連結グラフがあったとして、解き方としてはそれぞれの色のパターン4色かけ合わせた解き方をするじゃない？
その組み合わせ数が、例えば全部20万個の点が全てどれとも連結していなくて独立だった場合、
20万から2つの組み合わせを全て調べるっていうようになると組み合わせ爆発が起きるんじゃないかって思ったんだけど >>813
ありがとうございます試してみます
上から順番にやれば難易度的にも徐々に上がってくって認識でOKですか？ >>814
>>808 に書かれてるように N=20万、M=0なら 20万×19万9999/2 つまり 19999900000 になる
答えの数値は大きいけど、計算量が大きくなるわけじゃないから問題ない >>814
>20万から2つの組み合わせを全て調べる
ていうか、そんなことしない
組み合わせ数の立式をしてくださいな >>815
いや、そんなことはないかもです
Union-Findとか累積和はダイクストラよりも分かりやすいと思うので自分のやりやすい順序で埋めてくといいかなと思います！ >>816
んんんん？？
だって連結グラフA,B,Cがあったとして、それぞれの黒点白点を4通りかけ合わせるわけじゃん
結局、ab,bc,caのように 20万C２の組み合わせについて調べないといけないことにならない？？ >>819
vector<pair<long long, long long>> v;
に各連結成分の頂点数 {黒, 白} が入ってると思ってくれ
long long ans=0, sum=0;
for (auto [a,b] : v) {
ans += a*b // 同じ連結成分で違う色の2頂点の組の数
ans += (a+b)*sum; // 違う連結成分なら同色の2頂点も可
sum += a+b; // 見終わったやつは足す
}
あとは既に張られてる辺 M 本引けばいい >>818
ありがとうございます、上から順番にやってみつつ且つ自分のやりやすい順序で埋めてみます >>820
待ってね
Cプラプラ読んだことないから少し理解に時間がかかりそう
読んでみる >>820
なるほど！！
これすごい
そうか、黒、白で分ける必要がなかったんだね そうか。。普通に感動した
競プロの人たちすごいな
愚直にやるやり方しか思いつかなかった5chやっててよかったって今初めて思ったくらい感動しました
ありがとう >>820
ans+=a*b
ここだけわからない
正方形だったらそれぞれの頂点2だから、その計算だと4になるけど、
繋がっていない頂点数はその計算だと求められなくない？ >>825
「繋がっていない頂点」が何を指してるのか分からない
もう少し厳密に書いてほしい
入力が
4 4
1 2
2 3
3 4
4 1
だとして、連結成分は1つだけで白2黒2
>>820のループは1回だけ回って ans は 4
既に張られてる辺数4を引いて答えは0です 二部グラフか判定
連結成分のペアに対して要素の個数の積出す(累積和使う)
連結成分の内部でいい感じな計算
とかやったけど結構コード長くなってしまった >>824
愚直にコードを書いて解けるのはABC-BかCまでで、それ以上の問題は愚直に実装すると問題の制限を超過するからどう工夫するかが問われて応用的になると思っていいよ
ここからアルゴリズムやらデータ構造やらが活躍するんだけど、業務とかで役立つ機会は少ないし(寧ろABC-C以下みたいに愚直に書く機会の方が多い)から役に立たない云々言われることがあるって感じだと思ってる 俺も累積和取る感じでやったけど解説の方がスッキリしてるな >>825
822と計算式違うよ
0だったsumを更新してるだけだよ >>825
あ、ごめんその前の計算式か
まずは実際にありえる辺の総数を求めて、
最後に繋がってる本数を引くって事
例題の場合
白2,黒3だから2＊3がありえる辺の総数になって、
そこから引かれている4本を引くと答えの2本が出る
重複なしとか前提があるから出来る方法だけど
そう言う私もD解けなかったですけどねw c問題で水色とか紫とかがTLE出しまくってるの見ると
何やってるんだと思うよね C問題って間違えようがないと思うんだけど、
どういうところで間違えるんだろう Pythonなら答えの文字列を文字列のまま作るとかすればTLEじゃね なんとなく多重ループ正規表現でやってTLEしても気にしないくらいの寛容性が必要 PythonistはListで保持してjoinする癖を叩き込まないといかんのじゃ(´・ω・`) atcoder probrems をダークテーマにしてると青が紫になるからそれじゃね この競技のレートって絶対評価？相対評価？
レート自体は相対評価に見えるのに、レートに対する評価は絶対評価に見えるのおかしくない？
曲がりなりにもロジックの天才達が作ったシステムなのにこんな欠陥ある？ それは思う。正規分布的なレートの平均が200以下で、プログラマ一般では灰色上でかなり優秀ハズなのに茶色が雑魚という事になっておる。茶色でも一通りのアルゴリズムは使えるハズ。 社長曰くこんな感じだから、安心していいでしょ
https://twitter.com/chokudai/status/1474258242452987907
AtCoderがそのまま役立つ業務ってだいぶ少なくて、
【評価高】は赤まで、
数理最適化・研究開発
【評価中】は青～水まで、（黄もまれに？）
バックエンドエンジニア・機械学習エンジニア
【評価低～評価無】は水～茶色まで、
その他のITエンジニア
くらいがプラス評価になります。関連度が高ければ高いほど高いレートが評価されやすくなり、逆に低いと低いレートですぐカンストしちゃう、って感じ。
評価低に関しては「コードが書けることが保証されてる」くらいのアピールにしかならないです。
https://twitter.com/5chan_nel (5ch newer account) 青色からはバックエンドエンジニアや機械学習エンジニアの適正としても良い評価もらえるってことだ あいつら別にロジックの天才ではないだろ
ガチャガチャパターンマッチしてるだけで嘘投げまくりだし ABCのFまでで機械学習のスクラッチに関係ありそうな問題を見たことない。なんせ連続量の最適化がほぼ出ない。数理最適化詳しくないけど在庫やポートフォリオの最適化など近いのはヒューリスティックで普通の方は見当違いでは。 競プロの問題がそのまま何かの業務に役立つと思ってんのかね
もっと根っこのほうの潜在的な適正を測るのにこそ真価を発揮する競技だろ 実際レートが威力を発揮するのは中途より新卒 AtCoder Companions 使ってみたけど便利だな。 ふと思ったんだけど、全域木の全ての2点間の距離の平均ってどうやって求めたらいい？
全域木が直線だったらめちゃくちゃ簡単だと思うけど、複雑に分岐してたら20万ノードくらいあったら無理かしら？ 全域ってのがよく分からんが、木なら難しくない
総和が分かれば平均は分かるから総和の話をするとして、各辺についてその辺が距離に寄与する分を足せば良い
これはこの辺を消した時にできる2つの木の頂点数の積だから、木DPを1回すれば求まる
O(|V|) >>841
いや、それを憲法のようにずっと変えないのはおかしくない？って言ってるんだが
全体的な底上げがされてるならその限りではないでしょ
2年前の青と今の青って解ける問題が違うよねって話。 レートに対する評価は絶対評価じゃない
解ける問題が多少変わろうが評価は大して変わらなかったってだけ >>848
回答サンクス
木だけど、重み付きなんだよね
計算式がかなり複雑になると思うんだ 重み付きでも難しくないよ まず適当に頂点を選んで、根にする
根からdfsをして、各頂点を根とする部分木のサイズを計算する(nums[v]: vを根とする部分木のサイズ とする)
辺(u,v,w) (頂点uとvを結ぶ、重みwの辺)
が2点間の距離の総和(=sum(dist(u,v)) (1≤u<v≤N))に寄与する量は、
uとvの内、根から遠い方がvなら、w * (N-nums[v]) * nums[v]
根から遠い方がuなら、w * (N-nums[u]) * nums[u] になる
典型だから、ABCに転がってないか探したけど見当たらないな(CFならありそう) とりあえずコード書いてみたわ、こんな感じで合ってるか？
https://ideone.com/oTWtMA kotlin読めないけど、合ってると思う
min(subtreeSize[edge.source], subtreeSize[edge.target])のところが場合分け減らせてて良いね >>850
atcoderの立場として発言してるだけかと。
アルゴリズムの研究者が水色とかあるっぽいし、競プロにフィットしなければ緑以下が普通だろうけど、時間で競ってパズル色も強すぎる競技と、アルゴリズム力は結構離れてると思う。 はてなブックマークのテクノロジーに再帰は遅いって記事が載ってたわ。 >>853
なるほどおおおお
ただ、理解できそうで理解できない
確かにその式だと、平方完成したときに距離がn/2で最大になることがわかりそう。
ただ、なぜx*(N-x)になるのかがいまだに理解できていない。。
確かに遠い方を選べばx = Nにはならないから、0にはならない、これはわかるが。。
例えば直線だった時に最初の根で中点を選んでしまったとき、
根だから当然部分木のサイズはNになり、N回の寄与しかできない
中点だからもっと大きい数寄与できるはずでは。。
混乱してきた。。 https://imgur.com/a/urLR8OE
cdの辺(４)は遠い方だから、dの部分木サイズ２、
つまり2×3だから6
なるほど、、たしかに6回寄与してる。。。しかしなぜN-nなんだ。。
2項定理の基本がわかってないのかな まてよ、なるほど
自分自信を含んだ場合のそれより下の部分と上の部分が何通りあるか、それをどこまで伸ばせるかということか
なるほど、わかりそう 一人で連投すまない
なるほど！！めっちゃ理解した
木構造であっても直線であっても、そのノードが双方向から挟まれてるとしてどの位置にいるかっていうことが一定になるんだね
いや凄いな、典型っていうけどこういうの当たり前に理解してる人たちなのか。。
感動した 理解したかおめでとう！
じゃあ次は全ペアのパスの長さの平均じゃなくて中央値を考えてみてね >>867
サンクス！！
中央値。。。。。
n(n-1)/2通りある中から実態のある中央値を考えるのか
一晩考えさせてください。 >>867
最初に聞かせてほしい
いじわる問題じゃなく本当に求まる？ https://imgur.com/a/kHjv6cK
この場合は8が中央値
2分探索を使うわけでもないし不可能な気が。。 中央値は結構難しいような
中央値だから二分探索を使うというのは良いと思っていて、でも二分探索の判定部分で、
長さx以上のパスの個数 を計算する必要があって、これを計算するのは難しい気がする え、中央値解けるん？
考えたこと無かったわ、やってみるか
重み付きだよね？重み無ければ重心分解して畳込めば終わりだし 自分はそもそも重心分解を知らなかった 正しいか分からないけど、
重心cからbfsをして、各頂点v(1≤v≤N)までの距離d[v]を求めて、各d[v]を座標圧縮してBITに記録する
各d[v]について、d[u]≥x-d[v](1≤u≤N)となるuの数がBITで計算できる (x-d[v]もd[v]とまとめて座標圧縮する)
このままだと重心から見て、同じ部分木に属するパスを含んでしまうから、
重心から見て、vと同じ部分木に属する頂点uについてのみ、d[u]を座標圧縮してBITに記録して、
d[u]≥x-d[v]となるuの数を引く、とかで合ってるかな？ 重心からの距離をソートして頭と尻からそれぞれ見ていけばデータ構造使わなくてもカウントはできる
（結局ソートでlogつくが）
二分探索と分割統治の分を合わせてlog3つになるのかな 確かに 座標圧縮もBITもいらないか
O(N * (log^2)N * log(Nmax(w))) か (重すぎる) あー、なるほど理解した
確かに中央値求まるな……重すぎるけど ちょっと待て待てなんかすごいことになってる
重心分解なんか聞いたことないぞ 重心分解と座標圧縮について調べてみた
重心分解の条件が部分木が全てN/2以下になっているっていうことは、直線の場合が最大でっていう理解であってるよね？(直感的には明らかだけどなぜn/2以下ならといえるのか厳密な定義があれば教えてほしい）
後、画像圧縮も調べてみたけど、これってどういうときに使うものなんだろう 競プロ力って言うか、実務とかのプログラミング力ってどうすれば鍛えられるかな
持ってる知識は同じだとして
基礎体力が強い方が勝つんだろうけど、これってワーキングメモリの保持力だったりするんだろうか 実務とかのプログラミング力、っていわれても環境によって求められるものが違いすぎてなんともだけど、きみがいうプログラミング力ってなんなん？
個人的に「プログラミング力がある」って感じるひとは、それに比例して知識量もあるし、知識が同じなら差がつくとはどうしても思えない
なかには知識は全く同じはずなのにプログラミングすげえ！みたいな天才マンがいるの？
そんな人に出会ったことないし想像できない
というか仮にいたとしても技巧的なコードばかり書いててメンテできなそう 英語鍛えりゃいいんじゃね
今まで見てきた凄腕はみんな英語が達者で情報を日本語以外で取り入れまくってた 英語を鍛えれば有能になるんじゃなくて有能人材は元々英語くらいなら余裕だから因果関係が逆な気もする 競プロでも強い人がこどふぉとかの英語問題文で困ってるの聞いたことないし 例えば高専で、JavaScript, Python をやっていても、
なんだ、Ruby on Rails, Docker, AWS Solution Architect もやっていないのかと、
ウェブ系企業では全く相手にされない
そういう香具師でも、英語さえ出来れば、GAFAM では採用される。
まあ、競技プログラミングもそこそこ出来るし、まあ雇っても良いかという感じ
印象としては、Linux のシステム構築運用できない香具師が、GAFAMに受かる感じ 英語力はchokudaiが既に反例だから違うだろ
英語力がある方が有能だけど
実務とかのプログラミング力はどれだけ色々なことに手を出してきたかだと思うな、凄い奴は経験してる分野が多岐に渡ってて、何聞いてもそれなりに理解してる答えが返ってくる 別にGAFAM受かっているから優秀とは思わないけど、DockerやAWSみたいな個別的な技術の知識より学術的な情報科学に強い人材の方を重視しているから、一見モダンな知識がないように見えるだけなのでは？
そんなの入社後必要に迫られて勉強すればすぐ身につくようなものじゃないか CodeForcesの問題文は謎の登場人物、ストーリーが面倒くさいだけで、別に競プロの問題を抽出して理解するのにそんなに英語力いらない気がするな
英語圏の中学生向けの小説の方が難しいと思うわ >>879
重心探索のアルゴリズムで重心が定まったとき、重心とされた頂点の親の方の連結成分の成分数がn/2以下と言えるのか？という疑問かな？
であれば、重心を根とした部分木の頂点数はn/2より大きいから、親の方の連結成分＝重心を根とした部分木の頂点数はn/2以下になるって感じかな？（全然違う疑問だったら言ってくれ）
あと、画像圧縮と座標圧縮は別物だね
座標圧縮の方が簡単で競プロで頻出 座標圧縮って競プロだと当然のように使われるけど実際に業務とかでも活用されてるのかな(まあ大した実装量じゃないからわざわざ名前をつけてないだけなのかもしれないけど) >>890
あ、
×親の方の連結成分＝重心を根とした部分木の頂点数
〇親の方の連結成分＝重心を根とした部分木を元の木から取り除いた連結成分の頂点数
ね >>891
画像、科学計算分野とかゲーム開発では使うかもしれない
勤怠管理ソフトで使ってるのは聞いたことない 座標圧縮っぽいことは思い出してみると業務で使ったことあるけど座標圧縮だと意識してはいなかった気がする プログラムで活躍としては
センスのみ<知識のみ<<<知識+センス
なんだよ
これで勘違いが起きることが多い
知識のみしかもってないと一見最上なんだけど、実は何も産み出さない
知識のみでも誰かがセンスを持ってると一気に有益なものが産み出される
つまりピースを埋められる存在になれるかどうかで活躍は変わってくる E解けないからFから解いたんだけどFもFで計算量的に大丈夫なのか？って疑ってた最初の方に思いついた解法(ユーザー解説の奴)が他の解法で悩んだ挙句普通に通ったからあまりスッキリしない D計算時間を解決できなかった
配列とコンテナで管理するのが速いのかー。
アイデアはあったけどどれが最適かわかんなかった D、問題文誤読して違うことやってたのにACになってた
（誤答になる入力が存在することは確認済み） (a(b)a)がyesでも通るって話題になってるね yesでも通るというかNoが通らず不正解になると言う方が状況を誤解なく伝えられるんじゃね ABC283
そもそもの難度調整が下手すぎないか？よく考えて作ってるのか疑問 難易度言うならそもそもABCでD以上出さなくていんじゃね
D以上はARCに回せばいい
レーティングも400まででいいよ 黄色以上は解答できなくして賞金も貰えないようにすればいいよ 昔青だった人が水色なんだからビギナーコンテストはmax水色~緑下で十分すぎる AGCって1200無くても受けて良いの？
暇だし受けてみようかな ABC上位中国勢ばかりやんけ
少し前より青→黄の難易度かなり上がってそう >>912
あー、レートつかないのか。なら後日でも良いか 人類の5人に一人が中国人だから。
石を5個投げれば一つは中国人に当たる。 理由はしらんけど、どうやら中国勢は現在のレートが実際の実力に追いついてないひとが多すぎるから
だから中国人がたくさん参加するとパフォがちょっと渋くなるかもしれんなあ 中国って中高生くらいで強い人多いけど競プロの塾とか競プロの中国語の参考書とかもあるのかな この前2012年生まれの中国人の赤いたぞ
年齢詐称じゃなかったらすごいな >>918
塾はあるらしい
情報オリンピックで活躍できたら、好きな大学に入れるから高校生ががんばるらしい
参考書については、おれたしか2008年くらいにICPC対策の英語の参考書みたいなの買ったことあるんだけど、たしかそのオリジナルが中国語だったはず（俺が買ったのは英語に翻訳されたバージョン）
まあ今ならきっとかなりたくさんあるでしょ なんだ塾があるのか。
勉強したらできて当たり前だな。
中国人はしょせん中国人にすぎないな。
↑って、ネトウヨが言い出しそう。 中国なら有り得そうとも思うが同時に詐称も沢山いるしなあ ネトウヨって結局、清和会のために統一教会を支持してる奴らだろ？
国益だの愛国だの言ってるけど、その国というのは韓国のことだろう。 >>923
頭が悪いからパヨクになっちゃうの？
それともパヨクだから頭悪くなるの？ >>925
いまは社会科で習わないのか？
ネトウヨは自民党清和会、つまり韓国朴正煕派閥。
パヨクは社会党、つまり朝鮮総連派閥。 >>926
最近のネトウヨは嫌韓じゃないのか・・・
清和会のせいでややこしいな >>927
金大中暗殺未遂事件とかも習わないのか？ >>927
元々ネトウヨを作ったのが韓国人だろ。
いいように操られやがって。 統一教会は日本で、ゆとりある教育を提唱しているが、韓国では全く逆のことを言ってるからな。
騙されるなよ。 三角関数は高度な数学じゃないぞ。
全員が知っていなければならない基本的な算数だからな。
統一教会派の国会議員に騙されるなよ。 前の二つの状態を持つDP、前日のABCでもあったのにDPしなくても掛けていけば求まると迷走して1完遅解きだからダメダメだ
Bもどう実験すれば思いつけるのか タイムリーだね
すぬけさんやtouristいなかったら本当に中国勢が強い
横綱さんもかなりすごい chokudaiも3000の実力ないとか言いながらしっかり34位か すみません、くんerですけど明日からこっち書き込みます もしngしたかったら
1週間毎にｵｯﾍﾟｹ Sr1f-v7GxのｵｯﾍﾟｹSr以外の部分をngお願いします(前2桁はよく変わるので) 今の日本の若い人って頑張らないし甘やかされてるしそりゃ全体的な競争力低くもなるわ 競争力を上げるためにはもっとスパルタにせねば、とお考えなのですね >>948
スパルタにすると諦めるからどのみちだめ >>954
詳しい経緯は話してないけど、少し前のツイートで「ICPCのメンバーとは決別した」って言ってたでしょ
今日も練習すっぽかしたって自分で言ってるしチーム内でうまく言ってないんじゃないの 初心者なのですが
ABC262BをACLのDSUを使って解くことは出来ますか？
解説などでは全く使ってなかったので
そもそもの方針が間違ってるのか知りたいです
https://atcoder.jp/contests/abc262/tasks/abc262_b 路じゃなくて辺が存在すればいいからDSUを使う意味がない さっき考えついた問題
はじめ、頂点1つの根付き木（当然その頂点が根）がある。これからN-1の頂点をこのグラフに以下の手順で一つずつ追加する：
・P/Qの確率で新たに加える頂点を根とした新たな根付き木を追加する。辺は加えない。
・1-P/Qの確率で、既にグラフに存在している頂点の一つを一様ランダムに選び、その頂点の子として新たに頂点を加える。
なお、帰納的にこのグラフは根付き木の森になる。このとき、以下の期待値を求めよ。
・根付き木の頂点数の平均値
・根付き木の頂点数の最大値
・根付き木の高さの平均値
・根付き木の高さの最大値
それぞれどの程度の制約でできるか。 >>959
まあちょっと下のやつを見るのが1番楽しいからな >>957
グラフやDSUなど全く理解出来ていない質問でしたすみません いえいえ！全く問題ないです！
色んな解法の解き方を考えると理解が深まるのでいいと思いますよ >>960
これ、できた森ごとに平均とったり最大取ったりするって話だよね？
例えば、頂点数が3の木が2つ、頂点数が2の木が1つの森ができたという状況なら、平均は8/3、最大は3みたいな
一番上はO(N)だけど、他はすぐにはよさげな方法が思いつかないね 例えば二個目だけど、f(n,m,k)をN=n、最大頂点数m、根付き木数kである確率として、f(n,m,k) = Σ_{i<n/m} Σ_{j<n} 何かの係数 * f(n-im,j,k-i)みたいな風なDPだったりするかね？ 1つ目の問題、操作後の木の数の期待値が1+((N-1)P/Q)個で頂点数がN個だから木の頂点数の平均はNQ/((N-1)P+Q)じゃね？って思ったけどもしかして俺トンチンカンな事言ってる？ ｵｯﾍﾟｹ Sr1f-v7Gx
ﾜｯﾁｮｲ 477c-It8h
金玉民はネットWatchにでもスレ立てて勝手にやっててくれ >>967
一般にE[1/X] != 1/E[X]なので、それは成立しないかも？
あ、でも、自分のO(N)解ってp = P/Qとして、
Σ_i p^i (1-p)^(N-1-i) comb(N-1, i)/(i+1)を計算するってやつで、積分使えそうな形だからO(1)でもできそうだね NGでいいでしょ
結局前の板でもネトスト辞めさせられなかったし てか、積分がどうのみたいな話もいらなくて、
N Σ_i p^i (1-p)^(N-1-i) comb(N-1, i)/(i+1)
= p^(i+1) (1-p)^(N-1-i) comb(N, i+1) / p
= (1-(1-p)^N)/p
かね
なんかすごく有名な話から自明に導かれる気がするけど思いだせない まあNGしてスルーしとけばいいんじゃないかな
ありスレは考えようによっていろいろな荒らし対策ができるので こいつ俺と考えることが全く同じで気持ち悪いな 黄溜りだろ 典型性高めの話なので、レベルが近かったら自ずと似たようなこと考えるんじゃないかな >>964
>これ、できた森ごとに平均とったり最大取ったりするって話だよね？
>例えば、頂点数が3の木が2つ、頂点数が2の木が1つの森ができたという状況なら、平均は8/3、最大は3みたいな
その認識であってる ありがとう
てかO(logN)だね、普通にlogは定数をやらかしてた 自分もこの前問題思いついた(既出かもしれない)んだけど、
N個の区間が与えられて、Q個の区間変更クエリに対して毎回区間スケジューリング問題を考える(重ならない区間の数の最大値を答える)って感じの問題なんだけど、これってN、Q≦2×10^5でも出来るかな？
区間に重みが無い場合は差分考えればいけそうな感じもするけど重みがつくと流石に厳しい？ どういう更新をするのか分からないけど、重み無しは解けない？
左からの区間スケジューリングと右からの区間スケジューリングを前計算しておけばいけると思う
重み有りの区間スケジューリングは自分は初めて聞いた 更新無しだとセグ木+DPとか？
重み有りでも左と右から前計算しておけば解けそうだけどなあ あーでも、更新クエリで区間が全然違う場所に移動することを考えると、前計算の意味ないか
嘘解法だった 重みありの区間スケジューリングは端点で座標圧縮してイベントソートした上でDPすれば解ける(蟻本のintervalsっていう問題のk=1の場合でも紹介されている)
一応クエリはオフラインでも可能なものを考えてたんだけどどうだろう ここに業務で詰まってる課題を投げれば解いてくれるって聞いたんですが本当ですか？ chatGPTに投げるとあと一歩で動きそうに見えるコードを書いてくれる あっち荒されてるからやっぱこっちでくんの話題します😭 >>987
ネトストガイジはネットWatch板に自分で巣を作ってどうぞ ガイジスレも政治スレになったから避難所としてここにいるしかないな
自治erもこのスレに移住させたがってたししばらくはここでいいんじゃないか？ 知らない人向けに説明すると、この「くんer」というのはプログラマー板の方で特定の競プロerにずっと粘着し誹謗中傷を繰り返していたやつで、IDなしスレだったのをいいことに自演連投していた疑惑が濃厚 くんerは結構いるっぽいぞ
twitterですら3‐4人見たことあるし
何が楽しいんかね 競プロスレで何が楽しいのかねはブーメランすぎるだろ そんなこといっても話題にしちゃうやつがいるから、別板の競プロスレでは困ってた
でもここならワッチョイのおかけでそれほど騒がれないだろうから比較的大丈夫かと atcoderのABCのBやC問題までの話ですが
提出で他者のコードと違いが無いのにほぼ毎回5ms前後差が付くのは誤差なんでしょうか？
例えば最速の1msのコードをコピペして提出しても差が出ます
特にテストケースの1つ目が極端に遅くて例えば10msで
それ以降は全て1msか2msなのに1つ目が10msなので結果が10msになってしまいます
気にするレベルでは無いと思いますが素朴な疑問です 競プロの実行時間にはある程度誤差がつくよ
だから時間制限ギリギリのコードが誤差で落ちないように、TLEが出ても内部的には3回ジャッジし直してる
あと最初のケースだけ遅いというのもよくある（立ち上げ時のオーバーヘッド？） このスレッドは１０００を超えました。
新しいスレッドを立ててください。
life time: 87日 9時間 22分 12秒 5ちゃんねるの運営はプレミアム会員の皆さまに支えられています。
運営にご協力お願いいたします。
───────────────────
《プレミアム会員の主な特典》
★ 5ちゃんねる専用ブラウザからの広告除去
★ 5ちゃんねるの過去ログを取得
★ 書き込み規制の緩和
───────────────────
会員登録には個人情報は一切必要ありません。
月300円から匿名でご購入いただけます。
▼ プレミアム会員登録はこちら ▼
https://premium.5ch.net/
▼ 浪人ログインはこちら ▼
https://login.5ch.net/login.php レス数が1000を超えています。これ以上書き込みはできません。
