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

**仕様書無しさん** · 2024/03/21(木) 11:25:11.55

競技プログラミング、オンラインジャッジ、プログラミングコンテストや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/

前スレ
競技プログラミングにハマるプログラマのスレ 160
https://medaka.5ch.net/test/read.cgi/prog/1708962732/
競技プログラミングにハマるプログラマのスレ 161
https://medaka.5ch.net/test/read.cgi/prog/1709363800/
競技プログラミングにハマるプログラマのスレ 162
https://medaka.5ch.net/test/read.cgi/prog/1709602428/
競技プログラミングにハマるプログラマのスレ 163
https://medaka.5ch.net/test/read.cgi/prog/1709897526/
競技プログラミングにハマるプログラマのスレ 164
https://medaka.5ch.net/test/read.cgi/prog/1710220809/
競技プログラミングにハマるプログラマのスレ 165
https://medaka.5ch.net/test/read.cgi/prog/1710398066/
競技プログラミングにハマるプログラマのスレ 166
https://medaka.5ch.net/test/read.cgi/prog/1710650865/

**仕様書無しさん** · 2024/03/25(月) 23:01:09.87

うむにくは考察力を鍛えろといっている

**仕様書無しさん** · 2024/03/25(月) 23:03:04.85

ARCは常に事故死と隣合わせなのではい
bの33557ARCだけが例外

**仕様書無しさん** · 2024/03/25(月) 23:03:47.67

touristでもARCの全完なんてめったにできてないけど

**仕様書無しさん** · 2024/03/25(月) 23:04:03.21

>>877
AB今更解けても大して美味しくないから前半でちょっと詰まったorしくじった片方捨ててCD解きに行くみたいなのは暖色だとかなりやるぞ

**仕様書無しさん** · 2024/03/25(月) 23:06:05.08

昨日のセットは黄色だとAB2完安定止まりだし事故ったら1完やむなし
1完回避できるのは3完安定なのに事故で2完になったとかだから橙以上

**仕様書無しさん** · 2024/03/25(月) 23:06:40.75

どうせ最終的にはCD解けてないと温まらないのと、時間に余裕がある時に難しい問題を解いた方が落ち着いて取り組めるので

**仕様書無しさん** · 2024/03/25(月) 23:07:55.51

ARCがあるのだ！だけど、みんな参加しなくていいなのだ！

**仕様書無しさん** · 2024/03/25(月) 23:08:34.93

>>880
今見たらtouristARC全完結構してるやん

**仕様書無しさん** · 2024/03/25(月) 23:09:54.93

touristなら全完して当然だろ

**仕様書無しさん** · 2024/03/25(月) 23:10:56.52

掌クルックル

**仕様書無しさん** · 2024/03/25(月) 23:12:18.48

tourのiを借るガイジスレ民

**仕様書無しさん** · 2024/03/25(月) 23:13:57.18

スレ長かっけえな
どっかのfakeとは大違いだ

ごりちゃんはもう成長とかのフェーズはとっくに終わっててとっくに収束してるんだけど、でもまだ時間かかっても強くなりたいし時間かかってもHighest更新ドリームを追い続けたい

**仕様書無しさん** · 2024/03/25(月) 23:14:29.26

おれもARC全完したい

**仕様書無しさん** · 2024/03/25(月) 23:15:54.60

おれもくんのパンツはかっこいいと思う

**仕様書無しさん** · 2024/03/25(月) 23:20:38.98

見に行ったがねえじゃねえかよ嘘つき野郎

**仕様書無しさん** · 2024/03/25(月) 23:22:25.21

ホモとインコは嘘つき

**仕様書無しさん** · 2024/03/25(月) 23:28:27.43

>>878
考察力は精進してもほとんど上がらないよ
10年とか時間かければ少しは上がるかもってレベル

**仕様書無しさん** · 2024/03/25(月) 23:42:05.89

だから中受支配的と言ってるだろ
既に選別は終了してる

**仕様書無しさん** · 2024/03/25(月) 23:49:40.93

高受支配的でもある

**仕様書無しさん** · 2024/03/25(月) 23:55:01.42

高受したことないから話すことなし

**仕様書無しさん** · 2024/03/25(月) 23:58:06.56

>>850
2つの解法思いついた X が与えられるとする
1. 素数の余りによるハッシュを考える
でかい素数をランダムに数個とるり 1～20万の階乗とXに対して、それらの素数で割った余りを求める。当てはまるNがあるのでそれを答えればよい
2. 階乗の対数が結構バラバラなのに注目する
1～20万の階乗とXの対数をとる。Xの対数に1番近いものを答えればよい

実は2.の方が実装楽か？

**仕様書無しさん** · 2024/03/25(月) 23:59:22.39

高受偏差値70でポテ青上位ってとこかな

**仕様書無しさん** · 2024/03/26(火) 00:00:56.69

TKNDKS

**仕様書無しさん** · 2024/03/26(火) 00:05:54.68

>>899
ぜってぇそんなねえわ
せいぜい緑

**仕様書無しさん** · 2024/03/26(火) 00:08:49.27

ageカスさあ

**仕様書無しさん** · 2024/03/26(火) 00:18:36.62

緑って偏差値70もあるのか
青は偏差値80ぐらいか？

**仕様書無しさん** · 2024/03/26(火) 00:27:21.11

>>898
想定は前者
998と1097でハッシュ化すれば絶対に衝突しない
もう少し頭使うと末尾の0の個数でN!内の5の指数がわかるので5択問題と化す
こっから上手い性質探せたら良かったのだがたった5択なら愚直判定が通るのでインコ問送り決定

**仕様書無しさん** · 2024/03/26(火) 00:33:36.61

インコ部屋に収容せよ

**仕様書無しさん** · 2024/03/26(火) 00:39:34.72

昨日のBの隣接swap版どうやるんだろう

**仕様書無しさん** · 2024/03/26(火) 00:41:14.53

入力がN!でなくてP!(Pは素数)だったならハッシュ化せずとも末尾0個数+桁dp除算判定が可能なのでケチはつかんがインコ問のそしりは免れないため

**仕様書無しさん** · 2024/03/26(火) 00:43:22.66

>>903
緑で偏差値55で青で偏差値65とかそんなもんだろ
高受偏差値70はポテ青上位

**仕様書無しさん** · 2024/03/26(火) 00:54:37.47

>>850
Nが小さいからPython使えば愚直にO(N)判定でできないのかと思ったけど、多倍長整数がどれくらいおそくなるのかわかんないや

**仕様書無しさん** · 2024/03/26(火) 01:14:40.38

Bの隣接swap版はreplace回数の三分探索で解きたいがたぶん嘘
簡単のため文字列Sの(個数=)個数とする
隣接swapだけでカッコ列の対応を取るシミュレートを貪欲法で行い、実行後の対応の取れたカッコ列をTとする
SとTのカッコの差分を見比べると、交換するべき()の位置が浮かび上がってくる
()同士の距離が小さいほうから隣接swapだけで交換するかreplace2回でやるか貪欲に決定する
でどうだ

**仕様書無しさん** · 2024/03/26(火) 01:15:51.13

>>909
多倍長整数の掛け算はかなり時間かかる
O(1) ではないと思うが正確な計算量はわからん
自分の環境（Pypy3）だと200000!を計算するだけで7秒かかった

**仕様書無しさん** · 2024/03/26(火) 01:17:09.07

>>911
math.factorial(200000)を使え

**仕様書無しさん** · 2024/03/26(火) 01:21:03.03

>>912
0.16 sec だったけど、Nの特定はできなくない？全探索の代わりに二分探索しても重いぞ

**仕様書無しさん** · 2024/03/26(火) 01:22:28.92

よく考えたら素数p≦200000 で割り切れるかどうかで二分探索→Nの範囲を絞り、そこからは適当に多倍長整数でやる
でも出来るな（20万以下では素数の間隔は100以下なので間に合う）

**914** · 2024/03/26(火) 01:28:12.56

まあこれやるなら末尾の0の個数に注目するのとあまり変わらないか

**仕様書無しさん** · 2024/03/26(火) 01:31:36.29

>>913
まあそれはそうで、math頼みの階乗計算は200msかかるので愚直計算はできても10回まで
N!の末尾の0の個数が5の指数と一致することを使えば愚直5回で判定できてこれなら余裕
素数法だと素数砂漠の探索前に多倍長/多倍長をすればよく、これはn<200000なら400msで可能なので通せる

**仕様書無しさん** · 2024/03/26(火) 03:40:32.71

久しぶりに会話したらコミュ力ゴミカスになってて草
もう終わりだよ

**仕様書無しさん** · 2024/03/26(火) 04:21:37.56

ひととかかわれません

**仕様書無しさん** · 2024/03/26(火) 04:32:48.35

健常者志望

**仕様書無しさん** · 2024/03/26(火) 04:33:47.45

今は？

**仕様書無しさん** · 2024/03/26(火) 04:41:05.08

ジェネルシ
より正確にはモンスター　宇宙人

**仕様書無しさん** · 2024/03/26(火) 05:16:59.89

病気治してえー

**仕様書無しさん** · 2024/03/26(火) 05:25:29.73

ASDって診断されるメリットある？

**仕様書無しさん** · 2024/03/26(火) 06:23:21.15

しゃちょがLeetCodeに拗らせてるのは昔なんかあったのかにゃ？

**仕様書無しさん** · 2024/03/26(火) 06:37:43.21

ガイジスレ終了

**仕様書無しさん** · 2024/03/26(火) 08:11:01.89

コミュ力灰なせいで全てが終わった　かなしいね

**仕様書無しさん** · 2024/03/26(火) 08:21:50.66

どうしたの？
最悪のキメラが話を聞いてあげるよ

**仕様書無しさん** · 2024/03/26(火) 08:26:00.53

馴れ合いインコならぬ馴れ合い最悪キメラというわけか

**仕様書無しさん** · 2024/03/26(火) 08:29:02.95

復讐スレ開始

**仕様書無しさん** · 2024/03/26(火) 09:08:01.63

非婚しか日本のIT技術者になれない原因↓

支配者層による技術攻撃

ビルゲイツが日航機墜落させてTRON技術者を殺害
小泉や竹中が多重派遣業界にしてIT技術者を攻撃
文科省がゆとり教育制度にしてIT技術者は衰退
残業で金稼ぎや共働きが無理でIT技術者は滅亡

**仕様書無しさん** · 2024/03/26(火) 09:18:30.12

時代は馴れ合いだからね
俺も逆張り冷笑せずに馴れ合いをしていこうと思ってる

**仕様書無しさん** · 2024/03/26(火) 09:23:28.81

最悪のキメラでも良ければ友達になってあげるよ

**仕様書無しさん** · 2024/03/26(火) 09:33:47.69

馴れ合いスレ開始
Xの馴れ合いインコに負けない馴れ合いをしていこう

**仕様書無しさん** · 2024/03/26(火) 09:43:29.03

スレの姫になろうかな

**仕様書無しさん** · 2024/03/26(火) 11:14:45.01

料理成分はこたつがめさんで間に合ってます

**仕様書無しさん** · 2024/03/26(火) 11:43:26.69

ガイジガイジガイジ
インコインコインコ
キメラキメラキメラ
イジガイジガイジガ
コインコインコイン
メラキメラキメラキ

**仕様書無しさん** · 2024/03/26(火) 12:19:46.06

なぜホモスレなのに需要のない姫になろうとするのか

**仕様書無しさん** · 2024/03/26(火) 12:32:59.70

ファッションホモが雌男子を好くから

**仕様書無しさん** · 2024/03/26(火) 13:07:36.16

ここホモスレなの？

**仕様書無しさん** · 2024/03/26(火) 13:28:00.81

男色支配的です

**仕様書無しさん** · 2024/03/26(火) 14:29:41.94

kedさんヒュ青あるのかよ
レート下がらないとこんなもんか

**仕様書無しさん** · 2024/03/26(火) 14:29:44.85

kedさんヒュ青あるのかよ
レート下がらないとこんなもんか

**仕様書無しさん** · 2024/03/26(火) 14:33:04.54

2回も言わなくてよいです

**仕様書無しさん** · 2024/03/26(火) 14:35:24.40

2回も言わなくてよいです

**仕様書無しさん** · 2024/03/26(火) 14:37:01.92

ホモはしつこい

**仕様書無しさん** · 2024/03/26(火) 14:55:14.42

レス検知からなりすましまで2分もかかる雑魚に多重投稿なりすましされてキレそう

**仕様書無しさん** · 2024/03/26(火) 14:56:10.46

ハッタショとインコはエコラリアする

**仕様書無しさん** · 2024/03/26(火) 16:11:04.52

うんちでない

**仕様書無しさん** · 2024/03/26(火) 17:44:23.90

ヒュの青とアルゴの青の価値は同じ

**仕様書無しさん** · 2024/03/26(火) 18:51:24.90

予想したとおり大谷が言ったのは自民党の裏金議員と同じで
「通訳（秘書）が勝手にやった」
「僕は何も知らない」
そして質疑応答も拒否した
その対応に米国民どころか大谷贔屓の日本人さえAC射精完了できなかった
大谷はおれの恋人だというのに

**仕様書無しさん** · 2024/03/26(火) 19:07:44.57

庇ったり見捨てたりする明確なポジションを取らないくせに想いの深さだけひとりごつキモさ
これがガイジスレ文学

**仕様書無しさん** · 2024/03/26(火) 19:09:48.89

度量の小さいアナリスト気取りがホモごっこすんな

**仕様書無しさん** · 2024/03/26(火) 19:19:23.21

大谷特にファンでもアンチでもないけど日本帰ってこられると困るなあ
スパッと引退してくれ

**仕様書無しさん** · 2024/03/26(火) 19:43:36.38

ARC連敗で競プロイップスになって精進出来ない

**仕様書無しさん** · 2024/03/26(火) 19:45:44.12

俺はアナルストだけどね

**仕様書無しさん** · 2024/03/26(火) 19:59:02.01

擬態インコの末路だね

**仕様書無しさん** · 2024/03/26(火) 20:03:17.30

最近こういうインコのかわいい動画流行ってるよな
https://youtube.com/shorts/OcfXAcAw3u0

**仕様書無しさん** · 2024/03/26(火) 20:14:25.84

ガイジとガイジの争いはとどまるところを知らない…

**仕様書無しさん** · 2024/03/26(火) 20:20:12.70

やたら射精するガイジスレ文学と、やたらセックスする村上春樹文学は双対関係があるのではないか

**仕様書無しさん** · 2024/03/26(火) 20:25:53.53

双対の意味を知らなさそうなインコさあ

**仕様書無しさん** · 2024/03/26(火) 20:30:14.91

双対言いたいだけで草

**仕様書無しさん** · 2024/03/26(火) 20:31:09.09

俺もチンポとかセックスとか射精とか言いたいだけでごめん

**仕様書無しさん** · 2024/03/26(火) 20:31:54.58

射精と言いたいだけだろガイジスレ文学の説明だけ浮いてるし

**仕様書無しさん** · 2024/03/26(火) 20:32:28.02

相変わらず書き込みからレートと学歴が透けることよ

**仕様書無しさん** · 2024/03/26(火) 20:38:22.06

相書レ透

**仕様書無しさん** · 2024/03/26(火) 20:41:06.56

中受頻出四字熟語だから小学生スレ民は覚えておきましょう

**仕様書無しさん** · 2024/03/26(火) 20:44:27.45

全文暗記必須だが
ハッシュ化すんな

**仕様書無しさん** · 2024/03/26(火) 20:47:06.72

スレレスバ早解きのためにライブラリかテンプレ化(辞書登録)しとけ

**仕様書無しさん** · 2024/03/26(火) 20:56:21.26

テンプレ化して、毎回書き込みの先頭のほうに入れておいてもいいですかね

**仕様書無しさん** · 2024/03/26(火) 20:57:19.78

>>1とか>>2とかでdefineしとけ

**仕様書無しさん** · 2024/03/26(火) 20:57:53.85

#define ちんぽ long long

**仕様書無しさん** · 2024/03/26(火) 20:59:41.92

#define イコンインコ

**仕様書無しさん** · 2024/03/26(火) 21:14:23.81

IOIの代表は相変わらずndtkばかり
EGOIの代表は洛南除いて名門中学ってわけでもないな
https://www.atpress.ne.jp/news/388136

**仕様書無しさん** · 2024/03/26(火) 21:25:06.89

一昔前はks多かったのに

**仕様書無しさん** · 2024/03/26(火) 21:29:29.07

レートも一緒に紹介しろよ

**仕様書無しさん** · 2024/03/26(火) 21:40:27.30

ラグビースクールってなに
ラグビーやるの？

**仕様書無しさん** · 2024/03/26(火) 21:54:34.95

TKND＞＞＞KSというわけか