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

■ このスレッドは過去ログ倉庫に格納されています
1デフォルトの名無しさん (ﾗｸｯﾍﾟﾍﾟ MM7f-osoq)
垢版 |
2022/10/02(日) 17:43:58.66ID:FqAfPtIrM
↑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/12/04(日) 16:28:54.17ID:9++0/IB+0
途中に空白があって全部入力できてなかったとか
669デフォルトの名無しさん (ｱｳｱｳｳｰ Sa3a-wvAz)
垢版 |
2022/12/04(日) 17:53:44.19ID:pM2FPSpOa
昨日の問題EのcriticalHitがよくわからないんだけど
解説にatcoderのincludeファイルがあるんだけどなんだこれ？
PとQ求めたらこのファイル使うと勝手に計算してくれるの？
2022/12/04(日) 17:56:34.68ID:NAhGf0YwM
chokudai「あれ、AGCも典型じゃね？」
2022/12/04(日) 17:57:37.82ID:CGY/STbk0
それはAtcoder LibraryっていうAtCoderのジャッジで使えるライブラリなんだけど、初心者には明らかに説明不足だね・・・
672デフォルトの名無しさん (ｱｳｱｳｳｰ Sa3a-wvAz)
垢版 |
2022/12/04(日) 18:03:15.78ID:pM2FPSpOa
>>671
つまり、高速でPとQを解かせるのが本題で、
mod計算はライブラリがあるからそこで時間つかうなよ！って事かね？
使わないと困るケースがあるんだろうけど...理解せずに脳死で覚えた方が良いんかな？
2022/12/04(日) 18:04:20.29ID:NAhGf0YwM
この手のDPにACLの出番あるのかと思ってみたけど、modintか
2022/12/04(日) 18:06:53.79ID:NAhGf0YwM
>>672
別にACL使わなくても自分でスクラッチしてどうにかなるレベルだけど、負になったときの処理とかがめんどいから使った方が楽って感じのノリ
2022/12/04(日) 18:09:27.71ID:CGY/STbk0
そうだなあ
ACLで実装されてるのは有名アルゴリズムばかりで、ABCでもよく出題されるの多いからライブラリで実装されてるものは理解したほうがいい
ACLは使ってもいいし、使わなくてもいい

まあ、とりあえず問題が解ける程度には理解して使えるようになることをオススメしておくか
特にmodintは便利だと思う
ACLをローカルにインストールすれば、自分のパソコンからも使えるよ
2022/12/04(日) 18:12:21.58ID:CGY/STbk0
ちなみにおれはC++使ってないし、そういうライブラリは一通り自分で作ってる
2022/12/04(日) 18:14:00.78ID:NAhGf0YwM
休日でぼーっとしすぎて頭が痛い
何かしらウォームアップするか、逆に仮眠取るかしないとAGCやばい気がする
2022/12/04(日) 18:16:11.55ID:CGY/STbk0
>>677
休日の片頭痛は、だいたいカフェイン不足が原因だろうから、カフェイン摂っておけば治るというのが自説
2022/12/04(日) 18:24:50.23ID:NAhGf0YwM
モンスター爆飲みやなー
翌朝の予定とかもう関係ないね
2022/12/04(日) 20:00:57.71ID:9++0/IB+0
分数をmodで表現する方法が分からなくて解説見に来た人が何も分からないままだから、「modでの計算はたとえばACLを使うことで求めることができます」みたいな一文とともにACLドキュメントへのリンク欲しいね
そもそも新しく入ってきた人はACLの存在知らないだろうし
681デフォルトの名無しさん (ﾜｯﾁｮｲ 66e2-77kT)
垢版 |
2022/12/04(日) 20:09:31.79ID:EaAmvHmj0
小数点の既約分数表現だか、理解するモチベーションが全然わからない
2022/12/04(日) 20:18:03.95ID:YKYxvH3hp
分数のmod表現は最初は数字が非直観的で戸惑うかもしれないけど、やってることは全然難しくないからACL使用前提じゃなくて普通に理解すべき
逆元と繰り返し2乗法理解してれば一瞬で書けるし
683デフォルトの名無しさん (ﾜｯﾁｮｲ d9b1-WJTY)
垢版 |
2022/12/04(日) 20:40:00.50ID:c/97lm9K0
>>667
>>668

普通のコードです
std::stringでも同じ結果になったため、charにしてみました。
#include<iostream>
#include<string>
#include<string.h>

using namespace std;

int main()
{
char S[500009],T[500009]; // 変更前文字列、挿入後文字列
// 入力
cin >> S;
cin >> T;

// 変更後文字列の長さを求める
int len = strlen(T);
// 開始位置は先頭
int start = 0;
// 終了位置は文字列の最後
int end = len-1;

// 以下省略
return 0;

}
684デフォルトの名無しさん (ｱｳｱｳｳｰ Sa3a-wvAz)
垢版 |
2022/12/04(日) 20:48:19.58ID:pM2FPSpOa
>>683
intで足りてる？
685デフォルトの名無しさん (ﾜｯﾁｮｲ d9b1-WJTY)
垢版 |
2022/12/04(日) 20:50:00.93ID:c/97lm9K0
>>684
intって32ビットですよね？
でしたら足りてます
686デフォルトの名無しさん (ｱｳｱｳｳｰ Sa3a-wvAz)
垢版 |
2022/12/04(日) 20:53:07.80ID:pM2FPSpOa
足りてるなら言う事無いですね。
2022/12/04(日) 20:59:50.43ID:CGY/STbk0
>>683
ちゃんと10000って表示できるよ
https://ideone.com/cjnxWH#stdout

だからコードじゃなくて、コマンド操作の方法に問題があるんでしょ
688デフォルトの名無しさん (ﾜｯﾁｮｲ d9b1-WJTY)
垢版 |
2022/12/04(日) 21:06:26.43ID:c/97lm9K0
>>686
ありがとうございます

>>687
サクラエディタで１万文字を２行分書いて、それをCtrl＋Aでコピーして
VSCodeに右クリックでペーストしました
この作業で文字がカットされている可能性がありますね
ありがとうございます！！
689デフォルトの名無しさん (ｱｳｱｳｳｰ Sa3a-wvAz)
垢版 |
2022/12/04(日) 21:07:30.39ID:pM2FPSpOa
入力文字列が怪しそう
2022/12/04(日) 22:09:18.30ID:dd1ttyO10
期待値の問題ってワンパターン過ぎじゃ、、？
単に水色だとこんなもんで青黄の期待値問題はもっと複雑なの？
2022/12/05(月) 00:16:09.04ID:9VPmC7c9M
今回BよりAの方がずっと発想ゲーに感じた
2022/12/05(月) 00:29:08.62ID:dZQIdR+h0
同じ二完でも遅いと全然パフォ伸びないな
絶妙な解きにくさで、ああAGCだなと思った
2022/12/05(月) 00:35:10.61ID:9VPmC7c9M
>>690
そもそも水diffのDPは丁度EDPCで見るようなレベルだから、実際パターン少ない
もちろん上のdiffで典型度低くて難しい期待値問題はたくさんある
2022/12/05(月) 00:41:25.45ID:dZQIdR+h0
Aみたいなのは発想でどうにかするより逆順で実験する方が安定するよ
2022/12/05(月) 01:08:41.64ID:FvIGflqWr
期待値という概念の扱いに慣れてない低学歴が引っかかるから簡単でもdiffは上がる
2022/12/05(月) 01:09:31.17ID:gVdVhqi2p
青上位　青上位　赤　銅　銀　AC0
は草　
もうレーティング対象青からでも良いんじゃないか
2022/12/05(月) 01:26:14.28ID:wV6tNweHa
atcoder jumperは下回ったな
A問題最高diffはならず
2022/12/05(月) 01:29:24.67ID:ypvg8sem0
配点からしてAがむずかしめなのは予想できたし、まあ

水色くらいの人たちならそんぐらい自己判断できるし、まあ水色以上Ratedで良いと思うけどね
それよりARCを3200くらいまでRatedにしてあげたら？って気がしちゃう
2022/12/05(月) 03:02:28.71ID:OFDKazG70
操作を繰り返して全て同じにしたいときに隣接要素が異なる箇所の個数の変化を考えるのは典型な気がする

Bが重くてつらかった
2022/12/05(月) 10:20:45.99ID:DqBKeem4M
それは考えたけどほぼ常に2個ずつ減らせるとはわからんかった
2022/12/05(月) 10:44:48.54ID:pY2jkv26p
下界/上界が必ず達成できる典型という奴だな
自分はABCABC型が3回で揃えられることすら見逃してたせいで詰んでた
2022/12/05(月) 11:48:54.61ID:9VPmC7c9M
異なる文字同士が隣接している部分の特徴量として使おうってのはまあすぐ思いつくしそれはそこまでの発想じゃないと思うが、ABCABC三回とかがコンテスト中だと意外とソラで気付けない
そうこうしてるうちに別の方針に飛んだりしてかなり時間食う
一方Bは下界と上界がすぐ見えるし、700点問題にしては木となもりの関係性と似ていることに思い至るまでにそんなに飛躍はないように思う
実装パートの方がつらい
その結果が正答数逆転だわ
2022/12/05(月) 11:49:40.54ID:9VPmC7c9M
>>702
☓部分の
○部分の数を
2022/12/05(月) 12:49:21.04ID:xHOM0phNM
わかるわ
B発想の割に普通に実装が重い
時間経過でどんどんAC数増えるのも納得
2022/12/05(月) 13:44:54.25ID:6+3fZaFZp
愚直コードを書いてパソコンに実験させるのが良かったんだろうけど、これくらいの問題なら紙に書いて実験するので大丈夫だろうと高をくくって最小回数を勘違いしてたせいで一生WAが出て地獄だった
パソコンに実験させる習慣が未だにつかない
2022/12/05(月) 17:25:12.72ID:dZQIdR+h0
自分もどちらかというと移動中の微妙なスキマ時間に競プロの問題を考えることが多いから、実験はそんなに得意ではないかなあ
高難易度ほど予想解きスキルが必要そうだから、ARC/AGCで戦うのなら練習した方がいいかもね
707デフォルトの名無しさん (ﾜｯﾁｮｲ 66e2-77kT)
垢版 |
2022/12/05(月) 19:41:46.19ID:MF+Ck4c20
AGC、診断人氏が0完とか、もう一般的にかなり優秀な人ですら出れるレベルじゃないのかｗ
2022/12/05(月) 19:52:29.46ID:ypvg8sem0
水色の底辺なら0完でも温まってるから、逆にレート低いほど出るべき
2022/12/05(月) 20:16:56.33ID:F8Lb9jYBp
昨日みたいな簡単な問題が無い回だと本書いてる人や赤コーダーみたいな高レベルの人でも0完しちゃうことあるんだなってびっくりした
2022/12/05(月) 22:13:27.51ID:dZQIdR+h0
AもBも感覚だと普段のABC-Gより難しかったから、0完でも凹まなくていいと思うよ
2022/12/06(火) 00:38:56.11ID:2yqxdiTAM
赤の0完は流石に戦略やろ
一定時間かけてダメだったら後ろに賭けるしかない
まあ赤でも瞬殺できるわけではない問題だったのは確かだが
2022/12/07(水) 18:26:11.90ID:+RxBvimqM
赤からすると、終了30分前にA問題解いたとて、って感じだろうからな
最後のギリギリまでC以降に賭けた方がいい
2022/12/07(水) 20:38:58.44ID:KlMxIGrW0
競プロスレおやすみ～😪今日は少し精進した
2022/12/07(水) 22:37:11.32ID:fRJGzVLy0
プログラマー板のスレはもうめちゃくちゃだね
2022/12/07(水) 22:42:32.97ID:K0BDAES80
見に行ったけどなんかすごいことになってた
2022/12/07(水) 22:50:56.68ID:K0BDAES80
0完で水パフォってところから、AGCのrated制限ってかなり絶妙に設定されてると思ったね
年6開催のころに仮に同じ難易度、all ratedだったら、参加し続けることで一年すべて0完でも緑ぐらいには行きそう
2022/12/07(水) 23:03:19.10ID:mi/jvoGH0
良い子はあんなスレ見に行っちゃいけません
2022/12/07(水) 23:22:27.97ID:K0BDAES80
そういえば、この前のAGC-A、最初解法ガチャでMoじゃないか？とか考えたんだけど、それでもできるのかな
2022/12/07(水) 23:27:50.37ID:0gV/yTHUp
MoチラついたけどA問題でMoが想定解なわけないしな……って思ってすぐ却下しちゃった
テストケース次第では間に合うのかな
2022/12/07(水) 23:34:14.34ID:+RxBvimqM
想定解を知ったあとだとMoでACできる遷移はすぐ作れる気がするが、それって本質的にMoのおかげで解けたことにはならないんだよな
てかその遷移に思い至るんならMo使わんやろっていう
2022/12/07(水) 23:35:50.85ID:+RxBvimqM
メタ的にもAGCのAでMoはないだろうし
2022/12/08(木) 00:19:44.81ID:qo7J5oAL0
昔直大が998244353なら使えるアルゴリズムが1000000007で使えないことがあるのでメタ読み対策で998244353使う的なこと言ってた覚えあるけど具体的に何があるの？
998244353使ってる問題解いてて気になった
723デフォルトの名無しさん (ﾜｯﾁｮｲ d910-RX5i)
垢版 |
2022/12/08(木) 00:20:24.69ID:qo7J5oAL0
>>950

!extend:checked:vvvvv:1000:512
!extend:checked:vvvvv:1000:512

テンプレからコマンド消えてるのでテンプレに追加してください
2022/12/08(木) 00:33:13.01ID:TyHoBXE/0
>>722
ACLにもなってるこの畳み込みは 10⁹+7 だとあまり使い物にならない
このアルゴリズムを使うときはほぼ確実に998244353が指定される
https://atcoder.github.io/ac-library/production/document_ja/convolution.html
2022/12/08(木) 00:34:54.52ID:QbzOT+5k0
>>722
畳み込み演算を高速化するFFTの亜種で、数論変換というのがある
普通のFFTは複素数を使うけど、数論変換はずっとmod pで計算するから精度上の問題が生じないのがメリット
p-1 = 2^m * dみたいな形で書いたときにmが大きいpほど扱いやすく、998244353は大きくて、1000000007は小さいから、そこで数論変換を使うかどうかがバレやすい的な話
2022/12/08(木) 00:38:01.86ID:QbzOT+5k0
>>719
やっぱ一回は思い浮かぶよね
そんなに単純な解だと思わなかったし
2022/12/08(木) 05:37:05.87ID:JblDKfrH0
そもそも1クエリ固定の場合を解けないと話にならなくて、セグ木やらMoやらを考えるのはそのあとでないか
2022/12/08(木) 10:57:49.64ID:DNmDkQyIM
解既知区間を左右に1伸長したときにまた高速で解を求められれば一クエリでも多クエリでも対応できるから、そこに絞ってまず思考してみるというのも戦術としてはあるだろ
帰納的に考える方が多くの場合少ない思考リソースで問題解けたりするし
2022/12/08(木) 12:32:11.43ID:JblDKfrH0
言ってることようわからんが結局1クエリ解くことから始めてない？
2022/12/08(木) 13:06:21.88ID:bAy1n42uM
その1クエリを解くにあたり、Moで多クエリでも高速で処理することを見据えて、1クエリの解を伸長で構成することを試してみるって話
一方、セグ木で解くことを見据えるなら、モノイド性をどこかで見出して区間を併合しながら1クエリの解を構成できないか考えてみるというアプローチになる
メタ的には、多クエリで高速で解ける以上は、1クエリの解き方も限定されてくるだろうって考え方だな
別に数学的知見じゃなくて、ただの問題解く手順のお気持ちみたいなもんだから、わからないんならわからんでいいよ
2022/12/08(木) 13:14:19.81ID:bAy1n42uM
前回のAも、「多クエリを高速で処理できるんだから簡単な区間の特徴で1クエリ分解けるだろう（そもそもAGC-Aだし）」で想定解に至った人も割といるんじゃないか思っているが、発想的にはそれと似たようなものだと思うわ
2022/12/08(木) 14:18:33.85ID:sJ8eTx33a
区間の伸長が高速にできるなら、解が自明な長さ0や1の区間から始めるだけでは
2022/12/08(木) 14:28:51.79ID:QbzOT+5k0
自分がMoを考えたと言ったのは、1クエリ解くにしてもDPみたいに漸化式作れたらやりやすそうだからと思ったからかな
もちろん最初のクエリの答えは自明な区間から出発するよ
2022/12/08(木) 16:31:38.77ID:qo7J5oAL0
なおだいブログ曰くchatGPT使っていいらしいな
Cまでしか解けないしなんか問題文を変換しなきゃいけないらしいから茶以上だと意味ないけど
2022/12/08(木) 16:37:54.78ID:tY+Rj1vk0
適当に自動化してA、B、CをChatGPTに瞬殺してもらって良いってことなの？
2022/12/08(木) 16:46:31.91ID:tY+Rj1vk0
3問目まで自動で解いてくれるなら5分ぐらいは節約できるし多少はパフォ上がるかな
737デフォルトの名無しさん (ﾜｯﾁｮｲ d910-fj/B)
垢版 |
2022/12/08(木) 17:27:26.68ID:qo7J5oAL0
twitterから拾ってきたやつだけど
・英語版の問題文を与える
・数式等をTeXで書く(A_i, 10^2など)
・入力と出力の例を与える
・AtCoderの問題であることを教える
・Pythonで書かせる
必要があるっぽいから普通に解いたほうがいい気がするな
2022/12/08(木) 17:31:25.35ID:tAYudyq3a
まだ発展途上とは言えイラストAIもあっちゅう間だったしな。
もう俺みたいな底辺は解く楽しさしか残らねーわ。
2022/12/08(木) 17:49:40.32ID:bAy1n42uM
>>737
TeXへの変換規則さえちゃんと考えてコーディングしておけば、後は自動化できそうな感じもするな
2022/12/08(木) 17:54:32.49ID:bAy1n42uM
これからはAIをうまく使う力が重要なのであれば、練習としてそういう解き方を研究するのもありだと思ってるわ
2022/12/08(木) 18:06:46.91ID:05iO3Ijva
それってデータエンジニアじゃん！
Kaggleじゃん！
2022/12/08(木) 18:15:38.61ID:qvBkrjzGp
kaggle定期的にやりたくなるけど競プロ諸々との両立が難しくて毎回挫折する
2022/12/08(木) 22:15:49.90ID:LtNnKYdG0
健常者スレおやすみ🥱
2022/12/09(金) 07:42:08.88ID:NQJZdVld0
健常者スレおはよう🥱寒いね
2022/12/09(金) 15:37:29.25ID:JIsCFDDpM
Kaggleって機械学習モデルの精度競争的なイメージが強いけど、AIツールを活用した作業効率化みたいなイメージで話してた
2022/12/10(土) 12:50:59.26ID:FEPL+5PW0
健常者スレおはよう🥱今日はABCだね
2022/12/10(土) 16:56:35.59ID:+Gv2eYfg0
ChatGPTをAtCoderのコンテストで使用することが認められるならコンテスト出ないって人を見かけたけど、いまはまだ茶色程度の実力だけど、
仮に暖色程度の実力を備えた競プロAIが登場したとして、AtCoder公式から使用を認められたら、どう反応する人が多いか気になる
2022/12/10(土) 20:31:32.99ID:Ns16Znepd
まだ未参加なのですが過去問ABCのABまでしか解けないとして参加する意味ありますか？
あとABだけ解けて茶色行けますか？
2022/12/10(土) 20:44:33.79ID:TTumudvvd
コンテストになれば普段より集中して問題に取り組めるので参加する意味はあります
また参加回数が少ないとレーティングに補正がかかって低くなる仕組みもあります
ABだけでは茶色にはなれません
2022/12/10(土) 20:45:06.16ID:9Qn6ryF90
>>748
英検とかと違って無料で参加できる実戦だから、練習になるし意味あるよ
強いひとはAtCoder以外にもいろんなコンテストに毎週たくさん参加してたりするよ

ABだけで茶色は無理かな
茶色にいくならCまで余裕もって解いてくださいな
2022/12/10(土) 20:49:39.55ID:uF1Xgf00a
>>747
https://www.businessinsider.jp/post-263042

この前こんな記事読んだんだけど、やっぱりChatGPTは「考えて答えている」んじゃなくて「それっぽい文字列を吐いているだけ」みたいだから、これからよほどのパラダイムシフトがない限り暖色程度の実力を備えた競プロAIは無理じゃないかな
まあそのパラダイムシフトに立ち会ってみたい気もするけど

>>748
本番の時間制限あるなかで考えるのも楽しいし、やってみればいいと思うよ
2022/12/10(土) 20:59:17.91ID:Ns16Znepd
>>749-750
ありがとうございます
練習で参加してみます
2022/12/10(土) 22:40:05.14ID:Ns16Znepd
ABしか練習してなかったけどCまで解けて、
DはWAが少し出て時間切れでした残念。
でも緊張感あって楽しかったです。
2022/12/10(土) 22:43:34.37ID:6Z0a3kvJ0
今日は時間内に6完
2022/12/10(土) 22:49:32.73ID:tlhyP2tP0
普通にE、Fの実装重かったね
756デフォルトの名無しさん (ﾜｯﾁｮｲ bfe2-6Z9O)
垢版 |
2022/12/10(土) 22:51:50.49ID:O4kKtbHo0
D難しくなりすぎ・・・・。もらう方でやってバク取れず。２重dpでうまくいかない事に気づくまで40分。
2022/12/10(土) 22:56:44.55ID:q492UgBQ0
寝てたら終わってた草
2022/12/10(土) 23:04:25.58ID:Ns16Znepd
D解けた人の境界見たら、1245位だったのでかなり難解だったんですね。
ダメ元でサンプル通ったから提出したら当然WAでしたが解説見てもさっぱりでした。
少しずつアルゴリズムというものを勉強したいと思います。
759デフォルトの名無しさん (ﾜｯﾁｮｲ 4799-70Cd)
垢版 |
2022/12/10(土) 23:04:45.70ID:WdAZ/8IS0
editor使わず糞アットコの糞サイトbuiltin editorだけで書いてみた
やっぱり全然だめだな(´・ω・｀)
2022/12/10(土) 23:11:10.88ID:tlhyP2tP0
総和が○○のときの△△を求めよ、みたいな形はナップサックDPであることが多いね
761デフォルトの名無しさん (ﾜｯﾁｮｲ bfe2-6Z9O)
垢版 |
2022/12/11(日) 00:16:52.91ID:sLVycVhX0
同じ問題のレートが１年で50下がってるんだから、Dは茶色下くらいを目指そう
762デフォルトの名無しさん (ﾜｯﾁｮｲ 5fbd-FFNn)
垢版 |
2022/12/11(日) 01:07:10.13ID:Jt/PvfWs0
よかった
俺の調子が悪かったわけじゃないのか

三重ループまでなんとなくわかってたけど実装が複雑になりそうでできなかった
2022/12/11(日) 02:02:20.83ID:pBXkhdRDM
Ex見てるがやっぱり分割統治FFTいつまで経っても慣れんな
764デフォルトの名無しさん (ﾜｯﾁｮｲ a701-u86g)
垢版 |
2022/12/11(日) 02:54:41.11ID:7rOr8/1H0
愛知ループは三重の三倍難しいと言われてるからな。。
2022/12/11(日) 08:11:02.37ID:7I6zjj+w0
DPや二次元配列などでarray型の生配列を使う例が多いのは慣習的なものですか？
処理が速いとか利点があるのでしょうか？
2022/12/11(日) 08:55:06.62ID:Mvtwu1hIa
arrayより楽な選択肢なんかある？
arrayじゃダメなときは当然そっち使うにしても
2022/12/11(日) 09:07:28.08ID:6A4ez8rK0
青安定のために参戦を決めていたのですがぐっすり寝てしまい出れなかったであります🤓
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況