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

2022/12/26(月) 12:47:37.63

!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/

※前スレ
競技プログラミング総合スレ 64
https://mevius.5ch.net/test/read.cgi/tech/1664700238/

VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured

2023/03/19(日) 22:46:49.93

Gはかなり既出感の強い問題だからね
vaidation用の問題みたい

2023/03/19(日) 22:47:42.92

Ex、指数時間アルゴリズムのスライドに何か載ってないか探しに行ったけど、特に収穫はなく

2023/03/19(日) 22:55:37.60

Fは例の食塩水の問題が結構印象に残ってたからすぐ方針に辿り着けたけどABCだとやっぱりほぼ既出問題ばかりになるから精進が大切だな

2023/03/19(日) 23:29:06.01

Eでバグりまくって見てなかったFやったら5分で解けた…

2023/03/20(月) 00:08:10.86

Eバクりまくって4完。カス

2023/03/20(月) 00:29:14.29

multisetを使うDがレート380とか信じられないんだけど・・・

2023/03/20(月) 00:32:44.72

>>885
multiset使わなくても解けるよ
ACしたほとんどの人使ってないんじゃない？

2023/03/20(月) 01:55:57.10

Eまでほぼ愚直に実装する問題だったのはだいぶ珍しい気がする
Eみたいな問題はバグが怖いからあまり好きじゃないけど

2023/03/20(月) 02:28:36.69

WA出しまくりの6完ですわあ...(´・ω・`)クエリ処理で前も同じミスしたのよね

2023/03/20(月) 12:46:23.78

もともと寒色になんの価値も無いのでGPT使われようがなんの問題もないね

2023/03/20(月) 16:04:08.72

GPT4で5完水パフォか
これは使ってる人が水だからあんま意味ないけど
茶ぐらいの人が使ってもパフォ上がるんだろうか

2023/03/20(月) 16:08:18.71

https://qiita.com/autotaker1984/items/2929937cd1fea6137d1f
AtCoder終了のお知らせ
前回は質問を工夫して何度かやり取りと手直ししたら3.5でも一時間で7完だったからお前らよりよほど優秀

2023/03/20(月) 16:11:40.54

ガイジスレのみんなもこっちにおいで

2023/03/20(月) 16:17:14.20

優先度付きキューとか今日日灰色でも標準装備だろうし余裕でAIに指示出せるな
AtCoder崩壊近しなのか？(´・ω・`)

2023/03/20(月) 16:19:36.96

寒色diff程度の簡単めな問題なら解法分かってる状態で質問繰り返してしかも手直しまでしたら解けるに決まってるんだよな
解法が分かってない状態でも自分よりも高いパフォが出せるようになるかが問題

2023/03/20(月) 16:20:39.56

GCJとTCOが終わったり、ABCで大半のユーザがAIに負けるようになってもまだみんながんばってね

2023/03/20(月) 16:21:44.91

灰とか茶の人が実際に使ってみたレポートが欲しいんだけど、自分がガチでやるより良い成績が出る可能性があるとなるとなかなか使いたくないのかな

2023/03/20(月) 16:36:48.13

ARCのA問題も解けるのかな

2023/03/20(月) 16:38:45.12

AGCのA安定して解けるようになったらヤバいけど考察不得意そうだからまだ大丈夫そう
ABCのド典型問はどんどん解かれそうだけど

2023/03/20(月) 17:04:45.56

GPT4もそのうちAPI公開されるし
誰かが完全自動化ツール作って放流したら終了だね

2023/03/20(月) 17:26:39.70

逆に機能のGなんかは一発で解けてもおかしくない気がするけど、意外とまだ典型習熟度高くないね

2023/03/20(月) 19:49:00.37

>>894
なんで解けるに決まってんだよw
問題読ませただけで「ここではMoのアルゴリズムが使えます」とか「答えを固定して二分探索します」なんて言うAI他にあるか？

2023/03/20(月) 20:03:11.57

>>901
そうだから質問を繰り返してAIを導く必要があって、導き方を既に知ってるなら最早AIじゃなくて人間が解いてるのと変わらないのではって話をしてるんだけどどういうツッコミ？

2023/03/20(月) 20:05:57.80

>>902
日本語読めないのか？
AIが問題解決に最適なアルゴリズムを提案してんだよ
人間じゃなくてだな

2023/03/20(月) 20:13:25.50

>>903
上の方で貼られた記事のE問題までの話をしてんのね
社長のchatGPT縛り配信の話かと思った

2023/03/20(月) 20:17:33.98

>>904
何を言ってるんだ
7完達成しやがったという話を先週ここに書いたんだよ
今週5完の記事が出たから蒸し返した

2023/03/20(月) 20:19:39.32

蒸し返したらそんなの当たり前とか言うトンチキが出てきたから呆れてるとこだ
当たり前のわけねえだろ

2023/03/20(月) 20:27:08.93

>>906
当たり前っていうのはAIを適切な解き方に誘導したらそれに沿って解いてくれるのは当たり前って話をしていたつもりだった(3.5の時はこうしないと簡単な問題以外は解けなかった)

chatGPTがバージョン4になった今どういう風に解いてくれるのかは把握してないし先週のABCで7完したという話も初耳

2023/03/20(月) 20:44:01.94

Moのアルゴリズム提案してくれたやつは問題を読ませた“だけ“ではなくて質問である程度誘導してたとは思う
（もちろんそれで提案してくれるのはめちゃくちゃ凄いが）

2023/03/20(月) 20:46:48.04

>>907
まだ誘導とか言ってるのか
100回読むか小学校からやり直せよ

2023/03/20(月) 20:58:26.01

すまん、GPT4より弱いやつおる？w

2023/03/20(月) 21:06:12.87

レスバしたいだけのｱｳｱｳｳｰの人、結構みっともないからやめた方がいいよ

2023/03/20(月) 21:21:05.85

ほんと、そういうくだらないのはツイッターでやれよな

2023/03/20(月) 22:00:28.84

お前いつも論破されてそれだな

2023/03/20(月) 22:45:45.31

すまん
初心者なんだがIQが低すぎてこの問題が解けない
一つだけクリア出来ないテストケースがあるみたい

N以下の自然数でXの倍数またはYの倍数であるものはいくつあるか？

入力
N X Y
制約
1≦N≦10^6
1≦X＜Y≦10^6

コード

#include<bits/stdc++.h>
using namespace std;

int main() {
long long n,x,y;
cin>>n>>x>>y;
if(y%x==0) cout<<n/x<<endl;
else cout<<n/x+n/y-n/(x*y)<<endl;
}

2023/03/20(月) 22:46:24.96

誰かどの辺が間違ってるか教えて
なんでACできないんだろ

2023/03/20(月) 22:49:06.83

お願いします

2023/03/20(月) 22:50:00.28

For文書いたら出来たけどなんか釈然としないよね

2023/03/20(月) 22:52:12.36

ヒント：最小公倍数

2023/03/20(月) 22:54:12.33

最後x*yじゃなくlcmでどうや？

2023/03/20(月) 22:55:07.63

総当たりして誤るテストケースを自分で見つけるスキルを身につけることも重要

2023/03/20(月) 22:56:59.35

ありがとうございます
たしかに、最小公倍数でいいですね
IQがゴミすぎるんで競プロ止めます

2023/03/20(月) 22:57:42.29

止める→辞める

2023/03/20(月) 22:58:49.74

止めるでいいか

2023/03/20(月) 23:52:08.09

コドフォ…

2023/03/20(月) 23:53:18.04

コンテスト開始前に突如延期は酷いやサーバーの問題だから仕方ないけど

2023/03/21(火) 01:06:39.53

おそらくGTPにヒューリスティックを除くatcoder的なスキルはほとんど使われていない、使われてるのはニューラルネット、内積、最適化、強化学習など。何故か整数ばかりのパズル最適化は見当違いも良い所。
競プロは役に立たない。

2023/03/21(火) 01:20:29.80

役に立つと思ってやるもんじゃないって既に無限回言われてるだろ何を今更

2023/03/21(火) 10:22:30.40

AtCoderJobsのランクがほぼ無意味になるな

2023/03/21(火) 11:38:58.42

何も変わってないじゃん

2023/03/21(火) 12:36:35.41

>>926
> ニューラルネット、内積、最適化、強化学習

この並列笑えるな、内積はセンスある

2023/03/21(火) 13:35:42.22

競プロ以前に高校数学すらまともに勉強してなかったんだろうな
AI開発に全く従事してないような奴の妄言

2023/03/21(火) 13:55:08.65

>>930
トランスフォーマーの核なので強調してみたのじゃｗ

>>931
DSだけどどう温かい目で見てもABCの問題の大半は役に立たない。ガチ。

2023/03/21(火) 13:59:58.54

お前がディープステートだったのか
ついに正体を表したな

2023/03/21(火) 14:35:19.64

内積でqueryとkeyのある種の類似度を計算して重みとして利用するのはそうなんだけど、まず磨くようなスキルではないのではないかという
離散最適化が主なのはそうだけど、実質的には連続緩和して解くような問題もままあるので、連続最適化をしてないとも言えないし

2023/03/21(火) 15:06:25.17

Winnyの金子ですね判ります

2023/03/21(火) 17:35:53.57

問題
N 枚のカードが横一列に並べられています。左からi 番目のカードには整数Aiが書かれています。
カードの中からいくつかを選んで、合計がちょうどS となるようにする方法はありますか。
制約
1≦N≦60
1≦Ai,S≦10000
入力は全て整数
入力
N S
A1…AN

2023/03/21(火) 17:44:43.69

質問です
これって動的計画法を使う問題ですよね
dp[i][j]をiまでのカードのなかで合計がjとなるようなカードの組み合わせが存在するかと考えても上手くいかないです
ほとんどのテストケースではACが取れるので全く検討違いというわけではないと思うのですが、有識者の目から見て間違ってる部分はありますか？
#include<bits/stdc++.h>
using namespace std;

using ll = long long ;
using bl = bool ;

#define Rep(i,a,b) for(ll i=a;i<=b;i++)

int main() {
ll n,s,A[69];
bl dp[69][10009];
cin>>n>>s;
Rep(i,1,n) cin>>A[i];
dp[0][0]=true;
Rep(i,1,s){
dp[0][i]=false;
}
Rep(i,1,n){
Rep(j,0,s){
if(dp[i-1][j]==true) dp[i][j]=true;
elif(dp[i-1][j-A[i]]==true) dp[i][j]=true;
else dp[i][j]=false;
}
}
if(dp[n][s]==true) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}

2023/03/21(火) 17:46:15.85

自分でテストケースを作成して色々とやって見たのですが上手くいかないです

2023/03/21(火) 17:49:03.50

>>937
全然ちゃんと確認してないんだけどj-A[i]で範囲外参照してそう

環境にもよるけど、　#define _GLIBCXX_DEBUG を入れると範囲外参照関連のデバッグはしてくれるから便利だよ(実行時間が遅くなる場合もあるから提出する時は外れるようにすると良い)

まあこういう遷移はめちゃくちゃ良くあるし慣れたらデバッグしないでも殆どミスらなくなると思う

2023/03/21(火) 17:54:56.33

>>937
elifが間違ってる

2023/03/21(火) 17:59:28.32

>>939
ありがとうございます。
Ai＞jであるときとそうでないときで場合分けしたら上手く出来ました。

2023/03/21(火) 18:01:08.70

>>940
ありがとうございます
elifの部分もまちがえていましたか

2023/03/21(火) 18:04:55.14

配列外参照の仕様に関してはまだちゃんと理解していませんが、939のレスをヒントにして解決することが出来ました。

2023/03/21(火) 18:06:38.67

j-A[i] < 0 にならない？

2023/03/21(火) 18:07:25.41

寝てたら解決しとる

2023/03/22(水) 14:54:15.97

質問
N個の正整数の最小公倍数を求める問題で分からない部分がありました。

コード1ではACが取れなかったのですが、コード2に変えてみたところACを取ることが出来ました。
数学的にはコード1もコード2も違いがないと思うのですが、何がいけなかったのでしょう。
頭を捻っても全く分かりません。

2023/03/22(水) 14:54:42.44

コード1
#include<bits/stdc++.h>
using namespace std;

ll Gcd(ll a,ll b){
while(a>=1 && b>=1){
if(a>b) a=a%b;
else b=b%a;
}
if(a!=0) return a;
return b;
}
int main() {
ll n,A[100009],g,l;
cin>>n;
Rep(i,1,n) cin>>A[i];
l=A[1];
Rep(i,2,n){
g=Gcd(l,A[i]);
l=(l*A[i])/g; ←変えたところ
}
cout<<l<<endl;
}

2023/03/22(水) 14:55:09.27

コード2
#include<bits/stdc++.h>
using namespace std;

ll Gcd(ll a,ll b){
while(a>=1 && b>=1){
if(a>b) a=a%b;
else b=b%a;
}
if(a!=0) return a;
return b;
}
int main() {
ll n,A[100009],g,l;
cin>>n;
Rep(i,1,n) cin>>A[i];
l=A[1];
Rep(i,2,n){
g=Gcd(l,A[i]);
l=(l/g)*A[i]; ←変えたところ
}
cout<<l<<endl;
}

2023/03/22(水) 14:56:01.64

行数制限のためテンプレートは省いております。

2023/03/22(水) 15:11:18.73

多分問題文の省略したところに原因が書いてある

2023/03/22(水) 15:20:25.39

次スレ

競技プログラミング総合スレ 66
https://mevius.5ch.net/test/read.cgi/tech/1679465982/

2023/03/22(水) 15:52:00.88

l*A[i]がlong longの最大値を超えてオーバーフローするのでは

2023/03/22(水) 15:58:55.16

今度からChatGPTに聞けよ
質問丸々手直しせずコピペして聞いたらこんなふうに答えたぞ

コード1とコード2は、最小公倍数を求めるアルゴリズムとしては等価です。しかし、2つのコードは演算の順序が異なります。

コード1では、(l*A[i])/g という式を用いて最小公倍数を更新しています。これは、 l と A[i] の積を g で割った商を最小公倍数としていることを意味します。

一方、コード2では、 (l/g)*A[i] という式を用いて最小公倍数を更新しています。これは、l と A[i] の積を g で割った余りを最小公倍数に加えたものとしています。この操作により、 l と A[i] の積が l と A[i] の最小公倍数になるように調整されています。

なぜコード2がコード1よりも正確であるかは、データ型の問題に関係しています。コード1では、(l*A[i])/g という式を用いることで、最小公倍数が ll 型で表現可能な範囲を超えてしまう可能性があります。一方、コード2では、 (l/g)*A[i] という式を用いることで、最小公倍数が ll 型で表現可能な範囲内に収まるようになっています。つまり、コード2は、最小公倍数が大きな値になる場合でも正確に計算できるようになっているということです。

以上のような理由から、コード2がより優れた実装方法と言えます。

2023/03/22(水) 16:10:47.83

別に元々質問が多くて困っているようなスレではないし、ここで聞く分には構わないと思うけど、ChatGPTの性能すごいね
ただ、誤ったことも自信満々に言うから、まだまだ初学者向けのサービスではないと思う

2023/03/22(水) 16:14:44.26

ここで聞いたら「省略したところに原因が書いてある」と言うやつがいるから書いたんだよ
原因は書いてないな
書いてあるのは制約だ

2023/03/22(水) 16:18:21.55

制約が原因やん

2023/03/22(水) 16:23:05.26

ちなみにbingで「N個の正整数の最小公倍数を求める問題はAtCoderのどれ？」と聞いて返ってきたのが次の返事

AtCoderの「数学とアルゴリズム」コンテストにある「017 - Least Common Multiple of N Integers」¹が、N個の正の整数A_1, A_2, ..., A_Nの最小公倍数を求める問題です。制約は、2 ≤ N ≤ 10^5, 2 ≤ A_i ≤ 10^18で、問題の答えは10^18以下です。¹

この問題は、AtCoderの「数学とアルゴリズム」コンテストにあるもので、N個の正の整数A_1, A_2, ..., A_Nの最小公倍数を求める問題です。¹¹:[AtCoder](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_q)

ソース: Bing との会話 2023/3/22(1) 017 - Least Common Multiple of N Integers. https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_q アクセス日時 2023/3/22.
(2) AtCoder 版！マスター・オブ・整数 (素因数分解編) - Qiita. https://qiita.com/drken/items/a14e9af0ca2d857dad23 アクセス日時 2023/3/22.
(3) AtCoder 版！マスター・オブ・整数 (最大公約数編) - Qiita. https://qiita.com/drken/items/0c88a37eec520f82b788

2023/03/22(水) 16:23:49.71

>>956
制約は原因じゃないぞ
むしろ制約があるためllに収まるから真逆だ

2023/03/22(水) 16:31:30.64

口論したいわけじゃないんだが
制約が原因という表現で別に間違ってないやろ

2023/03/22(水) 17:23:43.33

>>952
>>953
ありがとうございます
理解出来ました
次からはchatgtpに質問して解決できなかったらここで質問します

2023/03/22(水) 17:34:10.54

>>959
間違ってる
電車が来てる時に線路内に入ってはいけないという制約があるとする
それを見ずアホが線路内に入って死んだとする
そいつが死んだ原因は制約か？
違うだろ

この質問の場合も制約があるから間違ったんじゃなく、制約がなくても間違ったんだぞ
10^9までの自然数という制約が無かった場合は条件分岐が必要になるがあるためにそれはしなくていい
制約は問題を簡単にしてるだけで難しくはしてない

2023/03/22(水) 17:39:14.74

その議論はいったいなんの意味があるの

2023/03/22(水) 17:46:21.59

制約次第では上のコードでもあってるんだから制約が原因だろ
まあほんとに意味のないやり取りなんでこれ以上は相手しないが

2023/03/22(水) 17:59:23.68

日本語わかんないやつはChatGPTより下だぞ
議論じゃなくお前の間違いを教えてやってんだから口答えすんな

2023/03/22(水) 18:07:59.02

ChatGPTはお前らより賢いから正しく言葉を理解して正しく答えたぞw

成約を見ないことで不正解になった場合、それは成約が原因と言える？

制約を無視してしまったことによって誤った結果が生じた場合、それは制約ではなく主にあなた自身が原因です。制約は、現実的な制限を示すものであり、それらを考慮しないことは、問題を引き起こす可能性があるためです。ただし、制約が明確でなく、十分に説明されていなかった場合は、誤解が生じる可能性があります。その場合、制約を理解しようと努力する必要があります。結局のところ、誤りを修正するためには、問題を引き起こす可能性のある要因を正確に特定し、それを修正する必要があります。

2023/03/22(水) 18:18:52.57

こっちは自分のことをガイジだと認識してないガイジが湧くから大変だねえ

2023/03/22(水) 18:42:32.05

お前いつも論破されていつもそれだなw

2023/03/22(水) 18:47:43.32

自分が正しいと思ってる間は無茶苦茶な強弁するのに証拠を突きつけられたら自演して人格攻撃に移りなおかつ自演のやり方の講義までするというガイジはいつになったら自分をガイジと認識できるんだ？w

2023/03/22(水) 19:16:24.27

効いてて草

2023/03/22(水) 19:28:06.30

制約上オーバーフローしうることがWAの原因なんだから、制約も、その制約によってオーバーフローするようなコードを書いたことも、それぞれ原因と言っても別にいいだろ
マジでしょうもねえ…

2023/03/22(水) 19:39:59.04

アホなのか？
回答の制約じゃなく質問の制約だそ？
原因はそれを考慮しなかったことに決まってんじゃんw
日本語読めないのかよ
ChatGPTですら読めるのにw

2023/03/22(水) 20:09:59.70

ほんとに何言ってるのかわからんわ
自分の中では理屈が通ってるんだろうけどどう通ってるのか想像することさえ難しい

2023/03/22(水) 20:11:09.38

何言ってるのかわからんのは自分の頭が悪いからと早くきづけるようになれるよう祈ってるよ
わかんなきゃChapGPTに聞け
正確に理解してるから

2023/03/22(水) 20:11:39.38

まあ要するにお前の言語能力は原始的なAI以下ということだ

2023/03/22(水) 20:33:08.15

ガイジスレはひとつだけにしてくれないか？

2023/03/22(水) 21:28:24.75

みんな集合だ

2023/03/23(木) 09:08:18.69

読解力でAI未満てそれ何ならAIに勝てるの？
もしかして数学で勝てるつもりなのか？

2023/03/23(木) 10:15:35.12

https://qiita.com/uynet/items/e700a4adf5263e4c1904
ChatGPT一人でレスバする

2023/03/23(木) 13:17:46.25

暴れてる奴もChatGPTなんだ怒らないでやってくれ