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

■ このスレッドは過去ログ倉庫に格納されています
1デフォルトの名無しさん (ﾜｯﾁｮｲ 1f9f-qCnf)
垢版 |
2021/07/28(水) 21:58:48.02ID:nljYiy+l0
!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/06(火) 22:51:12.89ID:wi6f+hdmM
線形計画法の問題とか考察つまんなそう
2022/09/06(火) 23:14:40.13ID:0mlgzznW0
線形計画はよく出てるじゃん
2022/09/07(水) 00:40:38.30ID:P6TFpbuE0
普通にLP解いたりラグランジュ双対とったりする問題は頻出だと思うけど
同じ数理最適化でもニュートン法とかもっと機械学習っぽい連続最適化問題出せみたいな話は分かるが
2022/09/07(水) 00:48:11.56ID:P6TFpbuE0
ただその辺はABC-GとかExとかARC-C以降とかに放り込まれているから、数論や組合せ論系の問題が元から得意じゃないとそこで阻まれてたどり着きにくいというのはそう
657デフォルトの名無しさん (ﾜｯﾁｮｲ bf71-InTp)
垢版 |
2022/09/07(水) 01:27:40.63ID:KXyAg9cX0
え、脳死でソルバーに突っ込んで解けるのがG以降にあるの？
だとしても普通に最適化系の科目をで履修中の人が解ける3-400点程度に押さえてCDあたりで出すべきかと
2022/09/07(水) 02:44:08.46ID:P6TFpbuE0
>>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.65ID:P6TFpbuE0
そもそもAtCoderのアルゴの方のコンテストだと確率的に正解になる解法はコンセプト上想定解にしにくいから、脳死LPが出てくるとしたらソルバーに投げるんじゃなくて普通に頂点全探索が間に合うような問題になるかな
二次元ですら実行可能領域求めるの結構大変だから、ABC-Cで出すとしたらかなりかなりわかりやすい凸多角形にする必要がありそう
2022/09/07(水) 03:03:03.88ID:k+EcBBmh0
ARC128-CのLP感好きだよ
2022/09/07(水) 03:05:01.25ID:P6TFpbuE0
あ、確率的に、というのはTLEの方の話ね
2022/09/07(水) 10:36:39.59ID:+ZV6H66AM
ABC-Cに虚無LP入れたら荒れそうだな
崎になにか教育コンテンツで啓蒙した方がよさそう
2022/09/07(水) 12:43:39.65ID:FwvlQ1D10
2021年以降のARCみたいな問題て他にどこで練習すれば
664デフォルトの名無しさん (ﾜｯﾁｮｲ e733-Iguz)
垢版 |
2022/09/07(水) 16:13:49.50ID:jifeMzUR0
https://atcoder.jp/contests/abc087/tasks/arc090_a
にある
左上および右下のマスにもアメが置かれており、あなたはこれらのマスに置かれているアメも回収します。
ってどういう意味？
単純に通ったマスの飴だけとったらACになったんだけど、問題の意味が分からんかった
2022/09/07(水) 16:33:40.95ID:yQCLjQqS0
スタートとゴールも移動中に通ったマスとみなす
666デフォルトの名無しさん (ﾜｯﾁｮｲ e733-Iguz)
垢版 |
2022/09/07(水) 16:39:19.33ID:jifeMzUR0
そういうことかありがとう
2022/09/07(水) 18:24:50.65ID:P6TFpbuE0
>>664
確かに一瞬、意味が取れなくて(i,j)を通ったら(i-1,j-1) or (i+1,j+1)の飴も回収できてますよ、的な話かと思ってしまった
(1,1)と(2,N)の飴も回収しますとか書いた方が紛れが少なそう
2022/09/07(水) 18:25:54.23ID:P6TFpbuE0
>>663
これは俺も気になる
相性が悪いのかもしれないけど、かなり難しくなってないか？
669デフォルトの名無しさん (ﾜｯﾁｮｲ 5f55-CzlZ)
垢版 |
2022/09/07(水) 19:18:51.47ID:pyqwkznf0
競技プログラミングの問題には人間の作者がいるので，それほど独創的な問題を量産できるとは思えません．
とすると，ある程度の訓練を積んだ人間にとっては，同工異曲な問題群に見えるのではないか？

と考えたのですが，あっていますか？
2022/09/07(水) 19:25:51.03ID:lTpXDHBr0
そらそうだよ
数オリだろうが過去問たくさん練習すれば解ける確率上がるからね
671デフォルトの名無しさん (ﾜｯﾁｮｲ 5f55-CzlZ)
垢版 |
2022/09/07(水) 19:40:51.71ID:pyqwkznf0
数学オリンピックの問題はおそらく数学者が作っていると思いますが，AtCoderの問題は学者が作っているわけではないですよね？
だとすると，問題の独創性はかなり低いのではないかと推測しますが，あっていますか？
2022/09/07(水) 20:11:10.05ID:lTpXDHBr0
さすがにAGCとかになると作問者もかなりハイレベルだし既出かどうかをチェックする体制などもあるのであまり関係ないと思いますが、作問者じゃないしわかりません
そんなに気になるなら高橋社長に聞いてみたらどうですか
TwitterでもYouTubeでも匿名で質問しても回答をくれますよ
2022/09/07(水) 20:12:27.65ID:lTpXDHBr0
AtCoderの出題者は今のところ、一般の学生、たまに会社員って感じではありますね
2022/09/07(水) 20:22:49.29ID:P6TFpbuE0
別にそんなことはないよ
ABCは典型問題だらけだけど、AGCはかなり独創性の高い問題を出すことを志向している
そもそも数学者としての能力と競プロの独創的な問題を作る能力はそもそも微妙に違う、良くも悪くも
もちろんAGCすら世界10位以内とかのクラスから見たらパターン見えるのかもしれないけど、大体の人だと二十年頑張ってもパターン学習できないと思う
2022/09/07(水) 20:23:20.87ID:P6TFpbuE0
>>674
あ、これは>>671へのレスね
2022/09/07(水) 20:28:55.80ID:P6TFpbuE0
数オリ勢の成績見た感じIMOとAGCだと多分AGCの方が難しいと思うんだけど、実際のところどうなんだろう
2022/09/07(水) 20:31:50.41ID:WXz7nKNF0
ABC224HなんかはLPの定式化は自明でソルバに突っ込んで解いた人もいるらしい
2022/09/07(水) 20:55:25.96ID:P6TFpbuE0
>>677
これソルバ解けるのか、思ったよりLPソルバ優秀だな…
というか想定解の双対とってMCFもかなり見えやすい問題だ
2022/09/07(水) 20:57:18.48ID:lTpXDHBr0
AGCも問題にバラツキあるから、ハッキリとは言いづらいけど、
全年齢対象なのになかなか全完が出ないAGCのほうがやっぱ難しといえるんじゃない？

ちなみに今年の数オリは中国からの参加者は全員が満点を取ったらしい
簡単だったのかな
680デフォルトの名無しさん (ｱｳｱｳｳｰ Sa8b-QAu0)
垢版 |
2022/09/07(水) 22:38:04.79ID:LY9bvG3na
赤コーダーともなれば数学者と変わらんだろ
2022/09/07(水) 23:09:32.31ID:WXz7nKNF0
赤を褒めてるのか貶してるのかわからんな
682デフォルトの名無しさん (ﾜｯﾁｮｲ e733-Iguz)
垢版 |
2022/09/08(木) 00:50:08.86ID:A4rHdGWR0
chokudaiも以前に何かの放送で、新しい問題つくるのがほんと大変だって言ってたな
2022/09/08(木) 01:10:26.92ID:tYYY8KHVr
うんち
2022/09/08(木) 01:10:36.47ID:tYYY8KHVr
あっスレ間違えた
2022/09/08(木) 16:53:49.09ID:/uGN1f4lM
E8くんなにするんだろう
新書籍発売？
新コンテストサイト公開？
2022/09/08(木) 16:56:30.24ID:/uGN1f4lM
まあ大概学問もパターンゲーじゃないか
むしろアドホックな考察力が求められる分野の方が少数だと思うね
2022/09/08(木) 17:47:01.03ID:ebtkaE3x0
典型90の本じゃないのかな
2022/09/08(木) 18:28:42.75ID:T90QpKCS0
あれまだ発売されていなかったのか
2022/09/08(木) 19:37:15.04ID:/uGN1f4lM
>>687
なるほど、そういえば発売まだだったのか
確かにそれが一番可能性高そうだな
2022/09/08(木) 21:04:16.55ID:AKUPUpuB0
E8くんって最近コンテスト出てない？
前のAGC見かけなかった気がするな
2022/09/09(金) 03:58:24.24ID:KcSQBtjOM
E8くん、すごい執筆速度だ
このアウトプット力は素直にすごい
ただ、やっぱりABC-ratedが対象読者みたいで、暖色を押し上げる本は相当難しいんだなと
2022/09/09(金) 11:34:36.68ID:zBJv5lXS0
新しいE8本、俺はヒューリスティックできないからその部分は読もうかと思う
2022/09/09(金) 13:43:54.42ID:kTxh4G5U0
ヒューリスティック蟻本誰か出して🤗
2022/09/09(金) 14:01:12.69ID:eDV4BhqD0
蟻本の著者でもあるwataさんが書いてるこれの解説を読めばよくね？
https://atcoder.jp/contests/intro-heuristics
2022/09/09(金) 14:14:38.24ID:kTxh4G5U0
これ普通に知らなかった
感謝です
2022/09/09(金) 14:21:03.62ID:eDV4BhqD0
でもこのPDF、ビームサーチの解説が「後で追記」のままになってるな・・・
chokudaiに通報したほうがいいね
697デフォルトの名無しさん (ﾜｯﾁｮｲ 5f55-CzlZ)
垢版 |
2022/09/09(金) 14:25:44.31ID:kJ4avtf50
競技プログラミングをやっている人で強い人でも、アカデミックな匂いのしない人
が結構いるように思います。
2022/09/09(金) 17:13:05.72ID:zBJv5lXS0
学者じゃないから、そりゃいると思うよ
数学や情報科学が得意な人も少しいるゲーマーコミュニティってだけで
2022/09/09(金) 17:33:18.01ID:zBJv5lXS0
暖色向け本の話だけど、今のAtCoderで黄色より上に上がるのに別にそんなに知識って寄与しないイメージ（というか知識だけならみんなもう持ってる層での競争）で、こういうデ/アの知識を入れた方がいいとか、知らないデ/アの知識を手に入れるにはどうしたらいいのかみたいな話はあんま”本質”って感じがしないんだよな
2022/09/09(金) 18:51:34.08ID:E+8eKKfg0
12年前に蟻本出したってよう考えたらすげえことだな
701デフォルトの名無しさん (ﾜｯﾁｮｲ 5f55-CzlZ)
垢版 |
2022/09/09(金) 19:03:35.57ID:kJ4avtf50
何がすごいんですか？
2022/09/09(金) 19:17:01.85ID:zBJv5lXS0
競技プログラミングは独創的な問題に価値を見出しているから、年々新しい問題がたくさん作られているんだけど、未だに12年前の本が中級者（ここでは水〜黄ぐらい？）向けの本としては定評があるから
2022/09/09(金) 19:22:06.29ID:n8dQNxep0
蟻本って、プログラミング・コンテスト・チャレンジブック、第2版、2012 の事か

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

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

読んだ感じ、すごい学生達だと思った。
商売はアイデア。これはニーズがあるから売れると思った
2022/09/09(金) 19:22:54.76ID:zBJv5lXS0
まあ蟻本の知識的な内容を全部理解しててもちゃんと考察力がないと橙にもなれないと思うけど
705デフォルトの名無しさん (ﾜｯﾁｮｲ 5f55-CzlZ)
垢版 |
2022/09/09(金) 20:00:57.21ID:kJ4avtf50
>>702
独創的な問題といっても，アルゴリズムとデータ構造の本に書いてある知識で解ける問題ですよね？

みなさんはアルゴリズムとデータ構造の本を読んで勉強しますか？
2022/09/09(金) 20:05:14.26ID:zBJv5lXS0
ある一定レベル以上行くと要求知識と難易度ってそんな関係ないんだよね
小学生でも理解できる単純な貪欲アルゴリズムが解法の問題が永続赤黒木を要求する問題より難しいということがままある
2022/09/09(金) 20:06:03.79ID:pJ7ShlGc0
解けないよ
小学校の計算ドリルじゃあるまいし

AGC解いてみればわかると思うけど、知識は大前提で、それ以上に閃きみたいなのが必要
つまりアルゴリズム知識問題というよりは、どちらというとやたら頭を使うパズルやなぞなぞといったほうがいい
2022/09/09(金) 20:11:55.82ID:zBJv5lXS0
AtCoderに関して言えば、正直、ABCの問題（Exまで）や典型90を解いて蟻本を読むだけでもほぼ知識的には網羅できていて、学術的なアルゴリズムとデータ構造の本を読む必要性があるかというとそこまででもない
ただ、アルゴリズムとデータ構造を題材としたゲームをやっているので周辺知識に興味がある人も多くいて、趣味で勉強している人は結構いる雰囲気
学術的じゃない人もいるけど、学術的なことが好きな人も他より多めだと思うので、そういう人と話してみたら面白いのではないかな
2022/09/09(金) 20:34:07.29ID:yIa0OFzGM
アルゴリズムとデータ構造の網羅性のある教科書の知識があれば知識面では十分問題が解ける水準にあると思う
ただそれには前提があって、発想力がないといくら知識があっても解けない（そしてここの要求水準が結構厳しめ）
って感じかね
2022/09/09(金) 20:37:14.53ID:pJ7ShlGc0
そうだよ
AGC解いてみろよ
AGCでも、AとかB問題ならアルゴリズム知識すら不要で、発想力のみ問われてるようなのが多いぞ
711デフォルトの名無しさん (ﾜｯﾁｮｲ e733-Iguz)
垢版 |
2022/09/09(金) 20:48:11.75ID:0OeV3J7Z0
何十年考える時間与えられても解けない自信あるわ
2022/09/09(金) 20:50:30.48ID:yIa0OFzGM
>>705
AtCoderの社長のchokudaiとかは、アルゴリズムイントロダクションを昔読んでたね
競プロで強くなるために最適な道かは知らないけど、読んでる人はいっぱいいると思う
2022/09/09(金) 20:53:37.03ID:Xak+SWAc0
好きな、覚えたてなコンピューター言語その他を使ってやるブラゲーっと思ってやってみた。
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.67ID:eDV4BhqD0
>>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.95ID:eDV4BhqD0
10^8回以上のループを書いてしまったら、実行時間制限に引っかかりそう

っていう程度の知識はいるけども
716デフォルトの名無しさん (ﾜｯﾁｮｲ bf71-InTp)
垢版 |
2022/09/09(金) 21:51:15.46ID:jmAmnAZ30
というか、典型を嫌うのでアルゴリズム全然使わなくても水とか青になれちゃうじゃん
2022/09/09(金) 22:03:48.01ID:N29LuzVwa
アルゴリズムの定義読んでこい
2022/09/10(土) 00:12:27.66ID:VggS9H2X0
蟻本は著者の頭が良いから簡潔に書かれてて、それ故に俺の頭じゃ理解できん
2022/09/10(土) 03:32:09.56ID:yhVOakDL0
本当に賢い人は云々
720デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/10(土) 04:59:42.21ID:eGCheWpr0
>>718
単に説明が下手なだけだと思います。
完成度も低いと思います。
2022/09/10(土) 05:04:17.39ID:44udkTjy0
ほならね
722デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/10(土) 05:06:40.45ID:eGCheWpr0
海外の本で良い本はないんですか？
2022/09/10(土) 13:06:15.05ID:ES5OPAh40
蟻本の説明がへたくそだとは思わないし、行間も一般的な数学書より狭いと思うけど、実際海外の競プロ本ってどんなのがあるのか気になるな
2022/09/10(土) 14:11:29.88ID:yhVOakDL0
Springerの"Guide to Competitive Programming"は読んだことある。
けんちょん本と同等程度のレベルって感じだけど典型テクニックへの言及はこっちのほうが多いかな
アルゴリズムの説明だけで実装が書いてないところが結構ある
2022/09/10(土) 14:14:41.39ID:2MbFO6mH0
蟻本は簡単な説明だけ。
個別のアルゴリズムは検索して、理解するまで自分で図を描いて勉強しないと無理

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

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

例えば赤黒木なら、どの本だったかな? みたいな
2022/09/10(土) 15:22:48.30ID:ES5OPAh40
>>724
ありがとう
聞いた感じ、英語圏の標準的な入門書って雰囲気だね
やっぱり気になるのは中国だからいくつか調べてみた

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

調べた感じまず目についたのはこのあたり？算法竞赛で競技プログラミングらしい
いずれもペーパーブックしかないところが惜しい
俺は機械翻訳しないと中国語読めないので
入门は日本で出版されている平均的なものとあまり変わらなそうな予感がするけど、宝典とかいうのは気になるね
2022/09/10(土) 15:25:44.75ID:ES5OPAh40
と思ったら電子書籍もありそうだ
amazonだけで調べて電子書籍ないと思い込んだのは我ながらネットリテラシー低いな
2022/09/10(土) 15:28:15.89ID:ES5OPAh40
しかし中華サイトは技術サイトでもキモい広告の表示のされ方がするな
2022/09/10(土) 16:26:58.64ID:vGRthkD8p
いいね、中国の最高の本を見つけたら教えてね
2022/09/10(土) 16:53:59.26ID:/N4+WCeu0
無理に中国語にこだわらなくてもいいと思うけど
2022/09/10(土) 17:39:53.64ID:yhVOakDL0
蟻本の凡人日本語訳が求められている
2022/09/10(土) 20:23:17.78ID:denZ2QcH0
今日初参加するわよろしく
本番の回答ここに貼ってくれてもOK！
2022/09/10(土) 22:42:02.88ID:h7iCGaIK0
なんで久しぶりに参加したときだけDが異常にムズいの
EとかFとか挑戦すらできず…
2022/09/10(土) 22:59:34.87ID:FQ2evD1NM
D解いた時点でひどい順位だったけどFGが軽実装で救われた
2022/09/10(土) 23:02:53.92ID:ulAsr0Va0
安倍晋三erすき
2022/09/10(土) 23:03:14.22ID:ulAsr0Va0
スレ間違えたけど間違えてない気もする
2022/09/10(土) 23:37:10.70ID:ES5OPAh40
Exの最後のパートの「区間集合が与えられて、その集合に属する任意の区間内に*が存在するように*を配置するとき、*の数を最小化せよ」って問題、定期的に出る典型だ
これもmincut maxflowの要領で双対とると蟻本でも有名な区間スケジューリング問題になって双対すごいってなった問題
なお今日はそこまで至れなかった模様
738デフォルトの名無しさん (ﾜｯﾁｮｲ de71-pqEy)
垢版 |
2022/09/10(土) 23:43:38.03ID:IxTwXPHP0
Dみたいなプログラミング的に普通っぽい問題の難易度が高いｗ
2022/09/10(土) 23:48:32.95ID:v7e0/wUkM
>>738
dfsで全列挙みたいなのが地味に一番実装難易度高い気がする
2022/09/10(土) 23:50:24.73ID:v7e0/wUkM
G、実はabc...とzyx...のときの順位を足して二で割るだけでいいって流れてきて、嘘だろ！？って思ったけど式を見てみたらそうだった
実はTrieもsuffixもprefixも要らんかったんや…
2022/09/10(土) 23:56:40.36ID:ES5OPAh40
>>730
競プロ強いのは中国語圏とロシア語圏だし、日本で出版されているよりすごい書籍があるとしたらその辺かなと思って
2022/09/11(日) 00:01:21.87ID:jAgyYoIY0
あと、Exの解説ではSA使ってるけど、長い文に対する複数文字列の位置検出といえばAho Corasick法がまさに使える
2022/09/11(日) 00:14:58.33ID:jAgyYoIY0
C、絶対位置を相対位置に変換して考えるのって初見でできたらかなり頭いいと思うんだけど茶diffなんだね
みんな頭いいな（もしくは典型で染みついている層が茶まで下りてきてるか）
2022/09/11(日) 00:32:41.95ID:Bha8il/10
パソコンに向かって解法や実装で延々と悩んでたのに、
疲れてベッドに横たわるとすぐにアイデアが出てくるのが謎
2022/09/11(日) 00:49:02.92ID:jAgyYoIY0
上位者は本番中に問題を解ける思考モードへの入り方がうまいっぽい
chokudaiか誰だったか忘れたけど、本番じゃないとAGCの問題解くの難しいって言ってたな
かなりメンタルが影響するらしい
2022/09/11(日) 00:51:45.15ID:kEOVMHNm0
数オリで中国チームが全員満点って話あって、情オリ見てみたけどこっちでも上位4は中国チームのメンバーで独占してるんだなあ・・・
https://stats.ioinformatics.org/results/2022

と思ってもっとよく見てみたら6位まで全部中国人やんけ
747デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/11(日) 11:51:48.46ID:c+Ui/I6I0
>>737
Exというのはどの問題のことでしょうか？
2022/09/11(日) 12:15:21.09ID:sY9L7CLNM
>>747
ABCの八問目で一番最後の問題
昔はHだった
749デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/11(日) 12:33:26.32ID:c+Ui/I6I0
>>748
ありがとうございました。

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

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

と書いてあるのですが、たかだか2個ではないですか？
3個になる例はありますか？
750デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/11(日) 12:37:14.74ID:c+Ui/I6I0
3点となる例がわかりました。
でも4点の例がないことはどうやって証明するのでしょうか？
直感的には3点であろうと思いますが。
2022/09/11(日) 12:39:35.27ID:B0Yjkt4W0
>>743
競プロ初心者だけどC、40分くらい考えた末解けて自分天才だろと思ったのに茶diffだったんだな
みんな頭いいな
2022/09/11(日) 12:40:58.84ID:kEOVMHNm0
初心者で今回のCが解けるなら大したもんだよ
2022/09/11(日) 14:17:40.92ID:sY9L7CLNM
>>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)のいずれの場合においても矛盾が生じる。
（証明終）
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況