競技プログラミング総合スレ 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/11/19(土) 23:06:20.86

ってか競技プロって実務で役立つ説ってどうなんでしょう
atCoder初めてはや３ヶ月だけど、
IT業界２年目で実務で、皆が重いって言ってる内容とか全然重く感じない

競プロによる基礎体力があるからでしょうか（願望）

2022/11/19(土) 23:07:43.19

Fは素直だったね
確かにABC-Fはたまにかなり素直なDPが来る印象

2022/11/19(土) 23:09:38.17

プレッシャーの中で頭使いながら速くコード書く練習してるから基礎体力をつける的な意味では十分役に立つんじゃないの？って思うね

2022/11/19(土) 23:10:56.74

引退します
https://i.imgur.com/fZw65ga.png

2022/11/19(土) 23:13:26.30

だよね
ただ、それ以外のサーバー知識とかlinux周りとかはやっぱり経験者の方が強いわ

でも、10年以上IT業界にいる人よりもSQLをかけたりするんだよね

こういうのって、職人の世界で言ういわば力持ちで、広く浅い（？）知識もってる人より偉くなりにくいのかね？どうなんだろう

2022/11/19(土) 23:17:05.43

>>514
BからC問題くらいまで解けるようになる価値はめちゃ高くて最も役に立つ帯域だと思う

2022/11/19(土) 23:19:13.45

>>514
おれも業務経験ガッツリ積んでから競プロやってるけど、競プロの知識が業務に役立つことほとんどないよ

例えばデータベースでは全レコード数をNとして、検索速度はO(logN)やO(1)らへんに落とし込むのがもともと当たり前だし、役立った気はしない
強いていうなら実装から見積もりができるようになったから、計算量やばいコードの見分けがつきやすくなったぐらいだけど、そんなことが役に立つ機会ほとんどない
なぜかというとオンメモリにたくさんデータを入れることがないからだろうな。1台の計算機でがんばるよりも、どうやってスケーラブルにするかってのが重要だし

アクションゲームのフロントエンド側とかだったら、オンメモリでいろんな幾何学的処理するからもっと役に立ちそう

どの問題が重いって言われてるのか知らんけど灰や茶が重いとか言ってもアテにならんし、ABCは他の競プロコンテストと比較すると圧倒的に実装が軽いしどういうことだろうな？

2022/11/19(土) 23:23:26.36

>>508
自分はそれで通したよ

2022/11/19(土) 23:23:39.51

>>520
514だけど、重いって言ってるのは実務でだよ

かなり細かい場合わけが必要だから時間がかかるっていう実装を頼まれて、3日とか想定してたのを30分くらいで終わらせた

スケーラブルにするのも大事だけど、細かい部分を見る目は大事なんじゃないかね？って思う時はある

今elasticsearch触ってるけど、細かいスコア計算の部分とかそういうのを把握するっていう意味で理数的な競プロの考え方はすごく役に立ってると感じる

2022/11/19(土) 23:24:31.32

>>521
やめろおおおおおおおおお

俺のやり方が間違ってたって思えれば時間間に合わなくてもあきえあめがつくのに。。
やっぱりそうか。。。
悔しい

2022/11/19(土) 23:25:42.08

基本的にはオンラインパズルゲームでしかないから競プロが実生活に役立ったら美味しいくらいに捉えて楽しむのが賢明で、役に立つことを期待して取り組むもんでもないってずっと言われてると思う
まあABC-B、Cくらいの指示に従って愚直にコードを書く問題は業プロの基礎体力に直結する気がするからスラスラ解けるのと解けないのでは全然違う気もするけどね

2022/11/19(土) 23:27:48.07

>>522
たしかにソロバン経験があると暗算が早くなるのと似たような感じで
競プロやってれば数学的/論理的な思考はだいぶ早くなるだろうね

2022/11/19(土) 23:30:38.86

>>524
業プロにワロタ
いやさ、今メンバーをプロジェクトにアサインする問題が会社にあって、

該当メンバーがコードの読み書きが全然できないって客先から怒られてたりするんだよね

だから、競技プログラミングのA問題を解けるかどうかで判定してみるのはどうだろうっていうことを提案しようと考えてた
解けるかどうかっていうよりもそれを解くときの姿勢とか、調べる気持ちとかがあるかどうかってそこで見極めることができる気がする

B問題でもいい気はするけどB問題以降はガチ勢っぽいイメージ俺は持ってるからメンバーのアサイン判定には不向きかなって

2022/11/19(土) 23:31:26.81

ABC-Cあたりがごく普通の業務で出て来る可能性があり、なおかつかなり個人差がある領域だと思ってるけど、そこが速いと捗る
その部分が進捗のボトルネックになってしまう人もいるので

2022/11/19(土) 23:33:39.83

自分は競プロできないからどうのみたいな考え方はそんなに好きじゃないけど、さすがにプロのプログラマーだったらABC-Aは解いてほしいかなあ

2022/11/19(土) 23:34:14.93

>>526
なんか普通にやたらレベルが低そうで笑えないな
とりあえず学歴フィルターしたら？

2022/11/19(土) 23:37:35.70

思うんだけど、
競プロって計算量オーダー云々っていうよりも

データの構造とかハッシュテーブル的なものをちゃんと理解しているかどうかだと思う
そういうあたりを正確に理解してれば、計算量なんて悪いパターンになることを知ってれ場何とでも対策できる

プログラム書く上においていろいろな構造を正確に頭の中で描けるかっていうことを図るいみで競プロは非常に有効だと考えてる

2022/11/19(土) 23:38:35.53

愚直に(全探索とかをして)コードを書いても制限を超過しないっていう点でABC-B(と一部のC)くらいまでは確実に業務に直結すると思うよ
たまにプログラミング関係なしで簡単な算数・数学っぽい問題も混じってるけど

2022/11/19(土) 23:39:20.45

>>529
俺自身が29歳までトラック運転手の高卒だし、学歴フィルターはできない
アサインチームがOJT目的であまりにもポンポン案件入れてしまうので、業務チームが火を噴いていることは事実
だから、A問題を解いてみてが一番いいと思う

2022/11/19(土) 23:39:40.71

>>530
そうだね、情報系学科を卒業してないなら、教養としてせめて競プロ経験しててくれ、って感じはあるかもしれない

2022/11/19(土) 23:46:23.51

頭の中で、配列、ハッシュテーブル、stack、queueのイメージぐらいできてもいいかもね
std::setは平衡二分探索木を忠実にイメージしようとか考えだすとめんどくさいけど

2022/11/19(土) 23:49:47.51

>>531
算数・数学も最低限の教養として必要だと思う

そもそもにして式を立てられないんだったら数字を使う業務にアサインできないと思うし、統計的な考え方ができるかできないかも大事だと思う
競プロで出てくる数学ってD問題までに限って言えば高くても高校レベルだから、漸化式を立てるとかそれくらいはやってほしいって思う

2022/11/19(土) 23:52:10.43

>>513
二次元累積和

覚えやす

2022/11/20(日) 00:02:59.31

Ex、解けてるの一人だけか
相変わらずNyaanさんの解説は読み応えある

2022/11/20(日) 00:36:46.56

>>517
サンプルを試しましょう…

2022/11/20(日) 01:05:14.62

A, Bが解けねえ奴には流石に知的労働は即座に辞めろと言わざるを得ない(´・ω・`)

2022/11/20(日) 01:10:14.63

>>532
ABCコンテストで試すより、それだったらPASTかPaizaのほうがいいかもね

2022/11/20(日) 02:11:59.36

Wとw間違えて3分ぐらい無駄にしたんだけどおすすめのフォントない？

2022/11/20(日) 02:43:28.01

problems見たらEが緑下ってコンテストのレベル上がった気がする。灰色コーダーは普通に優秀。

2022/11/20(日) 02:48:57.41

なわけねーだろハゲ

2022/11/20(日) 02:57:39.92

Cが灰色で慣れてればなんでもないけど、グラフの教科書通りリンク行列とか作ったりしちゃったらメモリが全然足りないとか

2022/11/20(日) 02:57:59.89

一昔前の茶が灰上位ぐらいになってて、灰上位の能力があれば十分通用する職場がたくさんあるのは事実な感じがするわ

2022/11/20(日) 09:19:09.77

今レート590なんだけど今日のARC問題、挑戦したら事故る可能性高いかな

A問題だけのみ完だとレート下がるんだろうか

2022/11/20(日) 09:42:39.68

とりあえずやってみたらいい
心配なら過去問もあるし
そのレートなら失うものはないと思うが

2022/11/20(日) 10:05:58.27

ARCはABCほど過去問を解いたからと言って解けるようになるとは限らないけどな！！！

2022/11/20(日) 11:38:53.13

Arcはせめて水色以上じゃないと0完がデフォになる
俺は緑だけどarcの茶diff が解けないこと多い
同じ色でもabcとarc だと難易度違うんだよ

2022/11/20(日) 13:12:17.38

コードの書き方とかアルゴリズムの基礎とかはJOIの過去問とかでもかなり良いよ
難易度によって変わってくるけど

2022/11/20(日) 19:10:56.38

今日のARCのA問題400点なのか怖いな

2022/11/20(日) 20:04:10.36

初挑戦だけど参加者が思ったよりハイレベルでビビった
Dまで解いて半分よりちょっと上程度なのか
そりゃ上位人にはかなうはずもないけどまさか底辺までここまでやるとは

2022/11/20(日) 20:12:36.50

AHC Nが小さい方が点数が大きくなるの見落としてて悲しい

2022/11/20(日) 22:17:57.35

参加者の属性で一番多いのが東大やからそりゃレベルは高い

2022/11/20(日) 22:21:08.79

東大生だとほぼ全員E問題は楽勝レベルなんだろうか

2022/11/20(日) 22:34:39.19

コンテスト中は一切の感想呟いちゃいけないのよね

2022/11/20(日) 23:02:04.72

2問が限界

2022/11/20(日) 23:03:24.44

傾斜が見事やね

2022/11/20(日) 23:11:55.12

とても丁度よく感じた

2022/11/20(日) 23:13:08.12

>>555
ABCでもそんなことはないと思われる

2022/11/20(日) 23:18:17.14

A問題、解き方はすぐにわかったけど、実装でかなり苦労したな
1時間以上かかった

B問題は問題読んでそっとじ

A問題、俺は端から一個飛ばして、数字毎に一個飛ばしっていうやり方をとってACしたけど
これが本当に一番最悪のケースっていうことって数学的に証明できるんだろうか

2022/11/20(日) 23:22:34.99

B、Cみたいなエスパー寄り問題下振れるとキツい

2022/11/20(日) 23:29:58.42

>>561
埋めていったときに空き区間の長さの最大値の最小値が1以下にするようにって感じだけど、確かに証明はめんどくさそう
直感的には明らかなんだけど

2022/11/20(日) 23:31:40.39

BもCもエスパー効かなくて崩れたやつ多そうだな
ARCっぽい感じだった

2022/11/20(日) 23:34:20.66

正直BよりDの方が解きやすいまである
焦った

2022/11/20(日) 23:45:52.50

Bとかパッと見かなり簡単そうなのに始点が同じ場合だけ考えれば良いことに気づけないと沼にハマって詰む

2022/11/25(金) 16:38:52.84

ABCの過去の問題見てると昔は簡単だったんだな。
C問題くらいまででも今のBより簡単じゃね？と思える

2022/11/25(金) 16:57:42.32

教材の充実や競争の過熱で、同じdiffでも今の方が難しくなってる傾向はあるよ

2022/11/25(金) 18:53:15.81

C++使いが問題作ってるから若干C++に有利だな
専用のライブラリが使えたりするし再帰呼出しとかのC++が苦手そうなやつはスタックオーバーフローしない回数になってるし

2022/11/25(金) 19:01:46.01

それはしゃーないわ

2022/11/25(金) 19:11:48.40

横レスなのだが、
C++って割とstack over flowには強いんじゃないの？
興味ある

C++が優遇されているのは同意
もう少し、Pythonの人へ配慮を…

2022/11/25(金) 20:17:30.79

常に問題の制約が64bitが前提になってるのがまずけしからんわけだ
64bit整数が扱いやすいなんてC/C++、JavaやGo、みたいなコンパイル前提の言語ばっかじゃん
たまには150bitらへんを制約にするとか
正規表現使えば楽勝みたいな問題をもっと出すべき

2022/11/25(金) 21:26:56.40

>>569
スタックオーバーフローしない回数なんじゃなくてatcoder上でオーバーフローしないってだけじゃないの

atcoderはスタックサイズ上限無制限にしてあるからmemory limit超えない限り落ちない

2022/11/25(金) 22:03:32.16

ノートPC持ってる人多いのか？
仕事はノートPCだけど会社から貸与されてる仕事用のものだから私用に使えないし、
自分のPCは基本的に自宅でしか使わないからデスクトップで十分だしスペック的にもデスクトップがいい
わざわざPC2台持たないし

2022/11/26(土) 00:15:04.34

あっそ

2022/11/26(土) 12:13:25.49

ガイジガイジガイジガイジガイジ
ガイジガイジガイジガイジガイジ
ガイジガイジガイジガイジガイジ
ガイジガイジガイジガイジガイジ
ガイジガイジガイジガイジガイジ

2022/11/26(土) 12:57:16.88

デスクトップPCはかなり機能強めのものを買って機械学習専用機にしていて、出先とかでも使える用のミドルスペックノートPCを普段使いにしているよ

2022/11/26(土) 20:12:54.37

競プロやるかーって思ってたけどなんかいまいち評判よくない感じなので見送り気味。プログラミングする人間に頭でっかちはちょっとダメ＞＜

2022/11/26(土) 22:08:05.48

なんだこいつちょくだいかよって思ったらちょくだいだった

2022/11/26(土) 22:42:27.81

D問題、普通に数学解けないと解けない問題が出てきたな
AC出来たからいいけど
A～Cまでは普段と比べてめちゃくちゃ簡単だと感じた
E問題は問題の意味が分からず、残り２０分でようやく意味が分かって時間的に足りないと思ってそっ閉じ

2022/11/26(土) 22:42:29.80

5完
F頑張ればできそうな気はするが時間切れ

2022/11/26(土) 22:43:41.33

https://imgur.com/a/gd38p1G
緑に近づきますように（レート落ちませんように）

2022/11/26(土) 22:45:47.35

>>581
今日プロ始めたばっかのころ（ここ４カ月以内）
DがとけなくてEが解けたっていういこと一回だけあった

それ以来E一回も解けていない
Eに手が届くレベルまで早くいきたい

2022/11/26(土) 22:57:30.63

D、最適化ライブラリでどうしても10^-3までしかあわないまま80分とかしてダメ元で投げたら通った・・・

2022/11/26(土) 22:59:44.90

>>584
python?どんなライブラリなのか教えてほしい

2022/11/26(土) 23:03:02.04

d問題で最小値を求めるべき関数、ほんとだったら下に凸なことを証明しなきゃいけないんだろうけど、「導関数が0になるとこ一ヶ所しかないからここが答えやろｗ」って解答しちゃった

2022/11/26(土) 23:04:28.90

>>586
俺も
高校時代だったらすぐに証明できただろうけど
わからなかったからmatplotlibで関数の形見て下に凸だって決めつけてしまった

2022/11/26(土) 23:20:38.01

>>585
scipyのoptimise

2022/11/26(土) 23:29:09.61

１年ぶり位に復帰したけどインフレやば過ぎワロタ
三分探索が茶とかもう無理ゲ

2022/11/27(日) 00:02:27.32

別に三分探索しなくても解けるからね

2022/11/27(日) 00:11:00.75

手計算したくないから、回答と少し違うwolfram先生の解析解の周辺の最小値でやったけど、最後のサンプルがどうやってもあわなくscipyに。実務家的ｗには脳死でoptimize一択。

2022/11/27(日) 00:29:03.57

Dで10^18制約で誤差10^-6無理じゃね？と思ったら絶対誤差または相対誤差って書いてあることに気付いた
ひょっとして今までの問題も全部そうだったのか

2022/11/27(日) 00:30:45.88

Python しか触ってないからわからないんだけど
他のCとかだと誤差が大きくなって3分探索とか使わないといけなくなるもの？

2022/11/27(日) 00:34:30.35

>>592
微分して0になる点の整数インデックスさえ求められれば
そこからプラマイ5くらいずらして最小値を求めてばいいと思うけど
俺はPythonでインデックスとインデックス＋1の最小値で求めることできたけど
ってか代数的に解ける問題が出てくるんだなってびっくりした

2022/11/27(日) 00:38:57.81

せっかくデ/アのスキルを磨ける競プロをやってるんだから、代数解法よりも三分探索を使って解いてほしいところ
まあ競技的にはとにかく解ければ勝ちなんだけど

2022/11/27(日) 00:42:37.70

>>595
計算量を考察する箇所でも代数的な考察するし

代数だけではどうしようもないということを頭でしっかり認識してからパズル的に解くのが醍醐味だと思うんだけど

2022/11/27(日) 00:44:19.50

>>593
想定解法であれば、3分探索で絞り込むのは「操作回数」だから、誤差が代数解法よりも小さくなるわけではないよ

2022/11/27(日) 00:46:09.44

そうだね、そら何にしても数学は使うよ
デ/アはそもそも数学が下地にあるからね

2022/11/27(日) 00:47:05.59

>>597
誤差の部分よくわからんのよね
どのくらいの誤差が起こり得るのかが
コンピュータの深い部分か何かしらの知識があればわかるんだろうけど

FFTで誤差が出ないから、とりあえず実用範囲で小数計算の誤差は考慮してないな
それだけPythonが数値計算で有能なのかも知れないが

2022/11/27(日) 00:47:32.02

>>598
デ/アって何？？

2022/11/27(日) 00:51:50.68

>>599
きみは何らかの代数ライブラリを使ったのかもしれないけど、おれが「代数解法」と呼んだのは公式解説にある「解法2　微分」のこと
「解法1　三分探索」でも「解法2　微分」にしても、どちらにしても最小値になる回数を見つけてからの計算方法はほぼ同じだから、同じ精度で答えが出力される
よって誤差は関係ない

>>600
データ構造とアルゴリズム

2022/11/27(日) 00:53:59.03

>>601
俺は微分したけど、3分探索はわからないけどLogNとかになるのだとしたら微分したらO(1)だと思うからそっちの方が速そうだけどな

データ構造／アルゴリズム
→わからんかったよ。。

2022/11/27(日) 00:55:09.30

>>600
データ構造/アルゴリズムの略

2022/11/27(日) 00:56:10.24

>>603
解説聞いたらわかったけど、初見じゃわからんかったよ

2022/11/27(日) 00:58:54.64

すまんな、競プロの界隈だとデ/アってよく使うから当たり前に使っちゃうわ

2022/11/27(日) 00:59:07.32

数学が下地にあるのは確かだけど、日本の学校教育では出てこないようなパズル問題が出てくるところが競プロの好きなところ

2022/11/27(日) 01:00:50.63

>>605
常識だったのか。スラッシュあまり使わない俺はあまり馴染まないかも知れない(と言って1週間後使ってるかもしれない)
競プロ初心者高卒だから、そういう界隈の言葉どんどん教えてくれると嬉しい

2022/11/27(日) 01:06:28.84

いや、ただのTwitterスラングやで
わからんくて当たり前

2022/11/27(日) 01:16:51.24

まあプログラマーは一応理工系技術職だし、高校理系標準レベル微積ぐらい扱えた方がいいと思うぜ

2022/11/27(日) 01:35:50.76

理系ならフォートランつかえ

2022/11/27(日) 02:20:45.46

ワテが3分探索を使わない理由は
・最適化の本で見たことがない
・多次元に拡張できない、教プロ特有な気がするので学習モチベがわかない

こんなところか・・・

2022/11/27(日) 05:04:19.20

今回は入力が整数だから二分探索のが分かりやすい気がした
めぐる式でf(x)とf(x+1)を比較して大きいならok、そうでなければng
最後にf(ok)を出力するだけ

2022/11/27(日) 08:39:17.72

下に凸と想定して二分探索で解けたよ