競技プログラミング総合スレ 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/06(土) 23:12:36.78

Eは昔六問ABCでFの位置に置かれてた問題に似てるな
やっぱりちょっとずつ問題のレベル上げてる？

2022/08/07(日) 14:06:05.87

Eをmodとった値になんの意味があるのかｗｗｗ
近似値で良いじゃん

2022/08/07(日) 14:29:12.18

業務でも浮動小数の誤差が嫌なときは確率や期待値に素数のmod取ったりするよ

2022/08/07(日) 22:33:12.42

シミュレーションとかでものすごく小さな誤差も気になるときには実際有理数体と有限体のどっちが取り回しがよいんだろうね
そういうのやったことない

2022/08/09(火) 13:47:59.34

トヨタでのバイト、AtCoderとして受託して業務提携でプレスリリースを出すみたいなことはできなかったんかね
いい実績作りな気がするけど

2022/08/09(火) 19:25:34.31

社長がいなくても回るんならもう副社長が社長でいいやん

2022/08/10(水) 14:57:40.38

AtCoderが受託開発を始めるのはちょっと違うでしょ

2022/08/12(金) 09:27:10.43

アは役！証明できるじゃん

2022/08/12(金) 09:27:31.49

アルゴリズムは役に立つ！

2022/08/13(土) 23:00:37.57

今回は前半の方がいつもより難しめで後半の方は簡単め？

2022/08/13(土) 23:09:04.86

自称ユーザー解説については、コンテスト中に書いて終了後即座に提出したか、testerが書いた（writerじゃないから非公式という認識？）みたいな感じじゃないか

2022/08/13(土) 23:18:52.37

切断クエリを逆順に見てUnionFindによる結合に読み替えるやつ本当にABC-Eって感じのテクニックだな

2022/08/14(日) 00:07:55.47

今さらだけどchokudaiが忙しい理由ってトヨタのアルバイターだったからか

2022/08/14(日) 15:11:07.66

0012 仕様書無しさん 2022/07/02(土) 21:05:02.67
prog：プログラマー［重要削除］
https://ace.5ch.net/.../saku2ch/1032017835/

230 上奥　龍 (ﾜｯﾁｮｲ d58e-sbT5 [182.171.118.130]) mistery0817@gmail.com 2022/07/01(金) 13:06:33.82 ID:9RE/ovUm0
対象区分：［個人・三種］優先削除あり
削除対象アドレス： https://medaka.5ch.n.../prog/1655625352/811
https://medaka.5ch.n.../prog/1655625352/813
https://medaka.5ch.n.../prog/1655625352/861
削除理由・詳細・その他： 811番のレス・813番のレスに対しては[個人名・住所・所属]の二類に属する情報が掲載されているため、削除申請を行います。
861番のレスに対しては[個人名・住所・所属]の三群に所属する情報であると考えていますが、
インターネット上のURLが掲載されている状況です。
そのURLには、個人名並びに私の昔の写真が掲載されております。
しかし、スレッドの議論の状況から誹謗中傷の個人特定が目的である情報であると考え、削除申請をさせて頂きます。

以上3点のレスが削除申請を行うものになります。よろしくお願いします。

231 Dele Ace ★ 2022/07/01(金) 16:49:02.69 ID:CAP_USER
>>230
見ました。
URLリンク先に問題がある場合はリンク先に削除を依頼して下さい

958 仕様書無しさん 2022/07/02(土) 19:03:13.41
>>894
ご尊顔
https://www.ds.shiga.../news-faculty/p7102/

2022/08/15(月) 00:10:08.26

1完ちょっと早め解きでおそらく微減...
でもまだARCどころかABCですらギリレート上がる範囲だから悲壮感はない🤗
よくやったほうだ😎

2022/08/15(月) 00:13:42.71

B方針は割と合ってる😭

2022/08/15(月) 00:15:58.63

もう政治の話する人と金玉ネタ擦ってるキッショい誘導しかおらんのか

2022/08/15(月) 00:27:35.29

AGCはやっぱり赤コーダー用コンテストだね

2022/08/15(月) 00:34:12.32

ABが解けて2800-2000だから
黄青にはいい難易度だった

2022/08/15(月) 00:43:08.18

180分のコンテストでB早解き競争ってしょっぱくない？

2022/08/15(月) 00:44:28.68

ああ、青だと確かにそうか

2022/08/15(月) 00:45:29.88

競争っていうほど簡単じゃないぞ・・・悔しい

2022/08/15(月) 10:28:16.89

アドホックで難しくて分かれば綺麗に解けるような問題が都合よく無尽蔵に作れる保証はない以上、AGCもそのうち考えたことがあるor見たことがある勝負に帰着するのかもな

2022/08/15(月) 10:50:14.74

遂に異常精進erが黄色止まりじゃなくなる時代なのねん

2022/08/15(月) 22:34:51.82

情けない話だが AGC より ARC, こどふぉ、インドのが楽しい

2022/08/20(土) 20:32:01.58

3-5-6-8-8-12か
なんとか四完したいなー

2022/08/20(土) 23:31:30.88

四完どころか二完遅解き…
Cで玉砕しました…

2022/08/24(水) 15:11:08.87

・｢1万時間の法則｣の元ネタ（被引用数: 9847）、再現されず。むしろ、一番上手なグループは累積練習時間が少ない傾向

競プロer的にはやっぱこれが大きいな

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の定式化は自明でソルバに突っ込んで解いた人もいるらしい