競技プログラミング総合スレ 63

2021/07/28(水) 21:58:48.02

!extend:checked:vvvvv:1000:512
↑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/

※前スレ
競技プログラミングにハマるプログラマのスレ 62
https://medaka.5ch.net/test/read.cgi/prog/1626625368/

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

2022/08/24(水) 20:34:14.85

山上義士の話ししてええか？

2022/08/25(木) 09:21:20.76

山上徹也の話だったらしていいよ

2022/08/26(金) 13:34:27.44

政治erもみんなこっちにこないとダメそうだな・・・

2022/08/26(金) 13:37:09.06

ホモラーも来たら面白くなるな😄

2022/08/26(金) 17:28:13.38

こっちならワッチョイでNGすれば1週間は見えないからありがたい😎

2022/08/27(土) 20:53:33.09

ABC出ます

2022/08/27(土) 22:52:05.61

Exって一種の実家DP？

2022/08/27(土) 23:11:30.79

二次元セグ木、存在は知ってるけど実装したことないやつだ

2022/08/27(土) 23:56:20.02

競プロから離れろ
俺なんてアンレで下がっても得したわくらいにしか思わん

2022/08/27(土) 23:56:46.49

間違えてワッチョイスレにくんの書き込みしちゃった😭

2022/08/28(日) 00:15:41.43

なんの問題ですか(レ)

2022/08/28(日) 00:50:07.66

アンレでやらかしたらむしろ得したって気持ちにならねえか？

2022/08/28(日) 15:45:18.47

のしゆたかへので一位争い？

2022/09/03(土) 22:43:13.85

２冠、難易度上がりすぎて長年維持してた緑脱落しそうｗ

2022/09/03(土) 23:11:31.53

Eってにぶたんが想定なのか・・・
ヒープ使って貪欲にやるほうが自然じゃない？

2022/09/03(土) 23:22:04.35

どうせこんなん二分探索でしょ(ﾍﾗﾍﾗ)って感じで半端な考察でコーディングしてたら、別に小さい順にとって全然問題ないことに気づいて結局ヒープ貪欲になったな

2022/09/03(土) 23:28:55.16

まあたしかに、最大値の最小化だからにぶたんぽい、って思えるか
おれは実験してたら貪欲でいけるってすぐ気づいてしまった

2022/09/03(土) 23:47:53.39

(コスト,インデックス)の配列のヒープでやってたけど中に手を入れられない事に気づいて２分探索にして時間切れ・・・

2022/09/03(土) 23:58:51.45

更新があったらpushすればいいだけ
更新前の残りカスがpopしてきたら枝刈り
要はダイクストラと一緒

2022/09/04(日) 00:14:55.13

C++ でいう std::set を持ってくれば中に手を入れられるので……？

2022/09/04(日) 00:20:53.96

ニブたんのイラストが欲しいところ。

2022/09/04(日) 00:28:12.08

G蓋を開けるとそんなに捻りがあるわけでもない挿入DPだな
なんで思い付けなかったんだろう

2022/09/04(日) 13:03:27.94

最近昔よりARCが解けない気がするし、いよいよ俺も過学習erかぁ～？って状態
頭が悪いのはどうしようもないからあきらめてるけど、CF div1過学習とかでARCはなんとかできる？

2022/09/04(日) 15:34:08.14

https://ideone.com/JtsEhf

これは以下の問題の解答として書いたものですがパスしませんでした。
どこが間違っていますか?

https://atcoder.jp/contests/dp/tasks/dp_g

2022/09/04(日) 15:35:21.26

トポロジカルソートを使っています．

2022/09/04(日) 15:37:44.90

深さ優先探索でのグラフの点への後行順のリバースオーダーがトポロジカルオーダーになるので，
それを利用しています．

2022/09/04(日) 15:42:05.58

ところで，アルゴリズム専門の大学教授が参加したら強いと思いますか？

2022/09/04(日) 15:43:12.14

むしろ、東京アルゴリズム専門学校を設立すべきでは？

2022/09/04(日) 15:45:32.52

Erik Demaineとか強そうじゃないですか？

2022/09/04(日) 15:49:41.68

>>628
次数が0の頂点からdfsを始めないとqがトポロジカル順にならないかな
あと、PythonとかPyPyなら
import sys
sys.setrecursionlimit(10**5+10)
とかを書かないとREになるよ

2022/09/04(日) 15:53:52.62

>>634

ありがとうございました．
その再帰のリミット設定を追加したらパスしました．
プログラム自体は変更しなくても大丈夫でした．

2022/09/04(日) 16:04:24.00

後退解析チックなトポロジカルソートしか知らないからそういうトポロジカルソートのやり方は知らなかった

2022/09/04(日) 16:09:15.88

>>633
強い人はめちゃくちゃ強いだろうけど、全般的にそうかは微妙かな
年齢も大きい
アルゴリズムの有名な実力のあるおじいちゃん研究者がこどふぉ水だったりするし

2022/09/04(日) 16:35:59.36

ARCはまだ訓練でどうにかなるレベルらしいから、気長に難問に取り組むのがいいんじゃないか
知らんけど

2022/09/04(日) 17:36:16.96

>>637

確かに人によって全然違うでしょうね．
極端な場合，プログラミングをやったことがないという人さえいるみたいですし．

2022/09/04(日) 17:48:11.72

みなさん，アルゴリズムの本はどんな本を読んでいますか？

クヌース
CLRS
セジウィック＆ウエイン
Kleinberg & Tardos

何かおすすめの本はありますか？

2022/09/04(日) 17:58:28.50

Cormen

2022/09/04(日) 22:31:48.58

超高速グラフ列挙アルゴリズム－〈フカシギの数え方〉が拓く，
組合せ問題への新アプローチ
ERATO 湊離散構造処理系プロジェクト・湊真一、2015

計算時間が何百億年も掛かるのが、数秒で解けた
「おねえさんの問題」で有名な、
湊真一の超高速グラフ列挙アルゴリズム ZDD

プログラミング・コンテスト・チャレンジブック、第2版、2012
3人の大学院生が、様々なコンテストの問題を集めたもの。g++ 用のC++

オライリーの「入門データ構造とアルゴリズム」は、インド人の著者

他にはセジウィック、石畑清、川中真耶など

2022/09/04(日) 23:20:29.56

ARCダメだった…

2022/09/05(月) 00:14:34.73

コルテの組合せ最適化の評判はどうなんですか？

2022/09/05(月) 16:51:34.75

>>641

ありがとうございます．CLRSですか．第4版が出ましたね．

>>642

『超高速グラフ列挙アルゴリズム』ってトンデモ本ではないんですか？

>>644

その本って，高級な話題を扱っていそうですが，競技プログラミングに結びつきますかね？

2022/09/05(月) 17:51:08.42

こんなところで聞いても灰しかいないぞ
赤か橙に直接聞け

2022/09/05(月) 18:54:43.43

>>645
コルテ組合せ最適化の内容に関して言うと、LP、フロー、マトロイドはじめ、競プロサイトの中でも知識が要らない方と言われているAtCoderでもそれなりに見るような話も結構扱っているように見える
ただ、それらをコルテで勉強するのがいいのかはちょっと自分はよくわからない

2022/09/05(月) 21:57:07.54

在庫管理系の面接受けたけど、競プロと関係なさすぎて。簡単な最適化くらい出せば良いのに。

2022/09/06(火) 19:20:46.62

業務はアルゴリズムとか関係ないからな
プログラマの仕事は基本的にデータベースの出し入れだけ
でも業務知識や設計はなかなかバカにできない難易度だな

2022/09/06(火) 21:25:40.57

いや、アルゴリズム、数理最適化使うんだけどatcoderパズルが的外れすぎて役に立たない。線形計画もラグランジュ法も出さないで何がアルゴリズム人材だと。

2022/09/06(火) 22:19:18.14

まじで！？AtCoder役に立たないの！？

2022/09/06(火) 22:46:39.84

問題にもよるけど昔より難易度上がってるし一般的な業務だったら灰色上くらいで、アルゴリズムっぽいのでもせいぜい茶色くらいまでかと。数え上げとかmod,xorなんちゃらみたいなのがなければもっと上まで役に立つ可能性があるといっても良い気がする。精進は時間の無駄と考えて気楽に参加してる。
AHCのほうはかなり役に立つと思う。

2022/09/06(火) 22:51:12.89

線形計画法の問題とか考察つまんなそう

2022/09/06(火) 23:14:40.13

線形計画はよく出てるじゃん

2022/09/07(水) 00:40:38.30

普通にLP解いたりラグランジュ双対とったりする問題は頻出だと思うけど
同じ数理最適化でもニュートン法とかもっと機械学習っぽい連続最適化問題出せみたいな話は分かるが

2022/09/07(水) 00:48:11.56

ただその辺はABC-GとかExとかARC-C以降とかに放り込まれているから、数論や組合せ論系の問題が元から得意じゃないとそこで阻まれてたどり着きにくいというのはそう

2022/09/07(水) 01:27:40.63

え、脳死でソルバーに突っ込んで解けるのがG以降にあるの？
だとしても普通に最適化系の科目をで履修中の人が解ける3-400点程度に押さえてCDあたりで出すべきかと

2022/09/07(水) 02:44:08.46

>>657
いや、さすがにそんな脳死解法が想定解の問題はいくらABCでも後半じゃ出ない
https://atcoder.jp/contests/abc216/tasks/abc216_g
例えばこれは数列をうまく変換して条件言い換えるとLPが出てきて、その双対LPが最短経路問題になってるからダイクストラ法で準線形に落とせるって問題
ソルバーに投げず別のアルゴで解けるようにしないと通らないし、また、LPに帰着させる部分が大体非自明なのがAtCoderで出るLPの特徴
一方、本当に一目でLPだとわかり、脳死でソルバーに投げればいいタイプのLPをABC-Cとかに出せって話もわからなくはない
個人的にはつまらない問題だと思うけど教育的ではある

2022/09/07(水) 03:01:49.65

そもそもAtCoderのアルゴの方のコンテストだと確率的に正解になる解法はコンセプト上想定解にしにくいから、脳死LPが出てくるとしたらソルバーに投げるんじゃなくて普通に頂点全探索が間に合うような問題になるかな
二次元ですら実行可能領域求めるの結構大変だから、ABC-Cで出すとしたらかなりかなりわかりやすい凸多角形にする必要がありそう

2022/09/07(水) 03:03:03.88

ARC128-CのLP感好きだよ

2022/09/07(水) 03:05:01.25

あ、確率的に、というのはTLEの方の話ね

2022/09/07(水) 10:36:39.59

ABC-Cに虚無LP入れたら荒れそうだな
崎になにか教育コンテンツで啓蒙した方がよさそう

2022/09/07(水) 12:43:39.65

2021年以降のARCみたいな問題て他にどこで練習すれば

2022/09/07(水) 16:13:49.50

https://atcoder.jp/contests/abc087/tasks/arc090_a
にある
左上および右下のマスにもアメが置かれており、あなたはこれらのマスに置かれているアメも回収します。
ってどういう意味？
単純に通ったマスの飴だけとったらACになったんだけど、問題の意味が分からんかった

2022/09/07(水) 16:33:40.95

スタートとゴールも移動中に通ったマスとみなす

2022/09/07(水) 16:39:19.33

そういうことかありがとう

2022/09/07(水) 18:24:50.65

>>664
確かに一瞬、意味が取れなくて(i,j)を通ったら(i-1,j-1) or (i+1,j+1)の飴も回収できてますよ、的な話かと思ってしまった
(1,1)と(2,N)の飴も回収しますとか書いた方が紛れが少なそう

2022/09/07(水) 18:25:54.23

>>663
これは俺も気になる
相性が悪いのかもしれないけど、かなり難しくなってないか？

2022/09/07(水) 19:18:51.47

競技プログラミングの問題には人間の作者がいるので，それほど独創的な問題を量産できるとは思えません．
とすると，ある程度の訓練を積んだ人間にとっては，同工異曲な問題群に見えるのではないか？

と考えたのですが，あっていますか？

2022/09/07(水) 19:25:51.03

そらそうだよ
数オリだろうが過去問たくさん練習すれば解ける確率上がるからね

2022/09/07(水) 19:40:51.71

数学オリンピックの問題はおそらく数学者が作っていると思いますが，AtCoderの問題は学者が作っているわけではないですよね？
だとすると，問題の独創性はかなり低いのではないかと推測しますが，あっていますか？

2022/09/07(水) 20:11:10.05

さすがにAGCとかになると作問者もかなりハイレベルだし既出かどうかをチェックする体制などもあるのであまり関係ないと思いますが、作問者じゃないしわかりません
そんなに気になるなら高橋社長に聞いてみたらどうですか
TwitterでもYouTubeでも匿名で質問しても回答をくれますよ

2022/09/07(水) 20:12:27.65

AtCoderの出題者は今のところ、一般の学生、たまに会社員って感じではありますね

2022/09/07(水) 20:22:49.29

別にそんなことはないよ
ABCは典型問題だらけだけど、AGCはかなり独創性の高い問題を出すことを志向している
そもそも数学者としての能力と競プロの独創的な問題を作る能力はそもそも微妙に違う、良くも悪くも
もちろんAGCすら世界10位以内とかのクラスから見たらパターン見えるのかもしれないけど、大体の人だと二十年頑張ってもパターン学習できないと思う

2022/09/07(水) 20:23:20.87

>>674
あ、これは>>671へのレスね

2022/09/07(水) 20:28:55.80

数オリ勢の成績見た感じIMOとAGCだと多分AGCの方が難しいと思うんだけど、実際のところどうなんだろう

2022/09/07(水) 20:31:50.41

ABC224HなんかはLPの定式化は自明でソルバに突っ込んで解いた人もいるらしい

2022/09/07(水) 20:55:25.96

>>677
これソルバ解けるのか、思ったよりLPソルバ優秀だな…
というか想定解の双対とってMCFもかなり見えやすい問題だ

2022/09/07(水) 20:57:18.48

AGCも問題にバラツキあるから、ハッキリとは言いづらいけど、
全年齢対象なのになかなか全完が出ないAGCのほうがやっぱ難しといえるんじゃない？

ちなみに今年の数オリは中国からの参加者は全員が満点を取ったらしい
簡単だったのかな

2022/09/07(水) 22:38:04.79

赤コーダーともなれば数学者と変わらんだろ

2022/09/07(水) 23:09:32.31

赤を褒めてるのか貶してるのかわからんな

2022/09/08(木) 00:50:08.86

chokudaiも以前に何かの放送で、新しい問題つくるのがほんと大変だって言ってたな

2022/09/08(木) 01:10:26.92

うんち

2022/09/08(木) 01:10:36.47

あっスレ間違えた

2022/09/08(木) 16:53:49.09

E8くんなにするんだろう
新書籍発売？
新コンテストサイト公開？

2022/09/08(木) 16:56:30.24

まあ大概学問もパターンゲーじゃないか
むしろアドホックな考察力が求められる分野の方が少数だと思うね

2022/09/08(木) 17:47:01.03

典型90の本じゃないのかな

2022/09/08(木) 18:28:42.75

あれまだ発売されていなかったのか

2022/09/08(木) 19:37:15.04

>>687
なるほど、そういえば発売まだだったのか
確かにそれが一番可能性高そうだな

2022/09/08(木) 21:04:16.55

E8くんって最近コンテスト出てない？
前のAGC見かけなかった気がするな

2022/09/09(金) 03:58:24.24

E8くん、すごい執筆速度だ
このアウトプット力は素直にすごい
ただ、やっぱりABC-ratedが対象読者みたいで、暖色を押し上げる本は相当難しいんだなと

2022/09/09(金) 11:34:36.68

新しいE8本、俺はヒューリスティックできないからその部分は読もうかと思う

2022/09/09(金) 13:43:54.42

ヒューリスティック蟻本誰か出して🤗

2022/09/09(金) 14:01:12.69

蟻本の著者でもあるwataさんが書いてるこれの解説を読めばよくね？
https://atcoder.jp/contests/intro-heuristics

2022/09/09(金) 14:14:38.24

これ普通に知らなかった
感謝です

2022/09/09(金) 14:21:03.62

でもこのPDF、ビームサーチの解説が「後で追記」のままになってるな・・・
chokudaiに通報したほうがいいね

2022/09/09(金) 14:25:44.31

競技プログラミングをやっている人で強い人でも、アカデミックな匂いのしない人
が結構いるように思います。

2022/09/09(金) 17:13:05.72

学者じゃないから、そりゃいると思うよ
数学や情報科学が得意な人も少しいるゲーマーコミュニティってだけで

2022/09/09(金) 17:33:18.01

暖色向け本の話だけど、今のAtCoderで黄色より上に上がるのに別にそんなに知識って寄与しないイメージ（というか知識だけならみんなもう持ってる層での競争）で、こういうデ/アの知識を入れた方がいいとか、知らないデ/アの知識を手に入れるにはどうしたらいいのかみたいな話はあんま”本質”って感じがしないんだよな

2022/09/09(金) 18:51:34.08

12年前に蟻本出したってよう考えたらすげえことだな

2022/09/09(金) 19:03:35.57

何がすごいんですか？

2022/09/09(金) 19:17:01.85

競技プログラミングは独創的な問題に価値を見出しているから、年々新しい問題がたくさん作られているんだけど、未だに12年前の本が中級者（ここでは水～黄ぐらい？）向けの本としては定評があるから

2022/09/09(金) 19:22:06.29

蟻本って、プログラミング・コンテスト・チャレンジブック、第2版、2012 の事か

色々なコンテストから、3人の東大大学院生がまとめた本でしょ。
ほとんど全てのアルゴリズムを網羅している

言語は、g++ 用のC++

読んだ感じ、すごい学生達だと思った。
商売はアイデア。これはニーズがあるから売れると思った

2022/09/09(金) 19:22:54.76

まあ蟻本の知識的な内容を全部理解しててもちゃんと考察力がないと橙にもなれないと思うけど

2022/09/09(金) 20:00:57.21

>>702
独創的な問題といっても，アルゴリズムとデータ構造の本に書いてある知識で解ける問題ですよね？

みなさんはアルゴリズムとデータ構造の本を読んで勉強しますか？