競技プログラミング総合スレ 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/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
独創的な問題といっても，アルゴリズムとデータ構造の本に書いてある知識で解ける問題ですよね？

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

2022/09/09(金) 20:05:14.26

ある一定レベル以上行くと要求知識と難易度ってそんな関係ないんだよね
小学生でも理解できる単純な貪欲アルゴリズムが解法の問題が永続赤黒木を要求する問題より難しいということがままある

2022/09/09(金) 20:06:03.79

解けないよ
小学校の計算ドリルじゃあるまいし

AGC解いてみればわかると思うけど、知識は大前提で、それ以上に閃きみたいなのが必要
つまりアルゴリズム知識問題というよりは、どちらというとやたら頭を使うパズルやなぞなぞといったほうがいい

2022/09/09(金) 20:11:55.82

AtCoderに関して言えば、正直、ABCの問題（Exまで）や典型90を解いて蟻本を読むだけでもほぼ知識的には網羅できていて、学術的なアルゴリズムとデータ構造の本を読む必要性があるかというとそこまででもない
ただ、アルゴリズムとデータ構造を題材としたゲームをやっているので周辺知識に興味がある人も多くいて、趣味で勉強している人は結構いる雰囲気
学術的じゃない人もいるけど、学術的なことが好きな人も他より多めだと思うので、そういう人と話してみたら面白いのではないかな

2022/09/09(金) 20:34:07.29

アルゴリズムとデータ構造の網羅性のある教科書の知識があれば知識面では十分問題が解ける水準にあると思う
ただそれには前提があって、発想力がないといくら知識があっても解けない（そしてここの要求水準が結構厳しめ）
って感じかね

2022/09/09(金) 20:37:14.53

そうだよ
AGC解いてみろよ
AGCでも、AとかB問題ならアルゴリズム知識すら不要で、発想力のみ問われてるようなのが多いぞ

2022/09/09(金) 20:48:11.75

何十年考える時間与えられても解けない自信あるわ

2022/09/09(金) 20:50:30.48

>>705
AtCoderの社長のchokudaiとかは、アルゴリズムイントロダクションを昔読んでたね
競プロで強くなるために最適な道かは知らないけど、読んでる人はいっぱいいると思う

2022/09/09(金) 20:53:37.03

好きな、覚えたてなコンピューター言語その他を使ってやるブラゲーっと思ってやってみた。
https://www.youtube.com/watch?v=Z9ki00Z5SWg&list=PLirT2ByBZWrNT1tlKZy2uAFRsaEc9KEEe&index=13

任天堂の“絶対に挫折させないプログラミングゲームUnreal Emgineみたいなノードだけど、Unreal Engineでいいんじゃないかと思った。
https://www.youtube.com/watch?v=Z9ki00Z5SWg&list=PLirT2ByBZWrNT1tlKZy2uAFRsaEc9KEEe&index=13

2022/09/09(金) 21:42:10.67

>>705
試しに解かなくてもいいけど、このへんの問題を考えてみ
AGCの中では破格に簡単な部類の問題だよ
https://atcoder.jp/contests/agc056/tasks/agc056_a
https://atcoder.jp/contests/agc021/tasks/agc021_a
https://atcoder.jp/contests/agc053/tasks/agc053_a

アルゴリズムの知識なんて全くいらないし、アルゴリズムの参考書なんてほとんど役に立たないよ

2022/09/09(金) 21:45:01.95

10^8回以上のループを書いてしまったら、実行時間制限に引っかかりそう

っていう程度の知識はいるけども

2022/09/09(金) 21:51:15.46

というか、典型を嫌うのでアルゴリズム全然使わなくても水とか青になれちゃうじゃん

2022/09/09(金) 22:03:48.01

アルゴリズムの定義読んでこい

2022/09/10(土) 00:12:27.66

蟻本は著者の頭が良いから簡潔に書かれてて、それ故に俺の頭じゃ理解できん

2022/09/10(土) 03:32:09.56

本当に賢い人は云々

2022/09/10(土) 04:59:42.21

>>718
単に説明が下手なだけだと思います。
完成度も低いと思います。

2022/09/10(土) 05:04:17.39

ほならね

2022/09/10(土) 05:06:40.45

海外の本で良い本はないんですか？

2022/09/10(土) 13:06:15.05

蟻本の説明がへたくそだとは思わないし、行間も一般的な数学書より狭いと思うけど、実際海外の競プロ本ってどんなのがあるのか気になるな

2022/09/10(土) 14:11:29.88

Springerの"Guide to Competitive Programming"は読んだことある。
けんちょん本と同等程度のレベルって感じだけど典型テクニックへの言及はこっちのほうが多いかな
アルゴリズムの説明だけで実装が書いてないところが結構ある

**642** (ﾜｯﾁｮｲ ea2c-kBqH) · 2022/09/10(土) 14:14:41.39

蟻本は簡単な説明だけ。
個別のアルゴリズムは検索して、理解するまで自分で図を描いて勉強しないと無理

だから、>>642
に書いたように、個別の著書で調べる

湊真一、セジウィック、石畑清、川中真耶、インド人とか

例えば赤黒木なら、どの本だったかな? みたいな

2022/09/10(土) 15:22:48.30

>>724
ありがとう
聞いた感じ、英語圏の標準的な入門書って雰囲気だね
やっぱり気になるのは中国だからいくつか調べてみた

・算法竞赛入门到进阶
・算法竞赛入门经典
・算法竞赛宝典

調べた感じまず目についたのはこのあたり？算法竞赛で競技プログラミングらしい
いずれもペーパーブックしかないところが惜しい
俺は機械翻訳しないと中国語読めないので
入门は日本で出版されている平均的なものとあまり変わらなそうな予感がするけど、宝典とかいうのは気になるね

2022/09/10(土) 15:25:44.75

と思ったら電子書籍もありそうだ
amazonだけで調べて電子書籍ないと思い込んだのは我ながらネットリテラシー低いな

2022/09/10(土) 15:28:15.89

しかし中華サイトは技術サイトでもキモい広告の表示のされ方がするな

2022/09/10(土) 16:26:58.64

いいね、中国の最高の本を見つけたら教えてね

2022/09/10(土) 16:53:59.26

無理に中国語にこだわらなくてもいいと思うけど

2022/09/10(土) 17:39:53.64

蟻本の凡人日本語訳が求められている

2022/09/10(土) 20:23:17.78

今日初参加するわよろしく
本番の回答ここに貼ってくれてもOK！

2022/09/10(土) 22:42:02.88

なんで久しぶりに参加したときだけDが異常にムズいの
EとかFとか挑戦すらできず…

2022/09/10(土) 22:59:34.87

D解いた時点でひどい順位だったけどFGが軽実装で救われた

2022/09/10(土) 23:02:53.92

安倍晋三erすき

2022/09/10(土) 23:03:14.22

スレ間違えたけど間違えてない気もする

2022/09/10(土) 23:37:10.70

Exの最後のパートの「区間集合が与えられて、その集合に属する任意の区間内に*が存在するように*を配置するとき、*の数を最小化せよ」って問題、定期的に出る典型だ
これもmincut maxflowの要領で双対とると蟻本でも有名な区間スケジューリング問題になって双対すごいってなった問題
なお今日はそこまで至れなかった模様

2022/09/10(土) 23:43:38.03

Dみたいなプログラミング的に普通っぽい問題の難易度が高いｗ

2022/09/10(土) 23:48:32.95

>>738
dfsで全列挙みたいなのが地味に一番実装難易度高い気がする

2022/09/10(土) 23:50:24.73

G、実はabc...とzyx...のときの順位を足して二で割るだけでいいって流れてきて、嘘だろ！？って思ったけど式を見てみたらそうだった
実はTrieもsuffixもprefixも要らんかったんや…

2022/09/10(土) 23:56:40.36

>>730
競プロ強いのは中国語圏とロシア語圏だし、日本で出版されているよりすごい書籍があるとしたらその辺かなと思って

2022/09/11(日) 00:01:21.87

あと、Exの解説ではSA使ってるけど、長い文に対する複数文字列の位置検出といえばAho Corasick法がまさに使える

2022/09/11(日) 00:14:58.33

C、絶対位置を相対位置に変換して考えるのって初見でできたらかなり頭いいと思うんだけど茶diffなんだね
みんな頭いいな（もしくは典型で染みついている層が茶まで下りてきてるか）

2022/09/11(日) 00:32:41.95

パソコンに向かって解法や実装で延々と悩んでたのに、
疲れてベッドに横たわるとすぐにアイデアが出てくるのが謎

2022/09/11(日) 00:49:02.92

上位者は本番中に問題を解ける思考モードへの入り方がうまいっぽい
chokudaiか誰だったか忘れたけど、本番じゃないとAGCの問題解くの難しいって言ってたな
かなりメンタルが影響するらしい

2022/09/11(日) 00:51:45.15

数オリで中国チームが全員満点って話あって、情オリ見てみたけどこっちでも上位4は中国チームのメンバーで独占してるんだなあ・・・
https://stats.ioinformatics.org/results/2022

と思ってもっとよく見てみたら6位まで全部中国人やんけ

2022/09/11(日) 11:51:48.46

>>737
Exというのはどの問題のことでしょうか？

2022/09/11(日) 12:15:21.09

>>747
ABCの八問目で一番最後の問題
昔はHだった

2022/09/11(日) 12:33:26.32

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

『プログラミングコンテストチャレンジブック第2版』のp.325に、

「したがって、先ほどの長方形を左半分と右半分の一辺dの正方形に分けると、それぞれの正方形には、
点はたかだか3個しか含まれません。」

と書いてあるのですが、たかだか2個ではないですか？
3個になる例はありますか？

2022/09/11(日) 12:37:14.74

3点となる例がわかりました。
でも4点の例がないことはどうやって証明するのでしょうか？
直感的には3点であろうと思いますが。

2022/09/11(日) 12:39:35.27

>>743
競プロ初心者だけどC、40分くらい考えた末解けて自分天才だろと思ったのに茶diffだったんだな
みんな頭いいな

2022/09/11(日) 12:40:58.84

初心者で今回のCが解けるなら大したもんだよ

2022/09/11(日) 14:17:40.92

>>750
コンテスト中だと直感で済ませちゃうけど、ちゃんと証明書こうとするとめんどいやつだ

全ての点対の距離がd以上であるような4点が正方形領域内にあると仮定する。
この四点をA,B,C,Dとし、四角形ABCDを考える。
(1)全ての頂点の角度が180°未満のとき
角度が90°以上である頂点が存在、これをAとしても一般性を失わない。
ここで余弦定理より、BD^2 = AB^2 + AD^2 - 2 AB AD cos∠BAD >= AB^2 + AD^2 >= 2 d^2
よって、BD >= √2d
(2)ある頂点の角度が180°以上のとき
角度が180°以上である頂点をAとしても一般性を失わない。
ここで、∠BAC+∠DAC>=180°なので∠BACと∠DACのいずれかは90°以上。
∠BACを90°以上としても一般性を失わない。
(1)と同様の議論により、BC >= √2d

正方形領域内の点対距離は√2d未満（座標計算普通にやれば示せると思う）
(1),(2)のいずれの場合においても矛盾が生じる。
（証明終）

2022/09/11(日) 14:26:08.97

あ、(1)も(2)も不等式評価で角度が180°以下であることを使ってるけど、ちゃんと書いてないからキモい雰囲気の証明になってるな

2022/09/11(日) 15:12:26.47

凸包の最遠点対という特徴量、いかにも重要そうだけどあまり競プロで使った覚えがない
ABC234Exなんかは最近点対問題の解法と似た発想かもしれない、さすがにABC234Exの方が難しいけど

2022/09/11(日) 15:27:05.90

本質は無なので無料です

2022/09/11(日) 15:46:11.70

逆に最遠点対どうやってNlogNで求めるんだっけって思ったが、凸包求めてキャリパー法でくるくるか
幾何系はド典型でも全然頭に定着しない

2022/09/11(日) 16:55:39.75

昨日のABC、Dの実装でバグらせる予感しかしなかったからEから解いて何とかギリギリ解けたけど難易度E>Fだったんだな
F典型って聞いたけど青くらいまで行けば典型に見えるんだろうかたしかに取り組みやすそうな問題ではあったけど

2022/09/11(日) 17:29:18.43

>>753
証明ありがとうございました．
うまい証明ですね．

2022/09/11(日) 17:37:25.16

>>751
今，解こうとしていますが，難しいですね．
素朴な方法だとΘ(N^2)ですね．
回転前の喜ぶ人の人数から，回転後の喜ぶ人の人数が簡単に計算できないかと考えているのですが，うまくいきません．

2022/09/11(日) 18:18:32.35

>>751
幅3のパルス波が押し寄せてくるイメージを思いつきました．
なんとなく解けるような気がします．

2022/09/11(日) 18:57:12.47

>>751

半日かかりましたが，Θ(N)のアルゴリズムを作ってパスしました．
これじゃ，コンテストでいい成績は残せませんね．

2022/09/11(日) 20:29:08.05

ARC出ません

2022/09/11(日) 23:13:18.91

E問題解きたかったなあ…

2022/09/11(日) 23:24:22.70

最終的にはわからない問題を考え続けるのが一番の練習法らしいから、解説を見ないで解く体力が長い目で見て実力に寄与する気がするし、ABC-Cを半日考えて解くのは上等
ただ、ABCだと知識ゲーの要素があるから、最初のうちは解説見た方がサクサクレートが上がる場合もあるし、悩みどころだ

2022/09/12(月) 07:10:41.31

「Closest pair of points」を求めるアルゴリズムについてですが，『プログラミングコンテストチャレンジブック第2版』の
説明だと説明が全く不足しています．

この本を褒める人がいますが，信じられません．
確かに他に少し高度なこの類の本がないというのは事実だと思いますが．

CLRSの計算幾何学の章に非常に詳しく解説が書いてありますので，そちらを読もうと思います．

2022/09/12(月) 07:12:15.09

『プログラミングコンテストチャレンジブック第2版』ですが，完全な解説ではなく，スケッチ程度の説明集だと
思います．

ネット上の解説などもそのようなものがほとんどだと思います．

2022/09/12(月) 07:57:57.20

そうなんだ

2022/09/12(月) 11:21:41.15

4点の証明よりめんどい行間ある？って思ったけどマージソートの部分か
x座標で点集合を分けたあと、各ステップでx座標的に隣接する点集合を合わせることを繰り返すわけだが、そこでマージソートの要領でy座標をソートすることで、時間計算量を増やさずにy座標のソートができる
ある程度のレベルの学術書で単体で行間埋められる本の方が珍しいし、別に行間だらけだから良書じゃないなんてことはないと思うがな

2022/09/12(月) 17:30:34.33

>>769
確かに有益な本だとは思うのですが，もう少し解説が丁寧だといいなと思います．
完全に理解するために，ソースコードに頼ることが非常に多いので．

何かおすすめのAtCoderの問題はありますか？
難しすぎると解けないので，初心者でも解けるくらいで面白い問題が希望です．

2022/09/12(月) 18:09:25.90

>>770
このサイトはAtCoder Problemsといって、各問題のdifficultyという数値を見ることができる
https://kenkoooo.com/atcoder#/table/

difficultyとはなにかと言うと、半分ぐらいの確率でその問題を解けるであろう人のレートを推定したもの
ここでdifficultyの二分探索でもすれば自ずと丁度いいぐらいのところに行きつくと思う
基本的には自分のレートと同じか一色上ぐらいがやってて楽しい
初心者でプログラミング自体はできるんなら、最初はABC-C、ARC-Aぐらいの問題が丁度いいレベルと思う
面白さについて言えばAtCoderの問題は大体パズル的には面白いはず、ただそこも好みだな
高度な知識をたくさん使いたいんならCodeForcesの方が面白いかもしれない

2022/09/12(月) 18:15:28.92

>>771

詳しく丁寧にありがとうございました．

時間をかけて解いていきたいと思います．

2022/09/12(月) 18:20:46.33

蟻本が解説に関して親切設計な本ではないのは確か
今は蟻本よりもっと初学者向けの競プロ本がたくさんあるから、その中から選ぶのも手ではある
最近は鉄則本なんていうのも出て、それも蟻本に比べたら多分初学者向け
https://kato-hiro.github.io/AtCoderClans/books/

ただ厳密数学的な意味で丁寧な本ってあるんか？自分は蟻本以外読んだことないからよくわからん

2022/09/12(月) 18:38:46.03

>>773
リンクありがとうございました．

2022/09/13(火) 06:55:02.21

こどふぉで自分のレートのdifficultyの問題をずーっとやってるんだけど、
簡単に解けるのと全然歯が立たないのがある…

2022/09/13(火) 19:26:09.73

外国人と日本人で結構な得意な問題が違う気がする

2022/09/14(水) 09:18:47.48

github.com/drken1215/book_algorithm_solution/blob/master/solutions/chap04.md

この4.6のコードですが、本当にO(N*W)ですか？

ボトムアップ型の動的計画法がO(N*W)というのは分かりますが、4.6は違うような気がします。