競技プログラミング総合スレ 64

2022/10/02(日) 17:43:58.66

↑2行になるようにする

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

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

※前スレ
競技プログラミング総合スレ 63
https://mevius.5ch.net/test/read.cgi/tech/1627477128
VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured

VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured

2022/10/29(土) 22:52:01.22

>>263
それ前回のパフォじゃん
さすがに今回はレートあがるだろ

2022/10/29(土) 22:52:46.63

>>263
これに表示されてるは前回の結果だよ　コンテスト名を見ればわかる
今回も含めてコンテストの結果は数時間後に出る事が多いから終わってすぐには反映されないよ

2022/10/29(土) 22:54:16.01

>>267-268
ほんまやあああああああああ
サンクス
しかしC問題で一回間違えた(直交方向に足した値が範囲内でおさまってるかの処理を書き忘れた）ので少しそれが心配。。

2022/10/29(土) 22:54:24.14

あとそのレートで4完してるなら今回でレートは100くらい上がるんじゃない？

2022/10/29(土) 22:55:21.84

ac-predictor入れなよ

2022/10/29(土) 22:57:09.33

レートの更新が来てるわね

2022/10/29(土) 22:57:27.79

https://imgur.com/a/5ACK8kd
ほんまやああああああ
緑色がみえてきたあああああああ

E問題まで確実にとけるように頑張りたい

2022/10/29(土) 22:58:19.47

Fって精進すればDP使おうってすぐ見抜けるようになるものなん？

2022/10/29(土) 22:59:37.34

うん

2022/10/29(土) 23:04:29.61

dpのiとjのループの順番を逆にしたら通った…

2022/10/29(土) 23:07:12.53

Fはいつもより典型度高めかな
ナップサックDPをするついでに、選ぶときの遷移と選ばないときの遷移でちょっと処理を変えるみたいなのは結構見る

2022/10/29(土) 23:08:20.93

from functools import lru_cache
pythonってメモ化再帰再帰が標準実装されてるんだ
知らなかった・・
どうやって制御してるんだって感じだが、やっぱり標準モジュール？ってすごいな

2022/10/29(土) 23:13:13.23

実際どうやってんのか知らないけど、メモ化再帰の実装はpythonのデコレータと相性いいと思う

2022/10/29(土) 23:18:18.42

計算時間の見積もりだけど、ラフに計算して10^8以下で平均的な定数倍の重さだったら2 secで間に合うし、普通に想定解になりうると思うよ

2022/10/29(土) 23:19:43.68

簡単にいうと、デコレータで内部的にdictを作って、引数と戻り値つっこんでるだけでしょ
dictより自分でlistを使ってメモ化したほうが高速だし、別にlru_cacheは覚えなくてもいい気がするな

2022/10/29(土) 23:25:38.82

標準実装部分って一度Cでコンパイルされてるから自前実装より速いと思っていたんだけどどうなんだろう。
あとdictってハッシュだから速いと思ってたんだけどlistの方が早いっていうことってあるの？
インデックスへのアクセスがn(1)だとしても再帰関数の場合はインデックスもばらばらだと思ったんだけど

2022/10/29(土) 23:30:42.87

mod逆元なんて意味不明な計算させんでも、誤差を認めた小数でええやん

2022/10/29(土) 23:30:58.93

Pythonの標準実装は、Cで高速化されて優秀なときと生Pythonで微妙な実装が施されていてひどいときの両方がある印象だね
PyPyに至っては最適化の仕方がよくわからないから実際に試すしかない

2022/10/29(土) 23:36:12.18

>>282
ハッシュ化のオーバーヘッドがあるから、とりうる引数の値が小さいんならlistの方が定数倍速いこともありうる
今回はそもそもlistでは対応できないはず

2022/10/29(土) 23:36:54.42

Pythonを使ってた時は自前で書いた二分探索だと通らなくてそこを二分探索のライブラリに置き換えたら余裕を持って通ったことがあったからCによる高速化の恩恵は大きそう

2022/10/29(土) 23:42:41.35

>>283
ターンが進むごとに指数的に減衰していきそうな行動パターンまでちゃんと追跡できてるかを問いたいとすると、mod逆元の方がいいと思う
まあ、小数解答方式でそういうタイプの枝刈りで通せる人はそもそも今回の問題だと問題なく想定解にたどり着ける気がするけど

2022/10/29(土) 23:45:49.46

Ex、ぱっと見Cartesian木で貪欲でいけるんじゃないかと思ってしまうが、そんな単純な問題じゃないっぽい

2022/10/29(土) 23:48:54.20

んー、F難しくはなかった
毎回変なところで失敗するからたどり着けないけど

2022/10/30(日) 00:52:02.32

Eまでは安定するようになってきたけどFが中々安定しない
今回のFは素直なDPで良いって聞いたらすぐだったのに

2022/10/30(日) 01:22:58.95

Cで正方形の定義書いてほしいと思うのは甘え？

2022/10/30(日) 01:28:08.60

GもExも見方によってはLPだし後ろの方はLP回だったのかも

2022/10/30(日) 01:28:10.10

長さが同じっていうだけで判定すると菱形も拾ってしまうよね

直行条件って内積知らないと厳しいと思うけど、やっぱり数学の知識が必要なんだと思った

2022/10/30(日) 01:31:32.00

>>290
部分和をちょうどxにするときに何かを最適化する問題って地味に取れる手立てが少なくて（今回のGみたいに例外的に連続緩和できるとかならともかく）、ABCだったらナップサックDPを出発点に考えても大体外れないと思う

2022/10/30(日) 01:35:18.53

数学から離れて長かったり数学にあんま縁がない人だと、辺の長さが全部等しい四角形が正方形であることの必要十分条件だと勘違いするのはめちゃくちゃありそう

2022/10/30(日) 14:22:57.27

ARCなくね？
AGCない代わりに最近たくさんあるなと思ってたけど、こっちも放出されつくした？

2022/10/30(日) 14:31:31.53

問題の枯渇で純粋なアドホック考察ゲー作るのが難しくなってきて破綻しつつあるから、アルゴの方はABCの延長線上みたいなゆるふわコンテンツがメインになり、AHCに賭けてるんじゃないかとか邪推してしまうな

2022/10/30(日) 14:56:59.25

短期AHC久しぶりだ

2022/10/30(日) 16:38:01.85

2週間前から始めていますが、AtCoderのBeginnerさえ1問しか解けません
復習はしていますが、全然スキルが上がった感じがしません(´；ω；｀)

2022/10/30(日) 16:41:43.31

とりあえず鉄則本やっておけばいいんじゃないかな

2022/10/30(日) 16:47:38.26

Bが解けないとすると、使用言語の文法みたいな基礎事項から勉強しながらやった方がいいかも
C++使いならAPG4bとか
Python使い用のも探せばあると思う

2022/10/30(日) 16:48:51.47

ARCは今年たくさんやったからいいとして、AGCは本当に生えてこなくなったね

2022/10/30(日) 17:05:56.90

AGC少なすぎて赤以上のレートはあまり参考にならんのよね…

2022/10/30(日) 19:01:29.07

頑張って高速化しただけで終わった

2022/10/30(日) 19:05:21.35

出力しないと次の入力を受け取れないシステムになってることを途中から忘れてたの本当にしょうもないミスだ

2022/10/30(日) 19:23:01.86

AHCはみんながガチすぎないことによって、昔のアルゴにあったっぽい良さが保持されている気がする

2022/10/30(日) 20:26:24.18

本当にちょっとした改善（ただし自分では思いつけない）でスコア爆上がりすることをコンテスト後に知るとめちゃくちゃ悔しい

2022/10/31(月) 00:06:58.82

まずは“本当にちょっとした”とかいう歪んだ認知を直すところからやね

2022/10/31(月) 02:21:24.13

短期コンだと本当にちょっとした改善でスコア爆上がりすることが多すぎて辛い
なんで本番中は入力を虚空に放り投げてることに気付けなかったんだと後悔してる

2022/10/31(月) 12:30:07.84

>>300
ありがとうございます、鉄則本頑張ります

2022/10/31(月) 12:31:58.77

問題に付いてるサンプルケースでは正解なのに、ソースコード提出すると他のテストケースで不正解となるんです

おそらくどこかでオーバーフローしていることが原因です

過去のコンテストのテストケースって全部どこかにアップロードされているんでしょうか？

2022/10/31(月) 13:05:29.42

https://atcoder.jp/posts/20
ないものも多いですしテストケースを見ることは推奨されていません
自力でテストケースを作って頑張る方法を身につけるのがいい
参考：https://betrue12.hateblo.jp/entry/2019/09/07/171628

2022/10/31(月) 13:10:33.60

オーバーフローならC++(gcc)だったら-fsanitize=undefinedで見つかるかも

2022/10/31(月) 13:25:03.50

オーバーフローしていることが原因とまで当たりついてるなら、一ヶ所ずつ型変えて提出してみたら

2022/10/31(月) 13:29:23.39

オーバーフローが原因だと分かってるんならもうACはすぐそこじゃないか
頑張れ

2022/10/31(月) 14:29:51.95

>>312
>>313
貴重な情報ありがとうございます

>>314
>>315
unsigned longでもオーバーフローしてしまいます

2022/10/31(月) 14:46:00.66

実はオーバーフローしてないんじゃない？

2022/10/31(月) 15:57:04.81

まさか余りをとる時に負になるケースを考慮していないとか？
ABC-DEFとか

2022/10/31(月) 16:02:58.05

(-m) % n がマイナスの余りになるという仕様になっているのはなぜですか？
((-m) % n) + n とするのが面倒です。

2022/10/31(月) 16:03:27.21

>>299,310,311 が同一人物だとしたら、そのレベルならあらゆるミスをしそうだし、原因はなんともかんとも
愚直で応えるコードを書いてもバグらせそうだし、他の人がACしたコードと比べてみるのがいいんじゃないか・・・

2022/10/31(月) 16:27:35.89

WAの原因なんてオーバーフロー以外にも無数にあるぞ
バグ、mod取り忘れ、コーナーケース、そもそも解法が間違ってる、等

2022/10/31(月) 16:34:07.66

>>319
C++の整数型は(m/n)*n + m%n == mが成り立つことになっていて、除算は0方向に丸めることが規定されているからです（C++11以降）
modintがおすすめ

2022/10/31(月) 17:50:46.88

標準的な型の演算規則ぐらいは身に染み付いてた方が良いと思うので、modintなしで地雷踏み尽くして覚えていくのもありではある

2022/10/31(月) 18:15:49.14

競プロって意味ないって言われてるけどどうなんだろうね？俺は楽しいからやってるけど

確かにこのアルゴリズムを直接的に実務で使うことはあまりないかもしれないけど、バグの発見とかは競プロで鍛えると速くなる気はしてる

2022/10/31(月) 18:22:42.24

まあ高校の数学と同程度には役に立つよ

ようするにめったに使わないし、そんな知識を活用せずに大成功してるひとのほうが多いくらい

2022/10/31(月) 19:21:20.60

脳トレが出来るオンラインゲームみたいなもんだし実生活に役立ったら美味しいくらいの気持ちで良さそう

2022/10/31(月) 19:28:31.38

ABCのD問題までスムーズに解けたらあとは趣味程度に思った方がいいと思うよ
逆にD問題までスムーズに通せるようになることで、ある言語で手早くスクラッチする力や計算量を意識する力はかなり身につくと思う

2022/10/31(月) 19:36:01.13

あと、アルゴリズムに興味を持つきっかけになるかな
スタックがLIFOでキューがFIFOだとか基礎教養でやったとき、正直つまらない暗記対象としか思ってなかったけど、ちゃんと意味があって重要だということが分かった
SQLでB木使うとかも競プロやらなかったら意識しなかっただろうし
ハマる人とっては情報科学の入口として優秀じゃないかな、競プロと相性悪い人はストレートに勉強した方がいいんだろうけど

2022/10/31(月) 19:48:50.64

>>328
おれは先に業務してから競プロやってるけど、RDBでB木使うとかは最初からめっちゃ意識してたぞ
インデックス効かないクエリを実行すると遅すぎてすぐ障害になるからな
そんでRDBだけでは実装が難しすぎる機能とかあったりするから、他のデータ構造も学ぶようになった

競プロはほとんどのひとはすぐ挫折して継続できないみたいだし、どっちのほうが良いかと言うと難しい

2022/10/31(月) 20:01:16.37

>>329
そこは人や環境によるところかな
自分はデータ分析職やってるけど、エンジニア職ではないせいか、ちゃんと理解してる人、意識してる人が少ない
役に立つのに、低レイヤーに触れる文化がないから、自発的にアルゴ勉強する発想が出にくい
あと競プロに相性いいのは、情報系に向いてる人というよりも、元々中受算数か高校数学、高校物理みたいなのがめちゃくちゃ好きとか数オリ経験者みたいなタイプだろうね

2022/10/31(月) 20:18:35.23

割と役に立つこと多いけど数論だけは未だに活用できた試しがない

2022/10/31(月) 20:32:10.84

純粋な離散数学や暗号理論も守備範囲にいれたいとすると、数論みたいな普通のエンジニアリングやデータ解析の範疇じゃ役立てるのが難しい内容も扱いうる
今の競プロの源流のICPCや情オリも、そもそもアカデミックな動機付けでやってるものだし

2022/10/31(月) 20:42:28.12

競プロ初心者でコーダーの俺
こっちの業務の役には立たないと思ってる
情報処理の資格を無駄に取得して給料アップ程度

競プロ面では、素直に実装してTLE連発
こんなガチガチに実装したら仕様変更に耐えられないだろうな
と思いながらAC取りにいく

2022/10/31(月) 20:47:49.35

話題乗り遅れたけど、rustなら x.rem_euclid(m) で余りが常に正になる
みんなrust使おう

2022/10/31(月) 21:29:59.58

ライブラリってデータ構造やアルゴリズムばかり気にしがちだけども細々としたutil系もあると便利よね

2022/10/31(月) 22:05:33.73

>>326
俺も同じような感じだわ。

脳トレで思ったんだけど、脳の老化防止に競技プログラミング!!
とか言って高齢者にプログラム教えたら面白いかもな。
大半はダメポだろうけど、何百人に一人は才能開花しそう。

2022/10/31(月) 22:09:17.19

util系って例えばどういうの？

2022/10/31(月) 23:44:45.25

新しいFizzBazz発見した
面白いように誰もコード書けない

回答見せるとみんな悔しそうな顔をするｗ

2022/11/01(火) 00:19:04.44

はいはい、すごいねー

2022/11/01(火) 02:22:23.21

面接落ちまくりなので、緑で役に立つ宣伝文句教えてほしいわ（´・ω…:.;::..

2022/11/01(火) 07:51:58.39

青でWeb系の就活したけど、競プロだけのアピールはあまり刺さらなかった印象
「自分のレートは上位3%です！」って言っても、はいはいすごいねーって感じだった

Webアプリを作って、見せるようにしたら多少ウケるようになった
いきなりゴリゴリのWebアプリを作るのは難しいから、例えば、競プロでよくあるグラフの入力をペーストすると、
巡回セールスマン問題を解いて、経路を描画してくれるみたいな、そういうアプリを作って、面接で見せれば、
「愚直にやるとO(N!)なんですけど、動的計画法を使うとO(2^N*N)で解けて嬉しいんですよ〜」
みたいなアルゴリズムの能力も見せれて、良いと思うよ

2022/11/01(火) 09:07:49.45

未経験からウェブ系へ転職するなら、Ruby on Rails 一択

YouTube で有名な雑食系エンジニア・KENTA や、RUNTEQ の動画を見ればよい。
KENTAのRailsサロンとか、くろかわこうへいのAWS サロンも良い

理系や競技プログラミングの知識などは、いらない。
文系で、英語・算数だけで十分

Linux, Docker, AWS、データベースなどは必須。
AWS Solution Architect も欲しい

2022/11/01(火) 09:30:51.55

青くらいで競プロアピールしてくるのは地雷臭しかねえ

2022/11/01(火) 11:21:20.61

別に水色ぐらいあれば、世間が競プロerに期待する人材の要件をほぼ満たす
jobsって転がってる求人もそのレベルだし
青以上になると考察力や競プロ過学習の高低の世界なわけで、そこの色の差で評価を変える理由がほとんどの企業では見当たらない
よほどの高知能者をポテンシャル採用したいときぐらいか
青でアピールするのは地雷とか純粋培養こじらせ過ぎだな

2022/11/01(火) 11:29:28.35

世間の大半は競プロerに「FizzBuzzやそれに毛が生えたようなコーディングぐらいならすぐできて、自発的にアルゴリズムの勉強ゲームをやる勤勉な人たち」程度の期待感しか持ってないし、暖色↑で始めてアピールできるようなものだと思ってるようだと、温度差で死ぬ

2022/11/01(火) 11:31:09.90

>>344
むしろその通りだから地雷なのよ

2022/11/01(火) 11:35:22.17

- 競プロ、まあ一応水色ですけど他に専門分野/強みあります

- ガチで競技として取り組んでててICPCメダリストです

アピールするならどっちかのスタンスだと思ってて青で下のパターンで来るやつがいてヤバいという話ね

2022/11/01(火) 11:35:51.24

壮大な取り違えをしててすまんが、青は高すぎて微妙って話か？
いや、まあ高すぎるってほどでもないだろ、って感覚だけど

2022/11/01(火) 11:38:35.93

>>347
理解したわ
そりゃ青の適切な使い方は上だし、メインウェポンに据えてるやつはヤバいだろう

2022/11/01(火) 11:47:34.29

>>349
でもそういう人特にjobs経由だと相当数いて競プロの評判落としてる気がするのよね

企業からしたらjobsは求人サイトの1つでしかないのにレート条件満たしてたらいけるやろと勘違いしてる的な

2022/11/01(火) 12:03:03.17

体育会系の活動は客観的な成果がそんなでもなくてもメインウェポンになる印象だから、青ぐらいでも頑張り度としては認めてほしい気持ちもあるけどねえ
もちろん、体育会系の活動を通じてわかる協調性や重労働耐性みたいなものを競プロじゃ測れないから、同様に評価されるわけはないんだけど

2022/11/01(火) 12:09:33.52

競プロある程度強いって堂々と言えるのはやっぱり黄色くらいから？
そりゃ橙赤の人から見ればまだまだだろうけどABC対象外にはなるし

2022/11/01(火) 12:12:20.53

>>341
競プロって見た目地味だし何がすごいのか横から見てよくわからないのが課題だから、可視化するのは効きそう
N^3をNlogNまで落とした←ほーん、で？
N=1e5だと6億倍の高速化←お？
目に見えるようにするとこれだけ速くなっている←おお！
ぐらいの印象の差が出るんじゃないかと思う

2022/11/01(火) 12:20:49.62

>>352
業界に競プロerがそんなにいなければ、青ぐらいでも強いと言っていいレベルだと思うかなあ
そういうところではむしろ競プロ自体がどうすごいのか伝えるのが課題になってくる
競プロerがたくさんいる企業だとすると、その人たちのレベル感次第では黄色も「頑張ってる」ぐらいの表現で留めた方がいいかもね
赤はさすがに無条件で強いと言っていい気がするけど

2022/11/01(火) 12:22:10.63

黄色が強い方にならない企業ってよほど限られたところだとも思うけど

2022/11/01(火) 12:34:48.15

青黄が社会で自分は強いとプレゼンしてもそんなに問題は起こらないだろうけど、大会でわかりやすいタイトルを取れるほどでもないから(中高生ならJOIでちょっと積めるが)、別のところでのアピールもあった方が無難

2022/11/01(火) 12:35:28.03

競プロってあくまで経験の1つとしてしか見ないよ
仕事でソロの競プロやらせるわけじゃないし…
コミュニケーションに問題ないか、とか開発経験の有無だとか、他にもいろいろチェック項目あるし競プロ以外のことも聞かなきゃならんのよ
競プロしかなさそうだな、ってひとには競技プロの取り組み方とかを掘り下げて聞くけど

2022/11/01(火) 12:38:40.95

まあ、仮に赤あってもほとんどの場合サブウェポンには変わらんと思うぞ

2022/11/01(火) 14:45:32.58

黄色だけどそんな就活の役には立たんかったぞ
それよりは他に普通の開発経験を持ってて、その中で競プロをどう活かしたかの方がウケは良い
が、大抵はチーム開発経験を聞いてきて、そっちが弱いと露骨に微妙な表情するんだよな……あと最終面接で落ちる

2022/11/01(火) 16:21:29.40

ヒューリスティックの実績メインで採用されてるのは結構見るようになったけどね

2022/11/01(火) 18:54:40.62

いくらアルゴリズムに強くても即戦力から遠いからな

普通に自作した小規模の趣味のwebサイト運営してますみたいなパンチはない

2022/11/01(火) 18:57:26.58

webサイトを立ち上げられる　& ノウハウを持っている
セキュリティ意識が高い&ノウハウがある　←　これが一番大事

競プロ出来てもまともにクラスも書けない人
いらんわな～

2022/11/01(火) 19:11:55.23

CTFとかkaggle辺りでの実績ってどういう評価になるんだろう

2022/11/02(水) 14:13:37.34

組合せ最適化第6版の和訳が出るぜ

2022/11/02(水) 18:02:49.90

https://github.com/yosupo06/library-checker-problems/issues/895
ガウス整数環での素因数分解
A+Biとしたときに|A|,|B| <= 10^9でも十分高速でできる
数論の知識が豊富なら再発明は困難でもなさそう、ABC-Gぐらいの問題っぽい？ARC/AGCタイプではない
結構知識を使うので考える過程でいろいろ勉強になった

2022/11/02(水) 18:08:47.53

コルテ和訳助かると思いつつも、17600円となかなか高い
第2版が値下がりしたりしないかな