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

■ このスレッドは過去ログ倉庫に格納されています
1デフォルトの名無しさん (ﾜｯﾁｮｲ 1f9f-qCnf)
垢版 |
2021/07/28(水) 21:58:48.02ID:nljYiy+l0
!extend:checked:vvvvv:1000:512
↑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/

※前スレ
競技プログラミングにハマるプログラマのスレ 62
https://medaka.5ch.net/test/read.cgi/prog/1626625368/
VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured
2021/10/24(日) 20:18:53.47ID:1P0Qc1d30
最近某ngtの質問箱に毎日のようにキモいのが送られていて、流石にかわいそうになってきたな。
2021/10/25(月) 00:43:40.20ID:xXPH57uh0
最近始めたけどついさっきああでもないこうでもないおかしい計算が合わないみたいなこと延々とやってC問題一つ解くのに2時間半かかった
辛い
2021/10/25(月) 04:27:00.29ID:GyOhDsWs0
実験エスバーって鍛えることできんのかな
2021/10/26(火) 22:34:52.78ID:59ycdlv3M
数学ではよくある考え方やテクがABC-Cから登場すると思うけど、基本的なものでも初見だと難しいものが多いと思う
最初からスムーズに解ける人たちは散々似た考え方に慣らされてきた人たちだと思うし
ABC-Cぐらいの数学的思考の素養ぐらいは身に付けておいて損はないと思うから、慣れてみるといいんじゃないかな
2021/10/26(火) 22:38:10.35ID:Z19LRAELr
競技プログラミングは役に立たない！！！１１１１１
2021/10/26(火) 22:43:03.70ID:59ycdlv3M
グラフや木の問題だったら手癖でよくあるケースを作れるようにしたりして実験そのものをスムーズにできるようにしたり
愚直解の実装を早めにやるように心がけたり
ありがちな注目すべき量(パリティー、剰余、木の葉の数、木の直径、頂点の次数、連続する二項の差分、転倒数、総xor…etc)の知識が増えてくるとエスパー精度上がりそう、俺自身実験エスパーそんな得意じゃないから知らんけど
2021/10/30(土) 01:57:46.41ID:cDpW0Kxw0
C問題ぼちぼち解けるかなくらいのレベルなんだけど時々手も足も出ねぇ…ってのが紛れてて辛い
まぁそういうのは大体みんなの正答率も低いんだけど
2021/11/01(月) 14:31:29.29ID:i3pN4gLD0
AGCの問題の解き方わからんね
昨日も、Bは不変量見つける感じで典型要素があるといえばあるけどAとかアドホックすぎる
2021/11/01(月) 17:13:19.31ID:xYwaxLMb0
文字種を減らして考えるの典型かもしれん
2021/11/01(月) 18:46:47.15ID:Dv3I90PDa
不変量見つけられなくて死んだ
351デフォルトの名無しさん (ﾜｯﾁｮｲ 1302-48dE)
垢版 |
2021/11/04(木) 22:10:01.18ID:hqf6Ttzz0
AtCoderの「第二回 アルゴリズム実技検定」のテストケースはどこにありますか？
2021/11/04(木) 22:38:53.47ID:KITyg0nv0
dropbox に上がってないのなら無いんじゃないか
2021/11/13(土) 00:38:47.84ID:WhtcoC320
ちょっとずれた話題になるけど競プロ好きな人ってどういう方向の就職が向いてるのかな
よくある金融系とか医療とか販売サイトとかそういうのが全然ピンとこない。ロジックを考えるのが楽しいのであって何を作るかにあまり興味ないというか…
2021/11/13(土) 13:07:06.56ID:7FvDzxQTr
無職
355デフォルトの名無しさん (ﾜｯﾁｮｲ 2302-09aj)
垢版 |
2021/11/13(土) 23:13:52.96ID:cg3EZESf0
paizaのSを全解き目指してるレベルの者だけど、>>345の意見には納得するところがある。
競プロやる前は、クラス定義してDictionaryでどうこうすれば、大抵の問題は片付いた
わけだが、競プロの問題ではクラスなど定義していたら時間切れになってしまうので、
配列だけで何とかするという、文法的にはレベルの低い書き方をして、いかに実行時間を
短くするかということに主眼がおかれていると思う。ビジネスで使うには10の何乗という
データ数はない場合がほとんどだし、計算に１週間程度掛かるのも問題ないことが多い。
競プロ的な書き方をすると、他のプログラマーとコーディングスタイルがかなり異なって
しまうと思う。
2021/11/13(土) 23:22:26.39ID:uY2REMe7r
>>355
>>345だけど長文キモイ死ね
2021/11/18(木) 20:07:30.91ID:Y/dc6XOP0
>>355
個人で開発するとき役に立つよ
2021/11/18(木) 20:15:30.78ID:otq4UsEcr
いや役に立たない
2021/11/18(木) 20:46:20.19ID:yaHQuJEZ0
paizaはatcoderと比較して時間制限が緩いし、その制限に間に合わないときは、
他に最適なロジックがあるってことだと思うよ

あと競プロを解いていると、自分が知らないやり方とか、効率の良いやり方を
知ることができるということが大きいと思う

意外と文字列と時間の細かい扱い方とか知らないことがあるので
それを知るきっかけになるので勉強になる
2021/11/28(日) 10:44:07.64ID:BXa3qjcoM
その是非や影響の議論は置いといてAB難化は事実だと思うんだけど、copilot対策という噂は本当なのかな？
2021/11/28(日) 10:56:10.69ID:DkHLSjjA6
ソースは特に見当たらないけど、それ以外にABを難しくするモチベがあまりなさそうだからそう言われてる
あとは精々、企業コンではあまりにもひねりのない問題の出題は避けてるとか？
362デフォルトの名無しさん (ﾜｯﾁｮｲ f79a-i1Ew)
垢版 |
2021/11/28(日) 13:18:03.58ID:ykDYmOS+0
競技プログラミング的なロジック組んで金になる方法考えてみようぜ
とりあえず俺は自動取引系ソフトに一票
2021/11/29(月) 02:15:40.60ID:6Nke2U5s0
取引系の問題は未来が見えてることが前提だからなあ
364デフォルトの名無しさん (ﾜｯﾁｮｲ 977c-VbP9)
垢版 |
2021/12/01(水) 02:28:23.44ID:7HPQuU+R0
ABC226-H の解説に類題として挙げられていた以下の問題が解けません
> 区間 [0,1] 上に一様ランダムに区切り線を n−1 本入れて n 個の区間に分けた時、 k 番目に短い区間の幅の期待値は？
ABC226-H 自体はすんなり解けたのですが上の問題は正直N=3の時点で自分には手が出なくて、困ってます
2021/12/02(木) 20:39:33.36ID:rnInpLg+M
まず、k=1はわかりますか？
これは期待値がx以上になる確率を考えるとできるはず（累積分布関数を考えているという点が類似ポイント）

で、一般の場合は包除原理を適用するとできる

途中式省くけど答えは1/n (1/n + 1/(n-1) + ... + 1/(n-k+1))になります
2021/12/04(土) 08:39:45.51ID:x9fVLDRG0
ええと、k=1の場合は
P(x) を x 以上となる確率として \int_0^{\infty} P(x) dx が求められれば良い
x 以上となるような区切りの入れ方は[0, 1-nx] に区切りをn-1本入れて、各区切りの間に幅xを挿入したものと一対一対応するので
P(x) = (1-nx)^{n-1}
よってk=1の答えは \int_0^{\infty} P(x) dx = 1/n^2
みたいな感じでいいでしょうか
2021/12/04(土) 11:45:52.27ID:GTTC1A5Hr
競技プログラミングは役に立たない！！！１１１１１
368デフォルトの名無しさん (ﾜｯﾁｮｲ 5202-PP5C)
垢版 |
2021/12/04(土) 12:33:36.19ID:gg0i98sn0
>>367
355だけど、役に立つよ。頭の体操になる。数学の問題を手で解くより面白い。
2021/12/04(土) 13:13:02.72ID:cnvRxgJD0
月刊はスルー
2021/12/04(土) 17:52:55.15ID:Sp+Fe1MX0
問題解くときの計算用紙代わりにブギーボードとかの電子メモ帳を買ったんだけど書き心地良いしかなり良かった
おすすめ
2021/12/04(土) 18:44:46.61ID:4uhn1ZQo0
>>366
0とmax取るか積分範囲を1/nまでにしないと壊れると思うけど合ってる
2021/12/04(土) 23:30:13.88ID:HadgEFtEa
>>370
何インチのやつ使ってる？
2021/12/05(日) 00:26:27.51ID:3WaDD3Ky0
>>372
10
2021/12/07(火) 22:01:44.64ID:XzzazBW10
ipadええぞ
375デフォルトの名無しさん (ﾜｯﾁｮｲ 0f01-izju)
垢版 |
2021/12/18(土) 14:36:12.14ID:EFVtFN3G0
「ゲームで金儲けする時代止められない」ＣＣＰゲームズ代表インタビュー

「CCPゲームズ」のヒルマ・ベーガー代表は14日、オンラインインタビューで最近、
話題に浮上した「プレイトゥオン（Play to Earn 儲けるゲーム）」について「世界のゲーム業界には、
すでにゲームアイテムを取り引きする2次市場が存在する」とし「儲かるゲームは以前にもあったし、
これからも止められない流れになる」と診断した。
CCPゲームズは、世界的な人気ゲーム「イブオンライン(Eve Online)」を開発・運営する。イブオンラインは、
世界で4000万人以上が楽しんでいる。
CCPゲームズは最近、NFT（代替不可能トークン）コンテンツを披露し、注目を集めている。
「アライアンス・トーナメント」というゲーム内の大会商品でNFTコンテンツを配った。
2021/12/21(火) 13:47:34.46ID:8AspzEl40
最近勉強始めたばかりの初心者だけど動的計画法でつまづいている
部分構造最適性っていうけど、損して得取れというか一部では損でも全体で見れば最良になるような問題やケースは無いのか？って思う
2021/12/21(火) 14:46:04.05ID:PWwxpbwJd
ないことを証明して使うんだぞ
2021/12/21(火) 18:49:26.20ID:gTw96teU0
枝刈り全探索だと思うとよさそう ナップサック問題でいうと大きさは同じなのに価値が低い組みたいにどう頑張っても得にならないケースは使わないように大きさごとに価値が最大のものだけ持っておく感じ？
2021/12/21(火) 20:30:24.97ID:JiGJ+/NL0
動的計画法がいまいち理解できない人には、メモ化再帰バージョンを試してみてほしい
と、個人的には思うんだけど、再帰呼び出しそのものが難しいかしら？
2021/12/21(火) 21:03:00.48ID:msz2/cZB0
馬鹿みたいだけどちょっと大きめの表を手で埋めてみるといいんじゃ
2021/12/22(水) 02:28:33.78ID:Z+1UFQDg0
近頃再帰少しずつ書けるようになってきてメモ化再帰も試してはいる
ただたとえばフィボナッチなんかはわかりやすい。同じ計算してるからメモしておくっていうのは
でも経路とかの問題でmemoは違う値にならえないのか？ってなる。値が更新されてたらそれを返すっていうけどさらに更新される可能性はないのか？って
2021/12/22(水) 07:21:37.51ID:NfauV/oWr
競技プログラミングは役に立たない！！！１１１１１
2021/12/22(水) 22:28:18.00ID:AhLEKKoC0
>>381
違う値になりえる場合は使えないよもちろん

正当性が証明できるときだけ使うし、正当性が担保できるようにアルゴリズムを組むんだよ
これ以上は具体的な問題見ないとなんとも
2022/01/06(木) 16:07:10.87ID:ar76WYHcr
競技プログラミングは役に立たない！！！１１１１１
385デフォルトの名無しさん (ﾜｯﾁｮｲ 9901-sV8s)
垢版 |
2022/01/06(木) 17:53:55.86ID:lFeOOX7v0
白カピを讃えよ
2022/01/06(木) 18:46:38.73ID:+JxpBntd0
新スレどこやねん
2022/01/06(木) 18:49:44.26ID:gEtgsFwH0
>>386
新スレはここです
向こうに新スレは立ちません
2022/01/06(木) 19:00:24.58ID:/n5h7nDr0
ABCが待ち遠しい
2週間も待てない
2022/01/06(木) 19:18:36.50ID:e57wTEaXr
ﾜｯﾁｮｲがなんだ実害はないぞ
390デフォルトの名無しさん (ｱｳｱｳｳｰ Saa5-keiW)
垢版 |
2022/01/06(木) 19:27:37.71ID:sqyEIboYa
別にわっちょい怖くなんかないけど、人がおらんとどうしようもない。向こうのスレコンテスト後の数時間はクソスレ極まってるけど、日常のバカ話で人を引き止めてるところはあるのかもしれない
391デフォルトの名無しさん (ｱｳｱｳｳｰ Saa5-keiW)
垢版 |
2022/01/06(木) 19:30:20.21ID:sqyEIboYa
>>390
>コンテスト後の数時間はクソスレ

すまん「コンテスト後の数時間以外はクソスレ」の間違い
392デフォルトの名無しさん (ﾜｯﾁｮｲ 9901-sV8s)
垢版 |
2022/01/06(木) 19:33:22.15ID:lFeOOX7v0
くんすこ
393デフォルトの名無しさん (ﾃﾃﾝﾃﾝﾃﾝ MM26-ADtK)
垢版 |
2022/01/06(木) 19:52:52.81ID:E4kfzcZtM
常時クソスレだろ？
2022/01/06(木) 22:42:19.30ID:+JxpBntd0
ごみ
2022/01/15(土) 23:10:33.87ID:JDpiuwgA0
どうして制限時間内に解けないのに、制限時間が終わった途端解法が思いつくのか……俺こういうことよくあるんだけどなんでだろうね
2022/01/18(火) 14:45:51.28ID:0TVQxye3M
実力が足りてないからです
〜完〜
397デフォルトの名無しさん (ﾜｯﾁｮｲ a734-B/cF)
垢版 |
2022/01/26(水) 13:16:14.83ID:HUI/BT/C0
>>395
何物にも縛られない「自由な動き」が創造性を高めると判明！
https://nazology.net/archives/103764

多分これが一番近い理由だと思う
創造性とは少し異なるけど競プロも発散的思考の要素はある
拘束とも少しずれるけどそれに似た緊張が不調なタスクには絡んでると見てる

>>396
結果だけみて判断するのは他人をフィルターにかけるときは傾向が収束するから合理的だが、個々の事案に向き合うときには不十分だと思うで
398デフォルトの名無しさん (ﾃﾃﾝﾃﾝﾃﾝ MM8f-yRnv)
垢版 |
2022/01/26(水) 17:34:45.45ID:IMxi6ITqM
風呂に入ってたら思い付いたアルキメデスの原理の逸話もあるし、精神状態に応じて辿り着ける思考は違うんだろうね
特にコンテスト終了前後じゃ劇的に違うだろう
考察得意な人は意図的にその辺のモードをコントロールするのが得意だったりしたりするのかも？
2022/01/26(水) 17:37:21.02ID:IMxi6ITqM
ロシア情勢がキナ臭いけど、CodeForces大丈夫だろうか
2022/01/27(木) 13:18:26.14ID:OpKzkVck0
ややズレるがchokudaiもコンテスト中は自分は天才だと思い込まないと解ける問題も解けなくなると言ってるな
強い人はメタ認知が上手いと言っていいと思う
2022/01/31(月) 18:47:21.46ID:Qej12BAi0
昨日のABC-Ex, 答えの値が求まるのはいいんだけど復元ってどうやるの？
2022/02/05(土) 22:52:58.12ID:jPeChQFj0
解説読んでも理解できないとなかなかつらいものがある
2022/02/07(月) 11:20:03.82ID:87L5vkcm0
それは本当に実力が足りてなくて悲しくなるやつじゃん
404デフォルトの名無しさん (ﾜｯﾁｮｲ 6301-piVT)
垢版 |
2022/02/14(月) 10:47:03.47ID:TVm+ejPZ0
フリーランスに立ちはだかる「常駐」の壁。慣例を打ち壊し、
“テレワーク”案件3割→8割へと成長を遂げた「クラウドテック」の軌跡

リモートワーク求人専門サイト「プロリモート」がリニューアルオープン、業務委託契約の求職者と企業をマッチング

1/3以上が採用につながる高マッチング率、リモートワーク×エンジニア・デザイナー専門の
人材紹介サービス「ReworkerAgent」正式リリース場所からも時間からも自由な働き方を実現！

『ReWorks（リワークス）』リモートワーク特化型転職サイトとして 3月5日 リニューアル

副業・兼業マッチングサービス「クラウドリンクス」登録者数2万人突破
中小企業で進む副業人材の採用、96％が継続採用を希望

茨城県日立市、県外からの「テレワーク移住者」に最大151万円の助成金

長野市、市内に移転・事業所設置し、移住することで最大550万円の支援金を支給

フリーランスが活用できる「最大1,000〜3,000万円・補助率50%〜75%」の
『ものづくり・商業・サービス補助金』とは？概要や条件を解説
2022/03/10(木) 16:34:08.09ID:gI/pxyVEM
ここが新スレですね
2022/03/25(金) 03:32:02.97ID:EX0HU7Ak0
こどふぉのE、思い付く過程が知りたい
2022/07/01(金) 23:28:27.46ID:JFBfOGuK0
むこうのスレもうだめかもしれんね
2022/07/02(土) 12:20:53.48ID:64B/Ignl0
こっちでまったりやるか
2022/07/02(土) 14:29:22.62ID:xEhxhveC0
うんち！w
2022/07/02(土) 14:38:46.53ID:eTWk7aiV0
おしっこ！w
2022/07/02(土) 16:34:24.04ID:BfnPedOR0
今日のABCの感想はこっちでやればええんか？
2022/07/02(土) 16:38:30.13ID:WXVFk7BC0
おれもこっちにする
2022/07/02(土) 17:13:03.65ID:Y5ZkAX2p0
むこうってどこ？
2022/07/02(土) 17:43:00.56ID:LoAUafRE0
まともな会話ができるならどこでもええで
2022/07/02(土) 17:53:27.76ID:0olBoaxMr
競プロ関係のツイートに対して言及するならまだしも写真に対して色々言うのは終わってる
2022/07/02(土) 20:55:32.38ID:WXVFk7BC0
ABCでます
2022/07/02(土) 22:55:59.87ID:WXVFk7BC0
うーん、FよりもさっさとGに取り組むべきだったか
2022/07/02(土) 22:59:29.78ID:0olBoaxMr
EFGHも50点ずつでもいいから点差欲しいな
ABCDF>ABCDEだろうし
2022/07/02(土) 22:59:32.54ID:WXVFk7BC0
Eの解説賢い
累積和とダブリング使って解いたわ
2022/07/02(土) 23:01:26.44ID:0olBoaxMr
低レベル帯は上位アルゴいらないって誰かが言ってたけど今回のEとかみたいに考察省略できるのはアドだよなぁ
2022/07/02(土) 23:06:03.64ID:64B/Ignl0
ワッチョイ有りだとガイジスレとイクが居なくなるのでは？
422デフォルトの名無しさん (ﾜｯﾁｮｲ 0a02-9ZeA)
垢版 |
2022/07/02(土) 23:06:46.41ID:2OTHusXb0
Bがこの重さってまじ？
もう新規囲い込む気ないよねこのサイト
2022/07/02(土) 23:08:58.82ID:64B/Ignl0
>>420
>>421
ワッチョイ一致してるけどスマホをwi-fiに接続しただけで自演の意図はないです
紛らわしくてごめん
424デフォルトの名無しさん (ﾜｯﾁｮｲ 8e02-CTF5)
垢版 |
2022/07/02(土) 23:10:19.92ID:cezlBl1t0
BCDの3問がCCCになってる
2022/07/02(土) 23:11:51.52ID:WXVFk7BC0
普通にナイーブだったし何も気にしてなかったけど、diff見るとたしかにB高いな
Fもなんかむずかったし、また文句出そうだな
426デフォルトの名無しさん (ﾜｯﾁｮｲ 0a02-9ZeA)
垢版 |
2022/07/02(土) 23:12:52.80ID:2OTHusXb0
プログラミング入門者で、競技プログラミングやってみよーって人が今回のABCのBをみたらどう思うだろうね
これじゃあ人なんて増えないわ
2022/07/02(土) 23:14:28.88ID:NaXk4Q6c0
Fみたいなやつ実装爆発して終わってまう
428デフォルトの名無しさん (ｱｳｱｳｳｰ Sacf-pVYn)
垢版 |
2022/07/02(土) 23:24:56.50ID:z91+ebe7a
bよく読めばそんなに難しくないんだけどな
出題者がdiff低く見積もったのもわかる気がする
2022/07/02(土) 23:34:27.93ID:64B/Ignl0
ABC255のBのdiffを余裕で越してきたな
歴代最難関Bか
2022/07/02(土) 23:42:03.00ID:cezlBl1t0
ABCで今回のよりもdiffが高いBが出たのは少なくとも5年前
2022/07/02(土) 23:43:25.18ID:WXVFk7BC0
灰や茶にとってはちょっと難しい要素が複数詰め込まれてた感じか？
問題文がちょっとむずい
8方向遷移がちょっとむずい
順番に並べて整数を作るのがちょっとむずい
みたいな
432デフォルトの名無しさん (ﾜｯﾁｮｲ 1b7f-K581)
垢版 |
2022/07/03(日) 00:33:20.34ID:1yNMSZTa0
Bはひたすら面倒くさかった
2022/07/03(日) 00:36:15.46ID:etWgu0oL0
二次元配列の8方向見ていくやつはスニペットとして持っとくべきだよね
2022/07/03(日) 00:37:25.46ID:QOwa7lEj0
水色の自分にとってはEが面白くて、頑張って解いたらレート上がって楽しい回だった
2022/07/03(日) 01:19:00.41ID:dJxTMHTHd
Bはchokudai作問だったか
確かにC問題の難易度だよなあこれは
2022/07/03(日) 11:20:46.08ID:Rs7jP0Dp0
B問題はdiff200くらいにしてあげるのが新規ユーザーも心折れずに、それでいてチャレンジできるから良いと思うの
2022/07/03(日) 14:22:50.28ID:hxbvIGfm0
競技プログラミングって実際にはプログラミングというより
基礎学力、算数の力を問うようなものだろ

実際超有名進学校の生徒が多いし
2022/07/03(日) 14:29:42.99ID:Rs7jP0Dp0
>>437
そもそも競技プログラミング(計算機科学)は数学の一分野
439デフォルトの名無しさん (ｱｳｱｳｳｰ Sacf-pVYn)
垢版 |
2022/07/03(日) 14:58:10.18ID:1KIWm0Nxa
>>436
diff200くらいだろうと思ってb問題にした結果です
2022/07/03(日) 15:47:20.27ID:xNYzPTaMM
昨日のBは実際難しかったね
あまり競プロ界隈は読解力で差がつくということを認めない傾向があると思う(実際は高校生大学生レベルでもそこで差がつく層はかなり多い)
2022/07/03(日) 15:48:33.58ID:nkFK6+7OD
今回の問題ってどこでみられるの？
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況