競技プログラミングにハマるプログラマのスレ 157
■ このスレッドは過去ログ倉庫に格納されています
昨日のDみたいに低級インコが過学習で嘘dpに走ってしまうこと? 百烈なめなめdpは落とせてもbfsdfsを落とせるか不安になってきた DAG度が高いほど百烈舐めDPが通るから、DAG性を評価するためのいい感じの指標になったりしないか >>34
vl dp(n,LLONG_MAX-100000);
dp[0]=0;
rep(i,2400){
rep(j,n-1){
dp[x[j]-1]=min(dp[x[j]-1],dp[j]+b[j]);
dp[j+1]=min(dp[j+1],dp[j]+a[j]);
}
}
昨日のDのこんな感じのコード 嘘貪欲の通りやすさで対象の複雑さを測るの面白い気がしてきた 平面グラフとかは一般グラフだと嘘みたいなアルゴが通るしな 百烈なめなめdp、最初と最後だけ百烈して途中は更新点から100歩だけ歩くみたいな舐めた枝刈りができる ダイクストラがすぐ見えない頭脳はトレースしたくないけど、質の良い嘘貪欲を思いつく能力は結構欲しい
というか精度高めればAGCとか強くなりそう >>39
130 赤コーダー
100 東大理三
70 東大理一
赤コーダーは理三より確実に難しい
agerにはわからないだろうが >>47
chokudai1浪で東工大と早慶理工落ちてるが ちょくが外れ値なのを界隈に長くいても気づけてない学習力、これがager 大受能力と競プロ能力は強い相関ないって何回言われてるんだよ デアの話題に混ざれないからまた「構って構って!」ってagerが騒いでるよ
Dの話題でこれだからD解けてない疑惑があるな N
X X 2
X X 3
…
X X N
X X 1 ←うーん、strongly connected!w SCCはpathのあるなしの評価だから、最短経路問題みたいな最適化問題にはそのままだと向かない的な >>50
非UTの赤コーダー多いし別に外れ値じゃないだろ
東大理三の赤コーダー率は高いし東大理三100赤コーダー90はガチだろうな 負辺あり最短経路問題をベルマンフォード法で解くとき、どれだけ辺の緩和をサボれるか、だと僅かに実用性ありそうだな (ダイクスタラとかベルマンホードみたいな難しい話してないで僕にかまって!低知能の僕でも分かる学歴トークして!) 百烈なめなめdpをランダムケースで落とすの割と不可能だな
1→3→2→4みたいな尺取型の移動が最適解ってのを2000回以上、無理だろ 単純なDAGだと勘違いしたDPを落とすのは確認しても(普通にランダムでも落ちるだろうし)、まさか2000回もやるとは思わんだろうね 過去スレ精進した
中学生でヒューリスティックなdpに到れるのはシンプルに凄い
渋幕だから地頭が良い子なんだろうな ダイクストラ法が分からなくても一生懸命考えて気合いでACできるような子だから超難関中学に受かったとも考えられる 中2でこれは凄いなと思ってAJL見たら上位は黄タッチしててレベチだった
怖いなぁ テストケースがランダムなら普通に通るか
こんなん簡単に落とせるのにテストケースかなりいい加減だったんだな >>71
最適解で通る辺の数がDPで回す回数以下なら全網羅できてACする Auxiliary Treeで典型90の35問目を解けるらしいがどうやってやるのか誰か教えてくれ Auxiliary Treeは理解した気になったがわからない 理一黄コーダーくらいが一番理三コンプ持ってそうだよな 百烈なめなめは分かっていれば簡単に落とせるが分かっていないとまず落ちない
適当に逆順ケースを入れるだけだと打ち切りありなめなめで通せるし あと舐める方向が半分の辺とうまく噛み合ってるので、最短経路が含有する後退辺の数が多くないといけない ダイクストラより思いつくの難しいし嘘解法というほど無根拠でもないから無理して落とす必要のない解法では >>63
非UTの赤コーダーが多いのは周知の事実
わざわざサンプル数を書くまでもない 造語症の奴がいるがただのループ回数決め打ちのベルマンフォードだろ 完全なベルマンフォードじゃないからループ回数決め打ちのって接頭辞つけたんだろ ループ回数決め打ちベルマンフォードはかわいくないため 軽いとはいえ計算量10^9近いのに通っちゃうんだな minはaddやandorxorの次くらいに軽い気持ち マーーーータ低学歴アンド低レートコンビのメェジィが暴れてんのか
どうやったらそんなところに進学しちゃうんだ? 共テがアドホック笑とか本気で言ってるから明治ってそういうレベルなんだなって この調子でARC頻度を増やしてAC射精完了で満たして欲しい 言うほどager暴れてた?
どれ?
打ち切りベルマンフォードで通してる人が居るって話じゃないの? 数時間前のスレ精進してから言ってる
全員が常に5chに張り付いてると思うな 自己主張は控えめでありながら、内に確かな実力を宿している、「眠れる獅子」のような東大生は結構いるが、労働市場では、「イキれる狐」に負けてしまう局面が多いという悲哀がある。 >>73
ベルマンフォードだな
writerが悪い
snukeは何してた?監督しろ 昨日のABC-Dなんて2、3分くらいで溶けるからマジで何でもいいよ
前のボス問既出レベルとかならまだわかるけどインコ問で騒ぐな 最初全ステージクリアかと誤読してクラスカルかいてた 最近MST見てないな
unionfindの良い応用なんだからそろそろ出していいぞ 最小有向全域木、パット見簡単そうだがサンプルコード長すぎて禿げた 最近ずっと非道い、毒ジュースが最悪
スポンサー名冠してこれはない
手抜いてるwriter誰だ? 毒ジュース回も酷いけどセグ木dp回が一番かな
検索して一字一句変えずにコピペすればAC出来てしまうから ベルマンフォードの一種ではあるが、グラフの特殊性がたまたまうまく活きるタイプだから、これを落とせというのは難しい
ハックケース作れる(前スレ901)ので競プロ的に正しい解法でもないが マーーーーーータ1日かけてバグを埋め込み頭の悪さを証明してしまった
うーんち!うんち!うーんち!うんち!
うーんち!うんち!ぶりぶりぶり!w ABCは典型でいいとか緑水枯渇とか嘘臭すぎな、ただの手抜きだろ 4完早解き
そろそろ俺もdiv1かね
EとかDP滅茶苦茶苦手だけど
前のevalとか完全にDP見えてなかったし 緑水枯渇はわからんこともない
ライブラリ窃盗集団と典型過学習erがダンピングするから典型要素でのdiff安定がはかれない ライブラリ窃盗するなとかいうやつは、STLや浮動小数点数も自分で実装しろ そのうち著作権とかライセンス汚染をロンダリングするリファクタリング動作にAIが使われるだろう
そういうの得意でしょAI 毒ジュースはトヨタコンでこれ?という気持ち
インコというよりチョクダイが舐められてそう CPUアーキテクチャ窃盗許せない
自分で設計して下さい 心の中の安倍晋三に意味のない人生だよって否定されてる
自民党嫌い ■ このスレッドは過去ログ倉庫に格納されています