競技プログラミングにハマるプログラマのスレ 42

■ このスレッドは過去ログ倉庫に格納されています
2021/03/20(土) 20:20:58.55
競技プログラミング、オンラインジャッジ、プログラミングコンテストやCTFに関する雑談スレ
次スレは>>950

AtCoder https://atcoder.jp/
yukicoder https://yukicoder.me/
Codeforces https://codeforces.com/
Project Euler https://projecteuler.net/
CLIST https://clist.by/
AtCoder Problems https://kenkoooo.com/atcoder/
AtCoder Clans https://kato-hiro.github.io/AtCoderClans/

※前スレ
競技プログラミングにハマるプログラマのスレ 41
https://medaka.5ch.net/test/read.cgi/prog/1615804518/
2021/03/20(土) 20:27:15.64
僕のセグ木が爆発しちゃうよー
2021/03/20(土) 20:53:26.52
テンプレ追加
AIZU ONLINE JUDGE (AOJ) https://onlinejudge.u-aizu.ac.jp/home
Topcoderリンク集 https://codeforces.com/blog/entry/21879
2021/03/20(土) 23:05:34.39
今回のAってABC178のBとほぼ同じだよね
全体的に一色分ズレてきてない？
2021/03/20(土) 23:10:14.04
見てきたけどそうでもないような
2021/03/20(土) 23:12:02.91
もなみちゃん…
2021/03/20(土) 23:12:59.57
すぬけの録画中に地震起こってて草
2021/03/20(土) 23:13:26.15
悔しくて泣きそう
2021/03/20(土) 23:15:26.81
max(a,b)-min(c,d)とかしてしもうた。恥ずかしい
2021/03/20(土) 23:15:52.14
>>8
泣いていいんだよ
皆んなで嗤ってあげるから
2021/03/20(土) 23:17:48.90
すまん、Fはconvolution貼るだけなのに解けなかった雑魚おるか？
2021/03/20(土) 23:18:13.01
はい
2021/03/20(土) 23:18:51.53
>>9
こっちは二重ループしたぞ
2021/03/20(土) 23:19:45.30
Dは典型？
Eの関数合成も典型か？

悲しい
2021/03/20(土) 23:19:46.28
>>4
引き算だから掛け算よりも解は自明だし
最悪全探索もできる (そのBはできない)

>>全体的に一色分ズレてきてない？
そのBのdiff52だけど一色分とは
2021/03/20(土) 23:20:14.74
むしろACLに含まれてる関数って貼るすらしないだろ
2021/03/20(土) 23:20:27.73
ぼくすぬけよろしぬけ
2021/03/20(土) 23:21:51.64
D典型っていうのかな
制約が異常に小さいときは全探索しろっていうのは典型っちゃ典型なんだけど、要は何の技巧も使ってない愚直解だから違和感がある
19仕様書無しさん
垢版 |
2021/03/20(土) 23:22:26.63
Eの何がFilterなんだって思ってたけどグラフ見たら確かにフィルタだ
2021/03/20(土) 23:23:26.88
Dは典型力じゃなくて完全に実装力不足だわ
なんで再帰関数で書かなかったんだろ自分
2021/03/20(土) 23:23:29.15
bit全探索の変形と考えればいいんじゃね
言うほど状態の持ち方愚直じゃない気も
2021/03/20(土) 23:23:43.30
再帰で全探索するっていうのはよく出るし書けないとおかしい
2021/03/20(土) 23:24:36.23
>>22
いやーその通りだな
反省だわ
2021/03/20(土) 23:24:59.38
Dは典型というか基本って感じじゃね、全探索だし
2021/03/20(土) 23:25:57.71
>>15
想定解としての発想が同じもの要求してるかなと思ったんだけど
一色分は間違いだね、最近前までの難易度と100点ずつぐらいズレてるような気がしてる
26仕様書無しさん
垢版 |
2021/03/20(土) 23:26:53.62
https://twitter.com/Monami_kanikani/status/1372821519605276673
https://atcoder.jp/users/kanipanunu
もなみー！そろそろ灰色になりそうなんだけどスパチャ送れば精進してくれるか？！
https://twitter.com/5chan_nel (5ch newer account)
2021/03/20(土) 23:27:26.15
D相手になんか難しいことしすぎてしまった…
2021/03/20(土) 23:28:45.69
レート下がったときに報酬送るとか学習の原則から考えるとダメだろ
2021/03/20(土) 23:30:41.81
もなみに複垢メソッド伝授するか
2021/03/20(土) 23:33:52.75
こんかいのもなみの成績だれか貼ってくり
2021/03/20(土) 23:34:30.20
蟹江もなみが精進したときに現れて颯爽とスパチャ送っていくおじさん　必要だろ
2021/03/20(土) 23:35:11.96
https://atcoder.jp/users/kanipanunu/history/share/abc196
2021/03/20(土) 23:35:44.30
おれはDP書いたぜ！
サンプル1で24が出力されてなんでだと思ってたら置く順番ごとに足してて3!がかけられてた
2021/03/20(土) 23:36:03.89
AB2完だよ
2021/03/20(土) 23:36:53.29
今回の不正は？
2021/03/20(土) 23:38:42.48
DPも全探索もダルいなーと思って5分考えたけど何も思い浮かばずしぶしぶ全探索を書いた
重実装が好きな人って存在するの？
2021/03/20(土) 23:39:31.12
重実装というほどのものでもないだろ
2021/03/20(土) 23:40:20.93
でもめっちゃDっぽい問題で俺は好きだよ
バグらせなかったし
2021/03/20(土) 23:43:54.59
きりみんぱいせんより弱くない？
2021/03/20(土) 23:45:48.18
いや、体調崩しただけでしょ
ポテンシャルは青後半はある
2021/03/20(土) 23:51:46.28
今回は本当に久々のプログラミングコンテストだった
ここ暫く数学パズルコンテストが続きすぎてた
42仕様書無しさん
垢版 |
2021/03/20(土) 23:54:47.44
EとFは数学パズルなので数学パズル回
2021/03/20(土) 23:54:54.28
今回ウマやら取材やらで雑魚新規が増えてパフォかさましされてる？
レーティング計算式分かんないから下が増えて上に影響するのか分かんないけど
2021/03/20(土) 23:57:12.65
>>40
うにさんチッス
2021/03/20(土) 23:57:54.36
数学のできないプログラマが使い物になるかい
2021/03/21(日) 00:00:19.03
E解説のminとmaxの合成ってどうしてこう変形できるんだ…？

こういうのってどっかに載ってる？
2021/03/21(日) 00:06:25.54
https://twitter.com/probably_uni/status/1372949199487000578?s=20
https://twitter.com/5chan_nel (5ch newer account)
2021/03/21(日) 00:06:38.91
y=xのグラフを書きます
max,min,足し算をするとグラフの形がどうなるか考えます
高々 2点でグラフの傾きが変わることがわかります
コードを書きます
おわり
2021/03/21(日) 00:09:21.27
解説の g(f(x)) の 2行目->3行目の変形の話じゃないの
2021/03/21(日) 00:11:08.27
意識としてはmin, maxを整理しようというよりは、関数の形考えて関数を特徴づける3つの値が合成によってどう変化するのかを考えたらこうなるって話じゃないか
min, maxの合成はいつでもこう変換できるみたいな定石はあるのかもしれないけど聞いたことない(束論っぽい)
2021/03/21(日) 00:12:07.07
これって
min(a, max(b, min(c, max(d, e))))
が
min(min(a, c), max(b, d, e))
に変形できることを示してるわけだけど、本当にこうなるん？
2021/03/21(日) 00:13:24.73
要するに裏では場合わけで三つの特徴量を別個に計算してるから、本来そんなに一行でできるほどスムーズな式変形じゃないよってこと
2021/03/21(日) 00:15:06.09
a, b, d, e > c の時にぶっ壊れてる気がするんだけど
2021/03/21(日) 00:16:52.98
>>51
頭死んでるから一番簡単な証明方法を書くけどa,b,c,d,eに0から4の順列を割り当てて全部の場合で常に等しかったら大丈夫じゃない
2021/03/21(日) 00:17:38.91
あー関数の形を考えればうまく変形できることはふんわり理解できたわ
2021/03/21(日) 00:17:49.80
って思ったけど c_2 は b_2 以下になってるから大丈夫なのか
2021/03/21(日) 00:17:57.08
>>53
ほんとだ
ダメじゃん、草
2021/03/21(日) 00:18:15.24
逆だった
2021/03/21(日) 00:18:46.52
>>56
そういえばそんな条件あったな
やっぱいけるじゃん
よかった
2021/03/21(日) 00:19:09.39
>>54
競プロらしくていい方法だと思うぜ
2021/03/21(日) 00:21:13.76
つまるところad hocな条件使うからmaxとminの一般論でできる合成じゃないね
だからそういう公式はなさそう
2021/03/21(日) 00:25:02.05
>>56
なるほど！
2021/03/21(日) 00:25:02.22
グラフ上で考察した結果を日本語で書くと冗長だから式で表してるだけだ思う
2021/03/21(日) 00:28:32.83
わざわざグラフなんか書かなくても環を知ってれば終わり
2021/03/21(日) 00:28:43.73
フィルター関数の形状を先に考えれば自然とこの合成式になるのかー納得

そう考えるとフィルター関数そのものが一種の典型と呼べてしまうのか
2021/03/21(日) 00:29:32.08
本当に終わりか？
説明してくれ
2021/03/21(日) 00:32:45.63
あー
じゃあこれ「t=4の時、非負数でk倍する」みたいな操作があってもおそらく同様に解けるのか？
2021/03/21(日) 00:35:13.60
僕の知ってる環は二つの演算のうちかたっぽでアーベル群だよ
2021/03/21(日) 00:36:08.17
掛け算出てくると傾き変わるのめんどくさいからやだ
解けるけど
2021/03/21(日) 00:36:14.31
>>67 解けるけどすぐオーバーフローしそう
2021/03/21(日) 00:37:12.85
HWという表現の罠
atcoderは全部これで統一されてんのかな
2021/03/21(日) 00:38:12.89
H→Wの順番が嫌ってこと？H×Wの掛けるがないのが嫌ってこと？
2021/03/21(日) 00:39:00.14
>>70 だけど傾きが切り替わる点がたくさんになりうるからキツイか
勘違いしてたわすまん
2021/03/21(日) 00:39:05.03
よくわかんないけどH,W≦16と見間違えたって話じゃない
2021/03/21(日) 00:40:26.17
E の解説の行間埋まらねえんだけどこれ解説間違ってないか?
clamp する範囲は狭まりはするけど広がりはしないはずだしこれは広がりうるように見える
76仕様書無しさん
垢版 |
2021/03/21(日) 00:40:34.75
単体で出るなら分からんでもないけど
2A+B=WHがある以上、問題文ちゃんと読んでねとしか言いようがない
2021/03/21(日) 00:41:25.31
>>75
頭ついてなかった、ちゃんと狭まってる
2021/03/21(日) 00:43:01.09
>>73
傾きが非負数である限りは常にフィルター関数形=min(high, max(low, a * x + b))で表せないかな？
79仕様書無しさん
垢版 |
2021/03/21(日) 00:48:50.66
可換モノイドだから成り立つね
2021/03/21(日) 00:51:43.17
>>67
負の数あっても大丈夫だと思う
2021/03/21(日) 01:01:05.48
そろそろ黙ろうか
ここまで我慢したけどもう耐えられないわ
ちょっとマジメに黙れ
2021/03/21(日) 01:03:00.32
>>80
関数の形状が反転するけど別に大丈夫か
2021/03/21(日) 01:06:15.30
>>81
誰に言ってたんだこいつ
統合失調症？
84仕様書無しさん
垢版 |
2021/03/21(日) 01:07:17.72
F典型っぽいけど170人しか解いてないの少し安心するな
2021/03/21(日) 01:08:15.79
>>79
可愛いモノイドに見えた
2021/03/21(日) 01:09:49.19
それぼく
87仕様書無しさん
垢版 |
2021/03/21(日) 01:10:12.90
モノイドは確かに可愛い(響きが)
88仕様書無しさん
垢版 |
2021/03/21(日) 01:13:27.66
Eはbeats貼るだけだから緑diff相当だろ
89仕様書無しさん
垢版 |
2021/03/21(日) 01:17:14.69
マジレスするとACLセグ木貼るだけでも緑上位なんだから、beats貼るだけで青最下位は普通じゃね
2021/03/21(日) 01:19:04.39
お願いだからぼくのかわいいびーつちゃんを広めないで
2021/03/21(日) 01:19:48.85
>>78 表せるね、二重に勘違いしてたわごめん
2021/03/21(日) 01:23:55.20
Python勢だけどDは状態をリストで管理して再帰で解いたけどリストの受け渡しが最初参照渡しになってるのに気付かず無限に時間溶かしてしまった
2021/03/21(日) 01:31:16.33
参照の値渡しな
2021/03/21(日) 01:32:38.13
明日のARCで銀パフォ欲しい
2021/03/21(日) 01:32:39.91
>>79
E？可換ではなくないか？
96仕様書無しさん
垢版 |
2021/03/21(日) 01:32:52.26
ちょっとお前らマジで黙れって言ってるのわからないの？
ふざけるのもいい加減にしろ
2021/03/21(日) 01:33:41.32
あー確かにEはセグメント木beatsで解けるのか
区間max更新と区間min更新の両方ができるの便利だなあ
2021/03/21(日) 01:35:20.40
beatsってどんなインターフェースあるの
2021/03/21(日) 01:36:05.97
Eみたいなデータ構造持ってると貼るだけになるやつ、
ABC以外では決して出ないせいでABCがそういう問題のごみ捨て場になってる気がするんだよな
2021/03/21(日) 01:41:37.51
beats、これまで勉強を放置してたけど、よくよく考えたら区間min、max、update、add更新全部できるのめちゃくちゃ強いな
2021/03/21(日) 01:45:26.36
機能追加って大体定数倍とトレードオフだと思うんだけど実際どのぐらいの速さなの？
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況