競技プログラミング総合スレ 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/11/29(火) 20:59:15.21ID:lAj9RF5h0
誤った解答というのは「ST各行の・の数だけカウントして比較」の話ね
2022/11/29(火) 21:00:15.27ID:RxTn59Tk0
それが落ちるケースなかっただけでは
2022/11/29(火) 22:07:29.73ID:FB4pDqos0
テストケースが弱いことなんてしばしばあるし
2022/11/29(火) 23:04:14.45ID:VWoS6vwd0
マルチテストケースにしてNが小さいところは全部入れれば簡単にテスト強くなるけど
AtCoderはやらないよね
2022/11/30(水) 00:12:33.13ID:9qvj+6epa
>>635
転地しないと駄目なのはaftercontest 追加されてたけど
点の数だけで通るってマジ？
2022/11/30(水) 09:53:36.46ID:apN+BzVh0
いつも思うんだけど、そういう作問の不備らしき問題ってどこに通報すればいいの？
2022/11/30(水) 13:22:48.31ID:5wsyQllOr
ちょくだいにリプ爆しろ
2022/11/30(水) 14:34:30.64ID:apN+BzVh0
ブロックされそうでこわい
2022/11/30(水) 15:07:15.45ID:Pc+r2fg0a
マジでTwitterくらいしかないよね
外国の人かわいそう
2022/11/30(水) 17:02:31.77ID:aIG6S061a
解説と同じアルゴリズムだと通るのに愚直に解くとWAになることがあって悩んだことがある
TLEならともかくWAになるはずなかったんだがなあ
なにせ1000000007で割った余りを書きましょうという問題で全部BigDecimalで計算して最後に一度だけ割る解法だったし
2022/11/30(水) 18:55:40.36ID:o5YY8Hyda
へえそうなの
大変だったね
2022/11/30(水) 21:04:42.76ID:+1VZTiuO0
質問するならコードを貼れ
通らないならどっか間違ってんだろとしか言えん
2022/12/02(金) 14:05:45.12ID:u1vu+Orua
AIに問題文投げただけで正答のコード返してくれるようになったら競プロは終わるのか？
2022/12/02(金) 15:11:52.86ID:U3+Z10Mra
灰茶は完全に死んだね
2022/12/02(金) 20:08:44.19ID:Nb3LXSL90
クリスマスはAGC🤓
2022/12/03(土) 21:56:16.75ID:JyCxq0uSM
クリスマスにちなんだスペシャル問題が出るんだろうな。
2022/12/03(土) 22:40:01.18ID:Uhw018620
A:やるだけ
B:累積和をやりながら差をやるだけ
C:Sの先頭から見てTと違う文字が出てきたところが答えになるだけ。Sの末尾になんか$とかみたいな1文字を追加しておくと簡単
D:素因数分解して素数ごとに、Nが最低でいくつ以上になるかを二分探索によって求めるだけ
E:f(x)=1 + P/100 * f(x-2) + (100-P)/100 * f(x-1) みたいな計算をメモ化とかDPとかしてやるだけ
F:BFSして訪問するごとにどこからどこへ行けるのかUnionFind使ってマークし、コストをポテンシャルとして記録する。あとから違う値でポテンシャルを更新できる場合はUnionFindのその集合はinfになるとわかる。答えはUnionFindと、ポテンシャルの差を見るだけ
G:Fまで早解きすればパフォがカンストして2400になるから賞金どうでもいいなら解かなくていいので無視するだけ
Ex:無視するだけ
2022/12/03(土) 22:44:01.02ID:IWvgV3l70
Fで無駄にLCA持ち出して距離を求めようとしたせいで時間浪費したのマジで勿体無くて泣ける　
LCAの項が打ち消されるのに
2022/12/03(土) 22:45:54.74ID:kk6HaUaJ0
C簡単すぎてびびったわ(´・ω・｀)
Dは素数の問題だとわかったが何故かいつまてまでも数個ACせんかった(´・ω・｀)
2022/12/03(土) 22:46:49.20ID:VCZIA7Uqp
今回はFまでの早解き回だったね　自分もカンストしてみたかった
2022/12/03(土) 22:47:06.24ID:UdtoWZb20
22:40:00に正解しても得点入らないの
2022/12/03(土) 22:53:22.87ID:Uhw018620
重み付きUnionFindってなんだろう
しらんけど同じようなことをおれは実装してたのかな
2022/12/03(土) 22:53:50.52ID:ScHASUx3a
小数点以下が切り捨てられて表示されていて実際の提出時刻は22:40:00を僅かに過ぎていたのか
あるいはコンテストの開催期間は[21:00, 22:40)だったのか
660デフォルトの名無しさん (ｱｳｱｳｳｰ Sa3a-wvAz)
垢版 |
2022/12/04(日) 09:19:17.67ID:pM2FPSpOa
これってカンニングやり放題だと思うんだけど意味あるの？
昔は会場で受けてた？
661デフォルトの名無しさん (ｱｳｱｳｳｰ Sa3a-wvAz)
垢版 |
2022/12/04(日) 09:30:54.97ID:pM2FPSpOa
転職の武器になるかな？って思って調べるけどよくわからない
ここのスレ見てても転職できたという報告は全然ないね
募集枠はあるけど採用されないように見えるね
2022/12/04(日) 10:29:38.14ID:cWum1xSPa
>>660
賢い友人いればカンニングし放題だよ
2022/12/04(日) 10:47:16.13ID:byXjLF2m0
遊んでた結果副次的に転職出来たらラッキーくらいに思っておくのが賢明でそもそも転職目的で取り組むものじゃない定期
664デフォルトの名無しさん (ｱｳｱｳｳｰ Sa3a-wvAz)
垢版 |
2022/12/04(日) 12:28:16.09ID:pM2FPSpOa
そういう事ね、とりあえず遊びでやってみるか
2022/12/04(日) 14:23:01.52ID:NAhGf0YwM
ChatGPTが解けてるのはただ単に問題文覚えているからだと思うが、AGCの新問を解けるようになったら革命起きそうだな
2022/12/04(日) 14:23:58.59ID:c/97lm9K0
1万文字をcinで入力して、文字列長を調べたら4095と表示されてしまいました
何故でしょうか？(´；ω；｀)
2022/12/04(日) 14:45:43.34ID:QAdxD5oY0
だからコードを貼れと
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で書かせる
必要があるっぽいから普通に解いたほうがいい気がするな
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況