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

レス数が900を超えています。1000を超えると表示できなくなるよ。
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/24(土) 23:04:41.84ID:Cc5Uw0Zt0
確かに直感的にはDはgreedyでもよさそうだけど、ナップサック法よろしく、整数が絡むと途端に直感greedyが壊れる
ABC-DからABC-Fぐらいの問題だとコンテスト中はgreedyがダメな理由を考えるより簡単に正当性を示せるDPを思いつくことを意識した方がいい
2022/09/24(土) 23:07:25.27ID:Cc5Uw0Zt0
反例に関して言えば2個取るという選択肢がないのが効いてる
2022/09/24(土) 23:16:48.66ID:Cc5Uw0Zt0
ExのFPS解面白い
確かにDP遷移で途中\sum_n {n a_n}みたいな形の式が出てきてめんどくさそうと思ったけど、こういうのはFPSならただの微分か
849デフォルトの名無しさん (ﾜｯﾁｮｲ 9e71-mIyF)
垢版 |
2022/09/25(日) 01:57:37.46ID:eKbCKhXa0
Dが水という事は、ビギナーコンテストだからC問題までの３問で良いじゃん
2022/09/25(日) 02:18:02.40ID:qNDnNxHD0
8問ABCは言うなればCodeForces Div. 2 + Div. 3 + Div. 4みたいな状態だから、Div. 3単独開催やDiv. 4単独開催が欲しいって話は分からなくもない
4問時代のABCがまさにそんな感じだったけど
コドフォが最近Div. 4増やしてるし、AtCoderも現ABCの下の区分のコンテスト作っていいと思うけどね
2022/09/25(日) 02:25:38.65ID:qNDnNxHD0
自分の感覚だと
CF Global = AC AGC
CF Div. 1 = AC ARC
CF Div. 2 = AC ABC-C〜Ex
CF Div. 3 = AC ABC-C〜F
CF Div. 4 = AC ABC-A〜D
ぐらいのイメージなんだけど、合ってる？
そんなコドフォ出てないから詳しくないけど、Div. 2以下の階級を全部ABCがカバーしている状態ではあるのは確かだと思っている
852デフォルトの名無しさん (ｻｻｸｯﾃﾛﾚ Sp47-Rupp)
垢版 |
2022/09/25(日) 09:32:03.84ID:HBsCeuHap
昨日のEってどういう思考過程をすれば二分探索が思いつけるんだ
言われたらそれはそうってなるけど
2022/09/25(日) 11:07:00.84ID:gbe15JeH0
>>845
肉を切らせて骨を断つ
無傷でいようとすると勝てないってわけよ
2022/09/25(日) 12:13:04.55ID:ODs0tVKRM
昨日のEは別に二分探索なんか使わなくても素直なやり方で解ける気がするが、判定問題が簡単で単調性がありそうならとりあえず二分探索試して損はない
2022/09/25(日) 12:15:43.34ID:ODs0tVKRM
ぐろふぉはAGCより取っつきやすい気がするな
2022/09/25(日) 12:46:21.45ID:ODs0tVKRM
Twitterみた感じEのO(NlogN)解は重実装扱いなのか
個人的には二分探索解と大して変わらんやろと思ったが
857デフォルトの名無しさん (ｻｻｸｯﾃﾛﾚ Sp47-Rupp)
垢版 |
2022/09/25(日) 13:15:51.54ID:JpevNCD6p
愚直にシミュレーションしようとしたらバグらせまくったから二分探索の発想が早い段階で思い浮かぶように出来たら便利だなって
2022/09/25(日) 22:01:15.20ID:IPCnGxrw0
端数は後でなんとかすることにしてだいたい何周すればいいか知りたくなって、周回数を決め打ちすれば何個減るかはO(N)でわかるから二分探索すれば良さそうとなる
2022/09/25(日) 23:58:46.25ID:5HnvgjcS0
ユーザー解説にO(NlogN)の実装があるから見たけど、そんな重実装かこれ？
二分探索より楽に見えるんだが
2022/09/26(月) 09:01:27.51ID:cpj0q9yVM
本来二分探索の実装ってかなりバグらせやすい方だと思うんだが、めぐる式で教育が行き届いている？のか、最近はみんな脳死で書ける印象
O(NlogN)解は量や内容は大したことないがアドホックなのが効いてんのかな
2022/09/26(月) 10:32:20.32ID:ncSKb+wV0
にぶたんの最後のシメを考えるのが苦手すぎる…
LRがどうなったら終わりで、どっちに答えが入ってるのか分からなくなるよ
2022/09/26(月) 11:47:57.47ID:ut+E4sGm0
そこでめぐる式よ 継続条件はwhile(abs(ok-ng) > 1)で答えはokに入る
2022/09/26(月) 12:49:10.56ID:QsR2IXV50
その式だけだとokがleftかrightか分からん
2022/09/26(月) 12:53:59.99ID:7xAfjatjM
別にleftでもrightでもどっちでもいいからバグらないと言える
位置関係より意味内容に忠実な表記
2022/09/26(月) 14:00:18.97ID:i/jndsoD0
ok、ngとかいいつつちゃんと定義域を渡さないといけないところらへんで、慣れてないひとは混乱するんだろうと思う
ok、ngではなくて、明確に定義域を指定するようなインタフェースに整えてあげると初学者には優しいでしょう

おれはいつも混乱しないように詳細を積めてから実装してるからok、ngなんて使わずhi、loで書いてるけど
2022/09/26(月) 14:31:20.74ID:QwvWOyok0
ok(ng)の初期値は条件が真(偽)だとわかっているところ
もしくは定義域の一個外にするけど
そんなに混乱するか？
2022/09/26(月) 14:51:56.76ID:i/jndsoD0
おれはしないから予想してるだけ
868デフォルトの名無しさん (ﾜｯﾁｮｲ 9210-A/T8)
垢版 |
2022/09/26(月) 15:55:48.24ID:50Eh55hb0
自分は二分探索、毎回コピペしてる
値が小さい方から大きい方にかけて、条件式がTrue, True, ..., False, Falseになるのと
False, False, ..., True, Trueになる2パターン用意しといて毎回コピペしてる
869デフォルトの名無しさん (ﾜｯﾁｮｲ 9210-A/T8)
垢版 |
2022/09/26(月) 16:10:31.34ID:50Eh55hb0
ん、めぐる式二分探索って、上の2パターンを一般化しますよっていう話か...
3年半も競プロしてんのに初めて知ったよ...
2022/09/26(月) 17:20:22.65ID:mM+PT8Od0
別にlo, hiやleft, rightの実装で全く困ってなければ知らなくてもいいと思う
位置と判定、境界を一緒に考えると頭がこんがらがる初心者にとって、めぐる式は判定関数とok,ngの初期値さえ与えておけば二分探索部分のコードは位置関係すら考えず貼るだけなので楽
2022/09/27(火) 00:33:47.81ID:OQZ1tOOg0
LRをどっちもokにしちゃうと無限ループしちゃうんだよな
まったくもう
2022/09/27(火) 00:51:50.39ID:ZwmfNOl50
あー、そういえば、めぐる式で一番重要なノウハウは、[left, right)の半開区間にすると処理が簡単、ってことだと思うわ

閉区間にすると考えることもコードも増えてキツイと思うんだけど、外人のコードだとかなり見かける
こないだのABC1位のひとでもこれでやってるんだよな
if check(mid)
l = mid + 1
else
r = mid - 1
2022/09/27(火) 01:56:33.69ID:f9wenpM60
中国って割と1-based・閉区間の派閥がいるイメージだわ
2022/09/27(火) 07:38:03.73ID:nRLJF7B50
取り敢えず区間扱うときは全て半壊区間が安定してるなぁ
2022/09/27(火) 10:17:28.55ID:RK9MOCkIM
そのあたりは情報処理能力やライブラリ化でごり押せるから、上級者でも筋の悪い実装方針でやってたりすることがあるイメージ
特に軽実装のAtCoderでは、まず算数パズルができるということが何よりも大事だから
876デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/27(火) 15:17:24.67ID:j2LDQh400
DAG上の最短路問題について普通のアルゴリズムとデータ構造の本には載っていません。
これはトポロジカルソート＋動的計画法によって、最短経路の求め方が自明だという考えからでしょうか？
2022/09/27(火) 15:31:56.76ID:ZwmfNOl50
さあ、ダイクストラでも大体十分だったりするから需要ないんじゃない？
2022/09/27(火) 16:05:50.65ID:RqBRw8Xlr
うんち
879デフォルトの名無しさん (ﾌﾞｰｲﾓ MM32-QTvv)
垢版 |
2022/09/28(水) 13:02:21.64ID:F+G1dH1CM
ABC263のDやってるんだけど、
kyopro_friendsさんの解説に出てくる累積minってググっても出ないんだけど、
nok0さんの解説のf(k+1)=min(f(k)+A[k+1], L*(k+1))のこと？
累積和使って最小値求めると、全体でO(N^2)になっちゃいますよね
2022/09/28(水) 13:33:58.07ID:E29MaAWV0
>>879
そのf(i)の意味を勘違いしてるかも。
例えばf(5)ならば、

①A1+A2+A3+A4+A5
②L+A2+A3+A4+A5
③L+L+A3+A4+A5
④L+L+L+A4+A5
⑤L+L+L+L+A5
⑥L+L+L+L+L

この６パターンの内の最小値って意味だよ
881デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/28(水) 15:59:44.30ID:B1p+YPuG0
AtCoder Problemsが独自に算出したという「difficulty」ってどこで見れるんですか？
882デフォルトの名無しさん (ｱｳｱｳｳｰ Sa43-q+3U)
垢版 |
2022/09/28(水) 16:24:44.67ID:cIcLbxtta
AtCoder Problemsで見れます
883デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/28(水) 16:38:42.88ID:B1p+YPuG0
>>882
Show DifficultyをONにしても表示されません。
884デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/28(水) 16:47:43.15ID:B1p+YPuG0
大槻のAtCoder入門を図書館から借りてきましたが、やさしすぎますね。
2022/09/28(水) 17:47:31.56ID:ZeFU5MB7M
>>883
左の円の色とか円の中のゲージがdifficulty
886デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/28(水) 18:08:29.44ID:B1p+YPuG0
>>885
ありがとうございました。マウスのポインターを円の上に持っていったら表示されました。
887デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/28(水) 21:41:22.84ID:B1p+YPuG0
大槻のアルゴリズムとデータ構造の本に、クラスカルのアルゴリズムの計算量が、
O(|E| * log(|V|)) であると書いてあります。

なぜ、 O(|E| * log(|E|)) と書かないのですか？
2022/09/28(水) 22:01:47.27ID:7KJ1BqpF0
文脈が分からないけど、単純グラフって仮定があるんなら|V|^2>|E|だからってことで深い意味はないと思う
強いて言えば|V|の方がlogのお得感が出るとか？
889デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/30(金) 12:34:13.21ID:aXocYaHs0
大槻のAtCoder入門という本に、頂点の数 N、辺の数 Mのグラフの構造の入力の受け取る処理に
O(N + M) の計算量が必要だと書いてあります。

O(M) が正しいと思いますが、どうですか？
890デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/30(金) 12:34:55.30ID:aXocYaHs0
>>888
ありがとうございました。
2022/09/30(金) 12:35:34.42ID:jkyVOJ86d
辺の数がゼロのグラフとか
2022/09/30(金) 13:36:02.20ID:DDlNV6wMd
入力長はO(M)だけどvectorの確保にO(N)かかりそう
2022/09/30(金) 14:19:09.50ID:LLOTX79E0
本当にグラフの構造情報を受け取るだけであればO(M)でいいけど、後続の処理で結果的にはO(N+M)かかることがほとんど
ただ、たとえばN=10^100, M<=10^5みたいなパターンの問題も考えうるから、O(N+M)よりはO(M)の方が正確かな、特に他に但し書きがないのであれば
かなり自明な話なので、そこのO(N+M)の記述で混乱して問題を解くのに支障が出る人はいない気がするけど
2022/09/30(金) 14:35:51.41ID:og+oo4X4a
すべて入力から受け取る必要があるならそら入力にO(N+M)かかるやん
入力の辺は重複しないみたいな条件がついてるなら、O(N^2)あるいはO(M)になったりする
895デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/30(金) 20:10:13.70ID:aXocYaHs0
>>891-894
ありがとうございました。

明日の午後9時からの「AtCoder Beginner Contest 271」に参加予定なのですが、
何問くらい解けるのが平均的なんですか？
100分しか時間がないのでおそらく2,3問しか解けないと思っています。
896デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/30(金) 20:13:19.02ID:aXocYaHs0
大槻の『AtCoder入門』という本を図書館から借りてきて第5章の中級編の最後まで読み終わりました。
そこまでの問題であれば、時間がかかったものが多いですが、すべて独力で解けました。
2022/09/30(金) 20:23:47.23ID:5Nix2QT6r
そうなんだすごいね
2022/09/30(金) 20:30:00.67ID:CkroVdQhM
大槻って呼ばれてるの違和感しかない
899デフォルトの名無しさん (ﾜｯﾁｮｲ 5f01-JEMU)
垢版 |
2022/09/30(金) 22:00:39.59ID:vp8mMnx50
東大出身のNTTなら敬称は殿だろね。
本もたくさん出してるし。
2022/09/30(金) 22:11:04.33ID:0jY5NHsN0
参加者の過去の成績や練習量はすべて公開されています
実力のある参加者は大量の問題を解いています
自分の成績が今ひとつでも気を落とさないことです
901デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/30(金) 22:17:34.52ID:aXocYaHs0
例えば、大槻の『AtCoder入門』という本の上級編の1問目の「abc115_d」の問題ですが、独力で解けました。
基本的なアイディアはすぐに浮かんだのですが、パスするのに1時間もかかってしまいました。
そして、練習を重ねてもこの時間を短くすることは難しいのではないかと思います。
902デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/30(金) 22:20:59.94ID:aXocYaHs0
あと一つ質問ですが、問題の解答(AC)を、計算時間の短い順にソートすると、上位の
解答の計算時間が異常に短いです。

ソースを見ても、アイディアは同じなのになぜあんなに速くできるのでしょうか？

計算時間のコンテストではないので、レーティング上は、あまり重要ではないと思いますが、
気になります。
2022/09/30(金) 22:53:54.54ID:LLOTX79E0
解ける問題数については、三問解ければまずOKで、あわよくば四問解くことを目標にするぐらいじゃないかな
初回参加だとC問題解けない人の方が多そうな気がするし四問解ければなかなかだと思うよ
ABCは毎週開催されるようなものだし、一回一回の結果を気にしない方がいい、特に最初は
レートには直近10回程度の結果が反映されるから、今回失敗しても続けてればすぐにその影響を消せる
あと、参加回数が少ないとレートがめちゃくちゃ低く算出される仕組みなので、パフォーマンスを自分の成績指標として見よう
2022/09/30(金) 23:07:02.91ID:LLOTX79E0
平均的な話をすると、どうなんだろう
AtCoderから競プロ始めた人だったら一から二完の間じゃないかな、そもそもプログラミング初心者も多いし
あと、上級者のコードが速いのは、再帰関数を非再帰にするとか、キャッシュ効率をよくするとか、入出力を高速化するとか、コンパイラのオプションを変えるとか、そういう細かい工夫の積み重ねだと思う
C++だったら別に意識しなくても問題ない気がするけど、Python使いだったら再帰を非再帰にするとか入出力高速化ぐらいはやっとくと、ABC-E問題以降楽そう
2022/09/30(金) 23:13:27.03ID:LLOTX79E0
つけくわえるとABC-Dまではかなり典型度の高い定型的な問題が多いので、練習すれば解答時間は縮められる方の問題だと思うよ
2022/09/30(金) 23:17:37.45ID:Hduo0GQQ0
レートでいうと100で上位50%みたいな感じだった気がするし、平均的なひとだったら最初は2完で上出来かね
強い人だと初参加でも3完か4完らへんをやってパフォ1000超えてるのが珍しくないけど
2022/09/30(金) 23:53:23.95ID:bglqOH/20
こどふぉもやりたいけど23時半から2時間ってのが微妙だな～
眠くなっちゃうんだよなぁ
2022/10/01(土) 00:16:22.62ID:LpkgDzWuM
社会適合者⁉
2022/10/01(土) 00:18:46.82ID:WF3iEAg30
末尾再帰で最適化できる言語もある
2022/10/01(土) 00:23:21.36ID:3jdVdEDLr
schemeだけちゃうんけ？仕様で定められてるのは
2022/10/01(土) 00:31:45.72ID:8aXdhr6R0
再帰だとPyPyよりもCPythonのほうが早いらしいけど、なんでそうなるのか気になる
912デフォルトの名無しさん (ﾃﾃﾝﾃﾝﾃﾝ MM7f-poG4)
垢版 |
2022/10/01(土) 20:55:59.80ID:w1pBwNBnM
ヒューリスティックコンテスト向けのおすすめ本ってあります？
913デフォルトの名無しさん (ﾜｯﾁｮｲ ff55-vqPj)
垢版 |
2022/10/01(土) 22:48:49.05ID:DVLayUHe0
A, B, Dしか解けませんでした。
Cはソートして、巻番号が小さい順に見ていって抜けている巻を、巻番号がもっとも大きな2巻を売って買う
ということを繰り返せば良さそうでしたが、実装が面倒だと思い飛ばしました。
2022/10/01(土) 22:50:22.12ID:8aXdhr6R0
Cは二分探索を使う解法にすれば実装がクソ軽いよ
915デフォルトの名無しさん (ﾜｯﾁｮｲ ff55-vqPj)
垢版 |
2022/10/01(土) 22:50:52.66ID:DVLayUHe0
>>903-906,909-911
ありがとうございました。
916デフォルトの名無しさん (ﾜｯﾁｮｲ ff55-vqPj)
垢版 |
2022/10/01(土) 22:52:49.49ID:DVLayUHe0
>>914
ありがとうございます。考えてみます。
917デフォルトの名無しさん (ｱｳｱｳｳｰ Sa27-XVJY)
垢版 |
2022/10/01(土) 22:52:51.85ID:CG2rPef9a
Cはにぶたんが楽だったな
愚直にシミュレートしたら3wa,2wa,1wa,1wa…って感じになったぴえん
2022/10/01(土) 22:53:56.43ID:8aXdhr6R0
>>917
おれもシミュレートしたけどWAを潰しきれなくて、二分探索にしたら瞬殺できてなんか悲しかった
919デフォルトの名無しさん (ﾜｯﾁｮｲ 6fbd-atM5)
垢版 |
2022/10/01(土) 23:00:56.33ID:zvX3MF2G0
8月から競プロ始めて現在レート337の雑魚

Dは楽だったけどCでwa出してしもうた。。
明日のレギュラーも参加するか
2022/10/01(土) 23:08:50.61ID:Ry8jupv50
(N-最初に持っている本で読む本の数)/2 >= (これまでの不足している本)で判定すれば別に二分探索もいらないと思うけれど
2022/10/01(土) 23:11:38.80ID:Ry8jupv50
Exってこれ典型なのかな？
解説見てみたらどことなくARCの難問っぽいけど
2022/10/01(土) 23:20:11.35ID:YhoWw2wyp
ABCのDまでは安定して解けるようになったけどEになった途端全然安定しなくなるのシンプルに過去問解き進めるしかないかな
2022/10/01(土) 23:21:52.81ID:YhoWw2wyp
というかCの制限時間が4秒だったのってどういう想定？二分探索でもシミュレーションでも割と余裕ある気が
2022/10/01(土) 23:25:52.82ID:Ry8jupv50
確かにCの制限時間よくわからないね
set使うと結構定数倍重くなるのかな？
925デフォルトの名無しさん (ｱｳｱｳｳｰ Sa27-XVJY)
垢版 |
2022/10/01(土) 23:28:08.04ID:CG2rPef9a
パスの復元じゃなくDpの値にそのままパスぶっ込むのでもokにしたかったとか？
2022/10/01(土) 23:28:38.05ID:Ry8jupv50
ABC-Eは典型90の内容抑えれば結構戦えるレベルな気がするなあ
あとEDPC埋めとかね
2022/10/01(土) 23:28:53.28ID:8aXdhr6R0
入力が 3 × 10^5 コ以上あるときは、解法に関係なく少なくとも3秒以上になってるような気がする
2022/10/01(土) 23:31:02.64ID:Ry8jupv50
2*10^5でもいい気がするけど、それだと速い言語で二重に走査するだけのO(N^2)回とかが通ったりすることがあるのかな
2022/10/01(土) 23:35:23.86ID:Ry8jupv50
てか2*10^5でO(N^2)が2secで通るんなら、3*10^5のO(N^2)も4secあれば通りそう
あとは初心者が筋の悪い入力受け取りをしていたときにそこのオーバーヘッドで落ちるのを予防するとかかな
930デフォルトの名無しさん (ｱｳｱｳｳｰ Sa27-XVJY)
垢版 |
2022/10/01(土) 23:35:36.10ID:CG2rPef9a
あ、dじゃなくcか
2022/10/01(土) 23:47:22.98ID:Ry8jupv50
HEX
2022/10/02(日) 00:22:19.74ID:3PZJtakoa
サンプルでWAを出すやつはこれを使え〜
https://greasyfork.org/ja/scripts/433152-atcoder-easy-test-v2
933デフォルトの名無しさん (ﾜｯﾁｮｲ 6f71-0qRf)
垢版 |
2022/10/02(日) 01:34:13.68ID:FZycuJqr0
なんか文句いってたら数え上げとXORの頻度が減った気がする。このあたりほんとアルゴリズムと関係ないので燃やすべし。
2022/10/02(日) 01:44:55.64ID:cj6ZUnIP0
G問題がちょうど数え上げ+XORだったけど
組合せ論嫌うのもよくわからないね
2022/10/02(日) 01:45:17.65ID:cj6ZUnIP0
あ、Fだった
936デフォルトの名無しさん (ﾜｯﾁｮｲ 6f71-0qRf)
垢版 |
2022/10/02(日) 01:55:00.10ID:FZycuJqr0
>>934
数年前はこの類が毎週出てて違和感しかなかった、統計学でも数理最適化でも観測範囲内で組合せ論は二項係数くらいしか役に立ってないハズ
2022/10/02(日) 01:58:26.63ID:rnPodEBd0
競プロは役に立たない
938デフォルトの名無しさん (ﾜｯﾁｮｲ ff10-UJKs)
垢版 |
2022/10/02(日) 02:03:38.75ID:m2kqJsOp0
C、線形で解こうとしたんだけど、謎の1WAが出て困ってる
同じ1WAの人結構いたけど、みんな二分探索に切り替えてACしてる
https://ideone.com/yD7l3P
誰か教えて欲しい
2022/10/02(日) 02:06:44.15ID:cj6ZUnIP0
「競プロは自分にとって離散数学パズルだ」ってりんごさんが言ってるし、整数論とかやるのと同じような立ち位置じゃないかなあ
そもそも初等組合せ論の考え方は初等確率論の基本なんだから、役に立たないというのも違うと思うしね
今回はGも数え上げ問題だったわけだけど、DP遷移部分について俺は幾何分布の考え方をイメージしたね
940デフォルトの名無しさん (ﾜｯﾁｮｲ 6f71-0qRf)
垢版 |
2022/10/02(日) 02:10:22.92ID:FZycuJqr0
>>937
そう、別に個人的にはそんなに嫌いじゃないんだけど、好む層の魂の元が中学入試あたりで、自然数の各桁の和とか数学的に大した意味もないトピックがやたらドヤドヤしていたのがちょっと不快。プログラミング、アルゴリズム、情報科学というより、IQ高めの算数エリートの娯楽という感じ。
2022/10/02(日) 02:12:42.56ID:cj6ZUnIP0
>>938
貯めてるsellが足りないときに貪欲に大きい方の本を売ってるけど、そこで順当にいけば読めるはずだった本売ってるんじゃない
一冊残しておいた方がいい場合とそうじゃない場合がある
2022/10/02(日) 02:17:08.77ID:cj6ZUnIP0
>>940
魂の元が中学入試なのはまあそうって感じ
俺も算数パズルや離散数学よりも比較的連続最適化とかの方が好きっちゃ好きだから分からなくもない
まあでもCSでは離散数学は基礎教養だし、離散数学と中受算数は親和性高いよね
943デフォルトの名無しさん (ﾜｯﾁｮｲ ff10-UJKs)
垢版 |
2022/10/02(日) 02:24:07.54ID:m2kqJsOp0
>>941
ありがとう ACできた
シミュレーションしながらsellを貯めていくのはダメで、sellをシミュレーションの前に計算するようにしたら通った
2022/10/02(日) 09:47:36.55ID:nZxo1B790
重複する本は∞巻目ということにしてからシミュレーションしてもうまくいくよ
2022/10/02(日) 11:05:00.45ID:bP9R5MM60
小数点の精度はどうすりゃいいのか未だに分からん
興味がないねんな…
946デフォルトの名無しさん (ﾜｯﾁｮｲ ff55-vqPj)
垢版 |
2022/10/02(日) 12:40:51.35ID:c1nVdKJ60
米田の新しい本を買いました。
PASTの公式本とどちらを先に読むか迷っています。
レス数が900を超えています。1000を超えると表示できなくなるよ。
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況