競技プログラミング総合スレ 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/13(日) 13:45:12.57

自分はすぬけ君の地下鉄旅行を思い出すのに時間がかかって間に合わなかった

2022/11/13(日) 14:19:52.10

確かにハブ的なものを作って辺の数のオーダーを落とすという典型は微妙に有名じゃないのか

2022/11/13(日) 16:09:21.76

Cの嘘解法、これを思い付くほうが想定解思い付くよりずっと難しいだろみたいなところがあるな

2022/11/13(日) 16:10:36.90

Cの嘘解法、これを思い付くほうが想定解思い付くよりずっと難しいだろみたいなところがあるな

2022/11/16(水) 02:30:47.15

httf提出したあ

2022/11/17(木) 19:51:39.15

AGC 生えてるけど冷える気しかしない

2022/11/17(木) 22:29:51.89

ARCも入ってるし、ICPC終わってエンジンかかってきたな

2022/11/17(木) 22:32:50.54

AGCの告知2週間前とかにされるんだな

2022/11/17(木) 22:56:08.64

今年で3回目のAGCか
だいぶ開催数減ってきちゃったね

2022/11/17(木) 23:01:38.63

一時的なもので外国人に協力してもらえばなんとかなるのか、本当に問題が枯渇してこれからどんどんAGC作問が厳しくなっていくのか気になるところ

2022/11/17(木) 23:11:25.50

Agcあとは年末に2回やれば及第点にはなるか

2022/11/18(金) 04:56:12.51

AGCの問題傾向よく分からん

2022/11/18(金) 15:45:59.95

こどふぉdiv.1ははなんだかんだ生えてるがインドは生えなくなったしどこも問題枯渇してるんだろう

2022/11/19(土) 15:26:42.45

opencupとかどういう質の問題が出てくるんだろうね
漏れ出てくる話を見る限り、割と知識バンバン使いそうな印象でAGC的な感じじゃなさそうだけど
AGC的傾向が唯一のものではなくて、そこで問題を食い合ってたら大変だなと

2022/11/19(土) 16:00:48.74

うんち！

2022/11/19(土) 16:13:20.32

Dまでにダイクストラを使った問題を2年くらい見てない気がする。やるだけになりがちなので出ない。

2022/11/19(土) 16:55:11.41

そりゃ直球でダイクストラをやる問題なんて中々出ないでしょ　ダイクストラに一手間加えたものは結構DEくらいで見かける気がするけど

2022/11/19(土) 17:01:35.33

どのコンテストの話なのかambiguousだ

2022/11/19(土) 21:53:02.57

opencupはかなりあらゆる問題が出るし難易度が高すぎて質とかよくわからん

2022/11/19(土) 22:40:57.03

E問題
やり方思いついたけど時間間に合わんかった
マジで悔しい

2022/11/19(土) 22:42:42.99

同じく。Dまでが難しく時間かかるから解けそうでも足りない。
問題数増やすなら通りやすくしてほしい。

2022/11/19(土) 22:42:46.42

G無理すぎ

2022/11/19(土) 22:45:13.42

6完
G真ん中先にとって対称に取れればいいけどそうじゃないときが分からん

2022/11/19(土) 22:47:01.65

B問題を読み間違えたのもあるけど一時間使ってしまった😭
Cが定型問題っぽかったのに残念すぎる…

2022/11/19(土) 22:47:25.31

ちなみに俺が考えたE問題の解き方として

横移動するときに、移動前の列と移動後の列の差分を計算して行くっていうやり方なんだけど

これじゃアウトなんだろうか。300っていう制約があったから計算量的に足りる気がしたのだが

2022/11/19(土) 22:47:36.14

Grundy数と真似っ子の複合でなかなか教育的な問題

2022/11/19(土) 22:49:01.60

https://imgur.com/a/Q2WBP15

Dまではノーミスでできた。
緑に近づけていたらいいな

2022/11/19(土) 22:51:20.76

Fまではだいぶ素直でABCらしい回だった気がする　
問題文やたら長かったけど

2022/11/19(土) 22:57:02.19

EとFの難易度が釣り合ってたのも久しぶりな気がするな
数ヶ月前のD辺りに似たような問題あった気がするし逆に置かれてたらFの方が解かれてそう

2022/11/19(土) 23:06:18.86

>>508
ちゃんと実装すればいけるんじゃない？
計算量増やさないようにする縦移動が少しめんどくさいので、二次元累積和の方が実装は簡単な気がする

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に手が届くレベルまで早くいきたい