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

**仕様書無しさん** · 2024/02/03(土) 19:58:14.59

競技プログラミング、オンラインジャッジ、プログラミングコンテストやCTFに関する雑談スレ
次スレは>>950

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

前スレ
競技プログラミングにハマるプログラマのスレ 146
https://medaka.5ch.net/test/read.cgi/prog/1703956202/
競技プログラミングにハマるプログラマのスレ 147
https://medaka.5ch.net/test/read.cgi/prog/1704285340/
競技プログラミングにハマるプログラマのスレ 148
https://medaka.5ch.net/test/read.cgi/prog/1704789393/
競技プログラミングにハマるプログラマのスレ 149
https://medaka.5ch.net/test/read.cgi/prog/1705206444/
競技プログラミングにハマるプログラマのスレ 150
https://medaka.5ch.net/test/read.cgi/prog/1705581588/
競技プログラミングにハマるプログラマのスレ 151
https://medaka.5ch.net/test/read.cgi/prog/1705833561/
競技プログラミングにハマるプログラマのスレ 152
https://medaka.5ch.net/test/read.cgi/prog/1706002843/
競技プログラミングにハマるプログラマのスレ 153
https://medaka.5ch.net/test/read.cgi/prog/1706339660/
競技プログラミングにハマるプログラマのスレ 154
https://medaka.5ch.net/test/read.cgi/prog/1706611293/

**仕様書無しさん** · 2024/02/04(日) 00:02:09.24

modで掛け算やるだけです
Hack無いなら乱択しなくて良い

**仕様書無しさん** · 2024/02/04(日) 00:02:24.75

>>175
modをとって演算をさぼるというのが典型ということか?(文字列hashなど）

**仕様書無しさん** · 2024/02/04(日) 00:02:57.92

乱択乱択言ってるインコ本当に理解せずに解説をオウム返ししてるんだなって感じてしまうな

**仕様書無しさん** · 2024/02/04(日) 00:03:05.22

乱択というかハッシュ化が本質だな

**仕様書無しさん** · 2024/02/04(日) 00:03:54.75

確かに

https://twitter.com/ngtkana/status/1753788442406998165
https://twitter.com/thejimwatkins

**仕様書無しさん** · 2024/02/04(日) 00:04:20.78

>>177
modを取るというか愚直に比較すると無理な場合はハッシュ化すると良いことがあって(ロリハでもそう)、ハッシュ化してしまうと衝突しがちだから複数ハッシュとって衝突確率を下げてるということ

**仕様書無しさん** · 2024/02/04(日) 00:05:47.09

水青ぐらいのインコでもARCに出たくなる回だった
戦略的には実は好手かもしれない
さすがに赤コーダーが運営している以上、深遠な策が奥にある可能性がある

**仕様書無しさん** · 2024/02/04(日) 00:06:17.85

今回のFみたいなのを乱択で抽象化してしまうような抽象化能力のインコもいるんだったら確かに黄タッチ全員本当にやれば出来るっていう主張も嘘になってしまうかも

**仕様書無しさん** · 2024/02/04(日) 00:07:19.15

Goodbye 2023並みの回だ

**仕様書無しさん** · 2024/02/04(日) 00:07:57.76

G平方分割TLEして悲しい

**仕様書無しさん** · 2024/02/04(日) 00:08:45.00

judgeが壊れてたりAGC格だったのにあれだったGoodbye 2023に並ぶのはさすがにむずかしいが、大概な回ではある

**仕様書無しさん** · 2024/02/04(日) 00:11:41.30

ARC精進ってインコでも効果あるの？
ABCのアドホック要素すら処理できないインコがARCの過去問埋めても解けるようになるわけないくらいの認識なんだが

**仕様書無しさん** · 2024/02/04(日) 00:11:42.43

今回のG通せるライブラリ予め持ってた人偉すぎ

**仕様書無しさん** · 2024/02/04(日) 00:12:23.25

>>187
とりあえずAくらいならあると思うよ
考察力は鍛えられると思うから

**仕様書無しさん** · 2024/02/04(日) 00:13:25.67

ARC-AならABCとは違うちょっとしたコツがあるだけのことが多いから意味あるよ

**仕様書無しさん** · 2024/02/04(日) 00:14:04.39

ARC-Aはひとくち論理パズルみたいで慣れると気持ちいい

**仕様書無しさん** · 2024/02/04(日) 00:14:04.72

そうなんか
ARCのA埋めするのありかもな

**仕様書無しさん** · 2024/02/04(日) 00:15:28.79

ARC-A、Bとかは中受算数に近くて、有名知識典型やるだけっていうよりはちょっと頭使って場合わけとかステップ踏めば正解に辿り着けるみたいな問題が多い

**仕様書無しさん** · 2024/02/04(日) 00:15:30.55

ABCは知らないと厳しい問題が多いじゃん

**仕様書無しさん** · 2024/02/04(日) 00:17:04.38

単純に解いてて面白いというのもある

**仕様書無しさん** · 2024/02/04(日) 00:17:06.94

単純に解いてて面白いというのもある

**仕様書無しさん** · 2024/02/04(日) 00:17:25.11

ABC-Dとかは完全初見では知らなくて無理(有名アルゴリズムの再開発が必要なため)なことが多いけど、ARC-B以下は完全初見でも競技or受験算数数学の素養がある人は解けるような問題が結構ある

**仕様書無しさん** · 2024/02/04(日) 00:18:28.78

WM使い慣れてないな

**仕様書無しさん** · 2024/02/04(日) 00:20:39.83

まあ明日のARCの配点楽しそうなので許す

**仕様書無しさん** · 2024/02/04(日) 00:26:24.82

水インコなのでA400点が怖い
300と400の間に崖を感じる

**仕様書無しさん** · 2024/02/04(日) 00:26:40.11

まあ、質としてどうなのというのはあるが、WMもmerge sort treeも微妙な理解だったから勉強の機会にはなった
ratedのインコと賞金争いしてる最上位層はかわいそう

**仕様書無しさん** · 2024/02/04(日) 00:29:35.80

黄色くらいでABCの問題作りたがってそうな人割と多そうだしテスター含めて公募でもいいと思うんだよな　こどふぉみたいに

**仕様書無しさん** · 2024/02/04(日) 00:32:09.02

最近中国勢が増えたのか知らんけどパフォ渋い気がする
中国支配的

**仕様書無しさん** · 2024/02/04(日) 00:34:00.97

ABCwriter、えびまさんとフレンズとノックマンと物理好きしか知らない

**仕様書無しさん** · 2024/02/04(日) 00:36:31.06

merge sort tree、いい感じの解説貼ってちょ
見つからない

**仕様書無しさん** · 2024/02/04(日) 00:37:15.54

前回writerやってたynymxiさんは今回普通に出てるし、writer固定というわけでもなさそうなんだよな

**仕様書無しさん** · 2024/02/04(日) 00:38:12.07

固定メンで回してるえでゅふぉも全然教育的じゃないって叩かれがちだし、固定メンで作問テスター回すのに限界がありそう

**仕様書無しさん** · 2024/02/04(日) 00:42:12.08

ちょくがもっと問題作って
ちょくの問題は好き

**仕様書無しさん** · 2024/02/04(日) 00:47:21.11

WMの解説読んでて、rankの説明をする前にrank_1を計算と出てきて激キモ再帰的データ構造なのか？と勘違いしたがサイレントで完備辞書使われたわ

**仕様書無しさん** · 2024/02/04(日) 00:49:45.65

今回のEとかあれで作問料貰えてるのか気になる

**仕様書無しさん** · 2024/02/04(日) 00:50:24.89

何ならボス問のGも大概な気がする

**仕様書無しさん** · 2024/02/04(日) 00:50:47.95

WM、解説読んで理解した
radix sortぽいことをして結果を桁ごとに保管、これをたどって検索しているんか
これってライブラリ化必須？
今まで鉄の意志で遅延セグすら手で書いてたが流石に面倒くせぇよなこれ

**仕様書無しさん** · 2024/02/04(日) 00:52:13.62

遅延セグ木ソラで毎回描いてるのは割と異常
JOI出身の人とかは必須能力らしいけど

**仕様書無しさん** · 2024/02/04(日) 00:52:46.80

何の縛りだよ

**仕様書無しさん** · 2024/02/04(日) 00:53:49.90

ICPCに向けての特殊訓練ならまだしも、通常のコンテストサイトではライブラリ化した方が吉だと思うよ

**仕様書無しさん** · 2024/02/04(日) 00:54:52.80

>>205
蟻本読めチンカス

まぁセグ木に対するフェニック木みたいなもんで機能的にはWMに包含されてるので覚えなくてもいい

**仕様書無しさん** · 2024/02/04(日) 00:56:49.91

ライブラリ整備こそがABCの醍醐味だぞ

**仕様書無しさん** · 2024/02/04(日) 00:57:16.47

>>214
だからSSRSくんみたいにソラで青くらいまでのデータ構造は書けるよ😎
まぁ役には立たない

**仕様書無しさん** · 2024/02/04(日) 00:59:02.39

蟻本のp170かな

**仕様書無しさん** · 2024/02/04(日) 01:03:50.14

X見たけど、Fを乱択と抽象化してるインコ大量発生しすぎだろ

**仕様書無しさん** · 2024/02/04(日) 01:09:20.56

これmerge sort treeの各頂点に累積和も持つ感じ？

**仕様書無しさん** · 2024/02/04(日) 01:13:42.00

インコは本質を理解せずに言葉だけをオウム返ししかしてないのがよくわかる

**仕様書無しさん** · 2024/02/04(日) 01:19:06.89

ライブラリ整備も何も、人が作ったライブラリペタペタするだけでええやん

**仕様書無しさん** · 2024/02/04(日) 01:23:00.65

うしさんのはたまにバグるから注意しろよ

**仕様書無しさん** · 2024/02/04(日) 01:31:51.33

search and paste content

**仕様書無しさん** · 2024/02/04(日) 01:36:43.38

F、乱択の問題で間違いないと思う
mod Pによるハッシュを考えると仮定して、A_iがPの倍数の場合に mod P で 0 になると嫌
でも、1個のA_iあたり60個しか素数を含ませられないから、合計6万個以下の素数しか入らない
しかし、10億以下の素数は約5000万だから、ランダムな素数を選べば100テストケースあっても衝突は高々1回くらいで嬉しい
乱択をすると悪意のあるテストケースをすり抜けられるっていうのは結構ある

**仕様書無しさん** · 2024/02/04(日) 01:44:07.70

そりゃ乱択の問題だけど、乱択というワードじゃ全然問題の重要なパートの情報がないという話
ロリハが想定解の問題を乱択の問題と覚えないでしょ

**仕様書無しさん** · 2024/02/04(日) 01:49:19.94

本当そう
乱択は一つの要素(というかハッシュ衝突を避けるための選択肢)でしかなくて、本質はハッシュ化的なもの

**仕様書無しさん** · 2024/02/04(日) 01:52:59.76

こういう案件を観測するとインコって努力の方向性が間違ってるんじゃないかと感じて悲しくなってくる

**仕様書無しさん** · 2024/02/04(日) 02:06:36.49

まあ別に素数を乱択する部分が本質だと思っているわけではなくて、どちらかと言うとハッシュ化という語彙がないために変な言葉遣いになってるだけだと思う

**仕様書無しさん** · 2024/02/04(日) 02:16:50.86

インコはハッシュ系以外の乱択を知らないし、ハッシュ系以外の乱択問題に遭遇することもほぼないため、実はそこそこうまくいってしまう情報の取り方の可能性はあるな
個人的には積を高速計算できるハッシュ化みたいな抽象化が今回は有用だと思った
剰余算は通常の積、ロリハは結合、zobrist hashはxorと、なんらかの積についておよそ準同型性が成り立っているハッシュと捉えることができ、今回の問題はそれがうまく効いてる
あとはGarnerでやる多倍長整数復元との関連付けで認識したりとかか

**仕様書無しさん** · 2024/02/04(日) 02:18:58.42

2年前くらいのABC-Gに純粋な乱択問題あった気がする
こどふぉでもたまに見かけるし

**仕様書無しさん** · 2024/02/04(日) 02:19:46.22

セックス問題

**仕様書無しさん** · 2024/02/04(日) 02:20:30.54

積を高速計算できるハッシュ化というか、CRTとかを考えたら自然な発想では
偶奇だけに注目したらある程度候補が消えることの延長と言ってもいい

**仕様書無しさん** · 2024/02/04(日) 02:20:57.74

chokudai作問のやつだろ
あれはかなり良問だと思っていた
あれがあるから乱択で括られると違和感が強いが、インコ目線だと8問ABC-Gで数年に一度出るレベルのものは無視してもそんなに差し支えない

**仕様書無しさん** · 2024/02/04(日) 02:23:34.53

乱択想定の問題、乱択想定って知って解くのでは何も意味がないから精進が難しそう

**仕様書無しさん** · 2024/02/04(日) 02:24:45.13

ああいういい感じの黄diff良問が多かったABCに帰りたいぜ
最近のはしょうもなすぎる

**仕様書無しさん** · 2024/02/04(日) 02:26:19.64

というかhash系以外の乱択ってad hocに発生するから統一的に学習するのは難しい

**仕様書無しさん** · 2024/02/04(日) 02:28:07.80

B問題で実装重いとか言ってる人いてビビる
グリッド探索で配列で進行方向を管理する典型を知らない感じなんかな？
読解が面倒くさいって話ならまだ分かるんだが

**仕様書無しさん** · 2024/02/04(日) 02:29:22.08

実際Bにしては重いなと俺は思ったな

**仕様書無しさん** · 2024/02/04(日) 02:30:33.83

(Bにしては)重いってことでしょ普通に
いつもなら1、2分で書けるけど今回は流石にキツい

**仕様書無しさん** · 2024/02/04(日) 02:31:09.79

というかそのレベルだともはや典型って呼ばないから
素直に書いてあることを実装するだけだし

**仕様書無しさん** · 2024/02/04(日) 02:37:30.11

すまん、なぜか勘違いしてたけどchokudai作問ではなかったかも
でも納得感のある乱択で良問だったのは本当

**仕様書無しさん** · 2024/02/04(日) 02:40:59.93

ちなみにABC272Gね

**仕様書無しさん** · 2024/02/04(日) 02:41:22.89

di, dj = dj, -di で時計回り90度
dj, di = -dj, di で反時計回り90度

**仕様書無しさん** · 2024/02/04(日) 02:43:26.80

>>242
dx[4]とかdy[4]を使ってグリッド探索をやるのって初見じゃ中々思いつかなくね

**仕様書無しさん** · 2024/02/04(日) 02:45:25.38

>>245
2行目は di, dj = -dj, di の間違い

**仕様書無しさん** · 2024/02/04(日) 02:47:12.12

>>246
うーんまあその4/8方向の差分-1-1列挙する書き方を典型と言われたらそうかもしれないけど最初から出来てたような気もするしよくわからん

**仕様書無しさん** · 2024/02/04(日) 02:47:26.35

>>245
頭いいな
この実装もありか

**仕様書無しさん** · 2024/02/04(日) 02:48:22.13

頭良いっていうか、回転行列を考えれば自明では？

**仕様書無しさん** · 2024/02/04(日) 02:51:04.59

回転行列か
線形代数でやった気がするけど出てこなかったな

**仕様書無しさん** · 2024/02/04(日) 02:51:51.40

逆に初心者はどう書くもんなんだ？移動分の-1~1をfor分で回して移動距離1のものだけ使うとかか？

**仕様書無しさん** · 2024/02/04(日) 02:53:57.81

今どの方向を向いているのかを変数か何かで持っておけばいいんじゃね

**仕様書無しさん** · 2024/02/04(日) 02:54:15.78

初心者の頃はif文４つ書いてた

**仕様書無しさん** · 2024/02/04(日) 02:55:01.41

>>254
これ２

**仕様書無しさん** · 2024/02/04(日) 02:55:04.74

本当に未定義動作すぎてよくわからないみたいなところはある

**仕様書無しさん** · 2024/02/04(日) 02:57:08.86

>>254
これ3

**仕様書無しさん** · 2024/02/04(日) 02:59:42.50

スレ民のベビインコ時代かわいいね

**仕様書無しさん** · 2024/02/04(日) 03:02:18.73

🤓青上位！黄色！ABC6完やるだけ！

(3年前...)

👨へーatcoder？おもしろそう！

**仕様書無しさん** · 2024/02/04(日) 03:07:02.52

BFSすら本見ながら書いてた時代が私にもありましたわね

**仕様書無しさん** · 2024/02/04(日) 03:10:32.89

まあ🍼🦜時代なら仕方ない
インコスレ民もこのまま精進を重ねて人間になろう

**仕様書無しさん** · 2024/02/04(日) 03:17:43.62

ジェネルシベビー

**仕様書無しさん** · 2024/02/04(日) 03:44:53.19

ガイジスレ

**仕様書無しさん** · 2024/02/04(日) 06:34:08.65

ABCはWriterメタが効くからWriter発表されたらこいつこんな問題よく出すよなとか軽く思い出しておくようにしてる

**仕様書無しさん** · 2024/02/04(日) 06:43:24.14

ちょっと前にいたアイコンが左右で表情違うキモい仮面みたいなイキリガイジって誰だっけ？

**仕様書無しさん** · 2024/02/04(日) 07:09:22.90

ガイジスレ終了

**仕様書無しさん** · 2024/02/04(日) 07:23:17.37

ABCにwriterメタもクソもないだろ全部ちょっと典型やるだけ既出を捻った問題で大して個人色ないんだし
ARC/AGCなら意味あるけど

**仕様書無しさん** · 2024/02/04(日) 07:24:34.29

ABCみたいな典型寄りしか出せないコンテストですらwriterメタが効く扱いなら逆に効かないコンテストはどれなんだよって感じ

**仕様書無しさん** · 2024/02/04(日) 07:36:40.84

実際ABCでこの問題あの人っぽいな～って思いながら解いてたら実際そうだったみたいなのはよくあるのでインコ共には有効な戦術じゃないか

**仕様書無しさん** · 2024/02/04(日) 07:38:37.71

writer少ない現状atcoderで問題傾向の偏りあるってことだな
やっぱコドフォやっといて正解

**仕様書無しさん** · 2024/02/04(日) 08:03:52.95

最近のABCよりはこどふぉの方が断然質良いな　
昔はABC良かったのに

**仕様書無しさん** · 2024/02/04(日) 08:35:15.53

ブルアカを持ち上げてみたところで原神に勝利できるわけではないからな
現実を見ないと敗北が待っている

**仕様書無しさん** · 2024/02/04(日) 09:02:26.36

もう格付けは終わってるのでブルアカ>>>>原神です

**仕様書無しさん** · 2024/02/04(日) 09:14:52.25

ブルアカ>>>>原神>>>>競プロ

**仕様書無しさん** · 2024/02/04(日) 09:37:34.85

水色タッチで停滞するような低知能にとってはそうかもね