[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 59 (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
11: 2021/06/25(金)20:38 AAS
典型４３ってc++でpriority queue使ったダイクストラでACとれる？
12(1): 2021/06/25(金)20:39 AAS
取れる
13(1): 2021/06/25(金)20:42 AAS
>>12
なんか工夫とか気をつけるポイントとかある？
14(1): 2021/06/25(金)20:45 AAS
>>13
何に引っかかってるか知らないけどそんなに特別なことしてない
陽にグラフ作らない、とかそれくらいpriority_queueにtupleぶち込んでる
15(1): 2021/06/25(金)20:46 AAS
どうせ大きい順に取り出してるとか
16(1): 2021/06/25(金)20:51 AAS
>>14
まじか
priority queueだとTLEで01bfsだと通ったからlogで落ちてるのかとおもってたわ
もうちょっとみてみる
>>15
greaterで指定してるからそれは大丈夫っぽい
17: 2021/06/25(金)21:03 AAS
見たやつ枝刈りしてる？
18: 2021/06/25(金)21:17 AAS
>>16
通ったの1.2sくらいだから定数倍悪いとか枝刈りミスってると落ちるかも
19(4): 2021/06/25(金)21:33 AAS
このコードなんだけど
１つだけTLEになる
外部ﾘﾝｸ:paiza.io
20: 2021/06/25(金)21:42 AAS
>>19
pqに入れるときにcost更新してないからじゃね
21: 2021/06/25(金)22:16 AAS
外部ﾘﾝｸ:snuke.h%60tenablog.com/entry/2013/03/01/152108
すぬけさんでもやらかしてしまうやつ？
22: 2021/06/25(金)22:23 AAS
アドレス間違ったわ
外部ﾘﾝｸ:snuke.h%61tenablog.com/entry/2021/02/22/102734
はてなそのままじゃ貼れないからごにょっと
23: 2021/06/25(金)22:52 AAS
ここが新しいプログラマーの豚部屋なのね(´・ω・`)
24: 2021/06/25(金)22:58 AAS
オーダーレベルで悪い書き方はしてなさそう
pq に突っ込む前にコスト更新しとくと多少枝狩りが効くとか
vector<vector<vector<int>>> cost(h, vector<vector<int>>(w, vector<int>(4, inf)));
を
vector<vector<vector<int>>> cost(4, vector<vector<int>>(h, vector<int>(w, inf)))
にすると早くなるかも
25(1): 2021/06/25(金)23:06 AAS
こういう教え合ってるのプログラマー板って感じしていいね
26: 2021/06/25(金)23:11 AAS
🥬
27: 19 2021/06/25(金)23:29 AAS
いろいろ教えてくれてありがと
すぬけさんのブログの最後に書いてあるおまけ（定数倍）のやつをやったら通るようになったので
定数倍が悪かったっぽいです
28: 2021/06/25(金)23:59 AAS
>>25
いいよね
この調子で反ワクチン派も啓蒙していこう
29: 2021/06/26(土)02:06 AAS
お前らってホント偏差値大好きっ子だよな
きもちわる
30: 2021/06/26(土)08:44 AAS
えびちゃんちゅっ
31: 2021/06/26(土)12:27 AAS
典型90にいつも引用RTしてる人、解けないときも律儀に解けませんでしたって言っててかわいい
32(1): 2021/06/26(土)12:32 AAS
典型90の072で、同じマスを通らず上下左右に移動する経路が高々28512通りってどうやって出るんですか。
感覚といってるぐらいだから簡単に出るんだろうが、さっぱり思いつかん
33: 2021/06/26(土)12:37 AAS
簡単に出ないから感覚って言って誤魔化してるんでしょ
34: 2021/06/26(土)12:42 AAS
1^4 * 2^8 * 3^4 = 20736だから最初の方向を決めるのを考慮しても40000くらいでは抑えられるんじゃね
35: 2021/06/26(土)12:46 AAS
どういう式かわからん
36: 2021/06/26(土)12:47 AAS
ワクチン妄信派も未来のことは説明できないから感覚で誤魔化して他人をバカにしまくってるしな
37: 2021/06/26(土)12:49 AAS
感覚が大事は分かるが、オーダー見積もり式ぐらいないと再現性なさすぎて無理。
38: 2021/06/26(土)12:53 AAS
>>32
第5回 PAST G が似た問題で、もっと荒い評価の式が解説に書いてある
39: 2021/06/26(土)13:01 AAS
脳がなければ脳死DPで求めなさい
40: 2021/06/26(土)13:05 AAS
4*4の盤面で全探索間に合わなかったら直感的に嫌な気持ちになる
41: 2021/06/26(土)13:11 AAS
4*4で全探索無理で式たててねなんて問題があったらすごいけど想像もつかない
42: 2021/06/26(土)13:13 AAS
駒の種類が1e18ぐらいある将棋
43: 2021/06/26(土)13:15 AAS
AHCやれよカス共
44: 2021/06/26(土)13:17 AAS
5ch書き込みながらやることでハンデをやってる
むしろ感謝して欲しい
45: 2021/06/26(土)13:18 AAS
まあそもそもこのスレで話題に出さない方がいいんだよね
46: 2021/06/26(土)13:22 AAS
俺は全くやる気ないし問題見てもないけど、コンテスト出ながら5chとかリスキーだろ
ぽろっと感想こぼしたらギルティーだぞ
47: 2021/06/26(土)13:28 AAS
集中力切らして冷えた時の言い訳なんだからどうでもいい
48: 2021/06/26(土)14:35 AAS
AHCは過疎ゲー
49: 2021/06/26(土)14:46 AAS
初心者なんですけど質問良いですか
50: 2021/06/26(土)14:50 AAS
hai
51: 2021/06/26(土)14:55 AAS
灘コンやってた
52: 2021/06/26(土)15:11 AAS
過疎ゲーの割に出れば勝てるタイプの過疎り方してないからなあ
53: 2021/06/26(土)15:14 AAS
大体のネトゲの末期は荒野で廃人モヒカンが跋扈してるよ
54: 2021/06/26(土)15:14 AAS
6時間ってなんか半端でやりたくないな
途中で切り上げるのも気分よくないし
かといって続きは明日やろうってできる長さじゃないし
55: 2021/06/26(土)15:20 AAS
ARC-Fまでの数学が1冊でカバーできる、競プロの数学解説本を誰か書いてくれ
範囲が膨大すぎて、何をやればいいのか分からない
56: 2021/06/26(土)15:23 AAS
さすがに需要なくて無理だろ
競プロに人生捧げた狂人が書いてくれるかもしれんが
57: 2021/06/26(土)15:24 AAS
需要がないとまでは言わんがその辺から先は自分で学んでこいと言う話になりそうだ
58: 2021/06/26(土)15:27 AAS
数学なら大したことないだろ
数オリ未満の範囲
群論とかほとんどファッションレベルだし
問われる知識の多さよりもその知識を使う問題に帰着させるのがムズい
59: 2021/06/26(土)15:35 AAS
要は数オリの網羅的な教材を競プロ向けに改造してプラスαしたものだな
60: 2021/06/26(土)15:43 AAS
まあ突然カタラン数とか言われて解けるわけねえだろってなっちゃったし、知ってれば解ける系はせめて抑えておきたい気持ちはわかる
61: 2021/06/26(土)15:44 AAS
grundy数とか出てくるし、それなりに意義はありそうだけど
数学として学ぶには浅い知識で十分すぎるし、かと言ってしっかりやるには範囲広すぎるし
結局各自で頑張っていくぐらいしかない気がする
62: 2021/06/26(土)15:59 AAS
pythonなんですけどリスト（配列）って変数 ＝ [ ]のこのかっこで作成できるじゃないですか
atcoderで人の解答見てると変数＝[0]のようにかっこの中に0があることが多いんですけどこの0って必要なんですか
A = [0] + list(map(int, input().split()))
みたいな感じで
かっこの中空じゃダメなのかなって
63(1): 2021/06/26(土)16:03 AAS
それは番兵置いたり1-indexedで添字がずれないようにするためだな
64: 2021/06/26(土)16:27 AAS
質問サイトとして少しでも機能している点でこのスレの存在価値はあるな
65: 2021/06/26(土)16:29 AAS
宇宙を創造した神がこのスレに存在価値はないと言っていたぞ
66(1): 2021/06/26(土)16:50 AAS
カタラン数はちょっと数学できる高校生なら普通に知ってるので
それ知らんのはあんまり高校で数学頑張らなかっただけだぞ
67: 2021/06/26(土)16:52 AAS
「ちょっと数学できる」の範囲が曖昧すぎるだろ
68: 2021/06/26(土)16:58 AAS
チョットデキル
69: 2021/06/26(土)17:34 AAS
AHC参加者少ないな
オワコンなの？
70: 2021/06/26(土)17:35 AAS
AHCやらない奴らがAtCoderからしたら終わったユーザー
略してオワユザ
71: 2021/06/26(土)17:38 AAS
土曜の昼〜夕方六時間丸々なくなるのはよっぽど気合い入ってないと厳しい
72: 2021/06/26(土)17:41 AAS
カタラン数とかチャート式で2ページ丸々使って解説するぐらいには高校数学の範囲だし
数学が嫌いじゃないなら知ってて当然かと思ったけど
73(1): 2021/06/26(土)17:46 AAS
>>66
そうなの？一応京大理系だけど本当に聞いたこともなかったから頑張ってなかったのかも
やっぱ東大生の人たちには常識なのかな
74: 2021/06/26(土)17:48 AAS
受験イキリきっしょ
75: 2021/06/26(土)17:55 AAS
まあ別に知らなくても東大数学やら京大数学で高得点取ることはできると思う
76: 2021/06/26(土)18:01 AAS
知らなくてもいいってのはその場で再発明できる程度の問題が多いからというのがある
カタラン数という概念を認識してなくても解ける
77: 2021/06/26(土)18:02 AAS
チャート式の色は？暖色？
78: 2021/06/26(土)18:10 AAS
またガイジがガイジバトル始めてんのか
79: 2021/06/26(土)18:15 AAS
外部ﾘﾝｸ:tsuchi.hateblo.jp
純粋培養黄色ってテクノロジ系7割も取れないもんなんやな
80: 2021/06/26(土)18:23 AAS
白カピ呼んで来い
81: 2021/06/26(土)18:28 AAS
合格できりゃ別にいいだろ
82: 2021/06/26(土)18:51 AAS
仮に合格点が7割だったら8割は取るだろ
たかが資格、合格できれば何も問題はない
83: 2021/06/26(土)19:28 AAS
夢見ることが全て始まり それが答えだろ
84: 2021/06/26(土)19:29 AAS
>>73
前にも、知らなくても東大合格できるの書き込みあったから
チャート式信奉者かどうかの違いでしょ
85(1): 2021/06/26(土)19:53 AAS
>>63
62の答えってこれでしょうか
どなたかこれをわかりやすく教え欲しいです
[ ]の中を空にしたらエラーになるのでしょうか
そうならとりあえずこれから[ ]の中に0入れとこうと思うのですが
86: 2021/06/26(土)19:55 AAS
ヒューリスティック前回まで1000人くらい参加者いたのに今回は600人か。存続危うそう
87: 2021/06/26(土)20:09 AAS
>>85
エラーにはならない
そもそも意味が違う
[]は空のリスト
[0]は要素数が1でその要素がゼロのリスト
88: 2021/06/26(土)20:28 AAS
ここ数年で増えた競プロユーザーって毎週参加できて一回二時間程度で済むというお手軽感が好きな人が多いでしょ
あとは受験数学や競技数学っぽいゲーム性が好きな人
マラソンってやっぱ人を選ぶよ
89: 2021/06/26(土)20:33 AAS
面白そうかどうかって言われると面白そうだと思う
ただあまり時間とれないし、同じぐらいの実力だと当然時間をたくさんかけた人に負けるので、出ようという気がなくなる
90: 2021/06/26(土)20:36 AAS
焼きなましの具体的なやり方がいまだに分からない
91: 2021/06/26(土)20:38 AAS
ヒューリスティックのレートが中々web実装されないのもある気がする
モチベ湧かない奴いるだろ
上下前次1-新書関写板覧索設栞歴
あと 911 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.037s