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

レス数が1000を超えています。これ以上書き込みはできません。
2022/12/26(月) 12:47:37.63ID:CkzYHyzir
!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/20(月) 20:27:08.93ID:JGpTxGZup
>>906
当たり前っていうのはAIを適切な解き方に誘導したらそれに沿って解いてくれるのは当たり前って話をしていたつもりだった(3.5の時はこうしないと簡単な問題以外は解けなかった)

chatGPTがバージョン4になった今どういう風に解いてくれるのかは把握してないし先週のABCで7完したという話も初耳
2023/03/20(月) 20:44:01.94ID:AhWhyU3m0
Moのアルゴリズム提案してくれたやつは問題を読ませた“だけ“ではなくて質問である程度誘導してたとは思う
（もちろんそれで提案してくれるのはめちゃくちゃ凄いが）
2023/03/20(月) 20:46:48.04ID:BTFdTO690
>>907
まだ誘導とか言ってるのか
100回読むか小学校からやり直せよ
2023/03/20(月) 20:58:26.01ID:enr3USaTr
すまん、GPT4より弱いやつおる？w
2023/03/20(月) 21:06:12.87ID:S2Sybo+q0
レスバしたいだけのｱｳｱｳｳｰの人、結構みっともないからやめた方がいいよ
2023/03/20(月) 21:21:05.85ID:6NGESZufa
ほんと、そういうくだらないのはツイッターでやれよな
2023/03/20(月) 22:00:28.84ID:p6MhJ7dBa
お前いつも論破されてそれだな
2023/03/20(月) 22:45:45.31ID:g4VcAGMh0
すまん
初心者なんだが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.96ID:g4VcAGMh0
誰かどの辺が間違ってるか教えて
なんでACできないんだろ
2023/03/20(月) 22:49:06.83ID:g4VcAGMh0
お願いします
2023/03/20(月) 22:50:00.28ID:g4VcAGMh0
For文書いたら出来たけどなんか釈然としないよね
2023/03/20(月) 22:52:12.36ID:/KHjyqT50
ヒント：最小公倍数
2023/03/20(月) 22:54:12.33ID:6NGESZufa
最後x*yじゃなくlcmでどうや？
2023/03/20(月) 22:55:07.63ID:6aqreXsg0
総当たりして誤るテストケースを自分で見つけるスキルを身につけることも重要
2023/03/20(月) 22:56:59.35ID:g4VcAGMh0
ありがとうございます
たしかに、最小公倍数でいいですね
IQがゴミすぎるんで競プロ止めます
2023/03/20(月) 22:57:42.29ID:g4VcAGMh0
止める→辞める
2023/03/20(月) 22:58:49.74ID:g4VcAGMh0
止めるでいいか
2023/03/20(月) 23:52:08.09ID:0oNeBZFb0
コドフォ…
2023/03/20(月) 23:53:18.04ID:Lo04kl5hp
コンテスト開始前に突如延期は酷いやサーバーの問題だから仕方ないけど
926デフォルトの名無しさん (ﾜｯﾁｮｲ 9bca-aXiD)
垢版 |
2023/03/21(火) 01:06:39.53ID:WiAWCQDG0
おそらくGTPにヒューリスティックを除くatcoder的なスキルはほとんど使われていない、使われてるのはニューラルネット、内積、最適化、強化学習など。何故か整数ばかりのパズル最適化は見当違いも良い所。
競プロは役に立たない。
2023/03/21(火) 01:20:29.80ID:W35aCdkdp
役に立つと思ってやるもんじゃないって既に無限回言われてるだろ何を今更
2023/03/21(火) 10:22:30.40ID:ayGaCmzS0
AtCoderJobsのランクがほぼ無意味になるな
2023/03/21(火) 11:38:58.42ID:IeqWtZWC0
何も変わってないじゃん
2023/03/21(火) 12:36:35.41ID:eYzPE6ipM
>>926
> ニューラルネット、内積、最適化、強化学習

この並列笑えるな、内積はセンスある
2023/03/21(火) 13:35:42.22ID:BiuFHUvxp
競プロ以前に高校数学すらまともに勉強してなかったんだろうな
AI開発に全く従事してないような奴の妄言
932デフォルトの名無しさん (ﾜｯﾁｮｲ 9bca-aXiD)
垢版 |
2023/03/21(火) 13:55:08.65ID:WiAWCQDG0
>>930
トランスフォーマーの核なので強調してみたのじゃｗ

>>931
DSだけどどう温かい目で見てもABCの問題の大半は役に立たない。ガチ。
2023/03/21(火) 13:59:58.54ID:3NbTT7XB0
お前がディープステートだったのか
ついに正体を表したな
2023/03/21(火) 14:35:19.64ID:2zmgamhJ0
内積でqueryとkeyのある種の類似度を計算して重みとして利用するのはそうなんだけど、まず磨くようなスキルではないのではないかという
離散最適化が主なのはそうだけど、実質的には連続緩和して解くような問題もままあるので、連続最適化をしてないとも言えないし
935デフォルトの名無しさん (ｱｳｱｳｳｰ Sa95-lF85)
垢版 |
2023/03/21(火) 15:06:25.17ID:icU0z8mba
Winnyの金子ですね判ります
2023/03/21(火) 17:35:53.57ID:1DnfyNWD0
問題
N 枚のカードが横一列に並べられています。左からi 番目のカードには整数Ai​が書かれています。
カードの中からいくつかを選んで、合計がちょうどS となるようにする方法はありますか。
制約
1≦N≦60
1≦Ai,S≦10000
入力は全て整数
入力
N S
A1…AN
2023/03/21(火) 17:44:43.69ID:1DnfyNWD0
質問です
これって動的計画法を使う問題ですよね
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.85ID:1DnfyNWD0
自分でテストケースを作成して色々とやって見たのですが上手くいかないです
2023/03/21(火) 17:49:03.50ID:8HipxHLW0
>>937
全然ちゃんと確認してないんだけどj-A[i]で範囲外参照してそう

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

まあこういう遷移はめちゃくちゃ良くあるし慣れたらデバッグしないでも殆どミスらなくなると思う
2023/03/21(火) 17:54:56.33ID:wykVgs8rr
>>937
elifが間違ってる
2023/03/21(火) 17:59:28.32ID:1DnfyNWD0
>>939
ありがとうございます。
Ai＞jであるときとそうでないときで場合分けしたら上手く出来ました。
2023/03/21(火) 18:01:08.70ID:1DnfyNWD0
>>940
ありがとうございます
elifの部分もまちがえていましたか
2023/03/21(火) 18:04:55.14ID:1DnfyNWD0
配列外参照の仕様に関してはまだちゃんと理解していませんが、939のレスをヒントにして解決することが出来ました。
2023/03/21(火) 18:06:38.67ID:2/Nqgm+N0
j-A[i] < 0 にならない？
2023/03/21(火) 18:07:25.41ID:2/Nqgm+N0
寝てたら解決しとる
2023/03/22(水) 14:54:15.97ID:XBvF4hES0
質問
N個の正整数の最小公倍数を求める問題で分からない部分がありました。

コード1ではACが取れなかったのですが、コード2に変えてみたところACを取ることが出来ました。
数学的にはコード1もコード2も違いがないと思うのですが、何がいけなかったのでしょう。
頭を捻っても全く分かりません。
2023/03/22(水) 14:54:42.44ID:XBvF4hES0
コード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.27ID:XBvF4hES0
コード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.64ID:XBvF4hES0
行数制限のためテンプレートは省いております。
2023/03/22(水) 15:11:18.73ID:9X0hpeOca
多分問題文の省略したところに原因が書いてある
2023/03/22(水) 15:20:25.39ID:9X0hpeOca
次スレ

競技プログラミング総合スレ 66
https://mevius.5ch.net/test/read.cgi/tech/1679465982/
2023/03/22(水) 15:52:00.88ID:AvapjKF+d
l*A[i]がlong longの最大値を超えてオーバーフローするのでは
2023/03/22(水) 15:58:55.16ID:lb80FTnL0
今度から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.83ID:psQ7vQwG0
別に元々質問が多くて困っているようなスレではないし、ここで聞く分には構わないと思うけど、ChatGPTの性能すごいね
ただ、誤ったことも自信満々に言うから、まだまだ初学者向けのサービスではないと思う
2023/03/22(水) 16:14:44.26ID:lb80FTnL0
ここで聞いたら「省略したところに原因が書いてある」と言うやつがいるから書いたんだよ
原因は書いてないな
書いてあるのは制約だ
2023/03/22(水) 16:18:21.55ID:9X0hpeOca
制約が原因やん
2023/03/22(水) 16:23:05.26ID:lb80FTnL0
ちなみに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.71ID:lb80FTnL0
>>956
制約は原因じゃないぞ
むしろ制約があるためllに収まるから真逆だ
2023/03/22(水) 16:31:30.64ID:9X0hpeOca
口論したいわけじゃないんだが
制約が原因という表現で別に間違ってないやろ
2023/03/22(水) 17:23:43.33ID:XBvF4hES0
>>952
>>953
ありがとうございます
理解出来ました
次からはchatgtpに質問して解決できなかったらここで質問します
2023/03/22(水) 17:34:10.54ID:lb80FTnL0
>>959
間違ってる
電車が来てる時に線路内に入ってはいけないという制約があるとする
それを見ずアホが線路内に入って死んだとする
そいつが死んだ原因は制約か？
違うだろ

この質問の場合も制約があるから間違ったんじゃなく、制約がなくても間違ったんだぞ
10^9までの自然数という制約が無かった場合は条件分岐が必要になるがあるためにそれはしなくていい
制約は問題を簡単にしてるだけで難しくはしてない
2023/03/22(水) 17:39:14.74ID:+5G5XKDn0
その議論はいったいなんの意味があるの
2023/03/22(水) 17:46:21.59ID:9X0hpeOca
制約次第では上のコードでもあってるんだから制約が原因だろ
まあほんとに意味のないやり取りなんでこれ以上は相手しないが
2023/03/22(水) 17:59:23.68ID:lb80FTnL0
日本語わかんないやつはChatGPTより下だぞ
議論じゃなくお前の間違いを教えてやってんだから口答えすんな
2023/03/22(水) 18:07:59.02ID:lb80FTnL0
ChatGPTはお前らより賢いから正しく言葉を理解して正しく答えたぞw

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

制約を無視してしまったことによって誤った結果が生じた場合、それは制約ではなく主にあなた自身が原因です。制約は、現実的な制限を示すものであり、それらを考慮しないことは、問題を引き起こす可能性があるためです。ただし、制約が明確でなく、十分に説明されていなかった場合は、誤解が生じる可能性があります。その場合、制約を理解しようと努力する必要があります。結局のところ、誤りを修正するためには、問題を引き起こす可能性のある要因を正確に特定し、それを修正する必要があります。
2023/03/22(水) 18:18:52.57ID:2usK+X1Z0
こっちは自分のことをガイジだと認識してないガイジが湧くから大変だねえ
2023/03/22(水) 18:42:32.05ID:lb80FTnL0
お前いつも論破されていつもそれだなw
2023/03/22(水) 18:47:43.32ID:lb80FTnL0
自分が正しいと思ってる間は無茶苦茶な強弁するのに証拠を突きつけられたら自演して人格攻撃に移りなおかつ自演のやり方の講義までするというガイジはいつになったら自分をガイジと認識できるんだ？w
2023/03/22(水) 19:16:24.27ID:AM4tOKKV0
効いてて草
2023/03/22(水) 19:28:06.30ID:I3ioWv5uM
制約上オーバーフローしうることがWAの原因なんだから、制約も、その制約によってオーバーフローするようなコードを書いたことも、それぞれ原因と言っても別にいいだろ
マジでしょうもねえ…
2023/03/22(水) 19:39:59.04ID:FZyO6fDta
アホなのか？
回答の制約じゃなく質問の制約だそ？
原因はそれを考慮しなかったことに決まってんじゃんw
日本語読めないのかよ
ChatGPTですら読めるのにw
972デフォルトの名無しさん (ｱｳｱｳｳｰ Sa95-puZl)
垢版 |
2023/03/22(水) 20:09:59.70ID:B0eWQ6KXa
ほんとに何言ってるのかわからんわ
自分の中では理屈が通ってるんだろうけどどう通ってるのか想像することさえ難しい
2023/03/22(水) 20:11:09.38ID:FZyO6fDta
何言ってるのかわからんのは自分の頭が悪いからと早くきづけるようになれるよう祈ってるよ
わかんなきゃChapGPTに聞け
正確に理解してるから
2023/03/22(水) 20:11:39.38ID:FZyO6fDta
まあ要するにお前の言語能力は原始的なAI以下ということだ
2023/03/22(水) 20:33:08.15ID:RXktniz50
ガイジスレはひとつだけにしてくれないか？
2023/03/22(水) 21:28:24.75ID:AM4tOKKV0
みんな集合だ
2023/03/23(木) 09:08:18.69ID:lPGuvOFY0
読解力でAI未満てそれ何ならAIに勝てるの？
もしかして数学で勝てるつもりなのか？
2023/03/23(木) 10:15:35.12ID:jVJKu0via
https://qiita.com/uynet/items/e700a4adf5263e4c1904
ChatGPT一人でレスバする
2023/03/23(木) 13:17:46.25ID:WdGFfLtNa
暴れてる奴もChatGPTなんだ怒らないでやってくれ
2023/03/23(木) 14:16:50.21ID:Z5yFziEVa
そんな賢くないだろw
暴れてるやつは日本語ろくに読めないんだからw
981デフォルトの名無しさん (ﾜｯﾁｮｲ c95f-5jEH)
垢版 |
2023/03/23(木) 23:22:59.72ID:Ao+X9Xng0
日本語の言語能力が低く日本人にとってはありがいんだろうな。
2023/03/24(金) 16:34:03.18ID:uNFSm4wfa
チョクダイが焦ってるけどAIの流れとまらんだろ
上流と趣味以外はオワコン
983デフォルトの名無しさん (ﾜｯﾁｮｲ 9bca-aXiD)
垢版 |
2023/03/24(金) 20:08:26.11ID:YL1QOUou0
コーディングテストとしてjobsに関係ある層がほぼ消えるワケじゃからのぉ、ワシもrated参加はやめるのじゃ
2023/03/24(金) 20:21:20.15ID:ZgVZm4b/0
>>976
集合の集合は集合でしょうか？
2023/03/24(金) 20:38:08.20ID:b1BDfC7u0
集合でラッセルのパラドックスを考えるガイジも集合しろ
2023/03/24(金) 23:20:35.66ID:vIsectOc0
公式が出来るって言ったらそれはもう終わりじゃん
2023/03/25(土) 02:10:10.73ID:pc8UC5Ad0
教プロはもうおしまいです
GCJとTopCoder Openという最も有名な最強の競プロerが競う大会は終了です
ABCもChat AIに無双されます
初心者も上級者も楽しめない競技になります
2023/03/25(土) 05:29:06.97ID:DJDWvsTV0
ちょくだいの最近の投稿見ると焦りが隠しきれてないな
まぁ絵師みたいなもんか
2023/03/25(土) 10:48:21.84ID:qiY7Z9Qp0
ライト層はAIで良いじゃんってなるから競技人口増えなそう
990デフォルトの名無しさん (ﾜｯﾁｮｲ 86ca-SHnl)
垢版 |
2023/03/25(土) 12:29:02.91ID:90xyxOUe0
ボケ防止としてはかなり有用じゃ、コンテストの体がないとやる気がせん
2023/03/25(土) 16:26:46.80ID:sftOMQ21r
ゲートボールの代わりに競プロを普及させよう
2023/03/25(土) 17:16:42.74ID:pc8UC5Ad0
老人ってドーパミンがあんま出ないんじゃない？
だから競技にする必要ないんじゃね
数独問題集みたいにモクモクとやらせれば十分だろ
2023/03/25(土) 19:54:56.57ID:OgnUV7oza
歳取るとレート下がる一方になるし普通は辞める
2023/03/25(土) 22:42:00.12ID:4uRItVdp0
A～E5完
Dで方針間違えすぎてGまで取りかかれず
2023/03/25(土) 22:42:21.94ID:lg//0IqP0
Eのサンプル3が一生合わなかったのなんでだろう
2023/03/25(土) 22:44:53.55ID:J/KfDX0zM
Eそんなに難しいか？と思ったけど、確かに微妙に典型度低いかもしれんな
2023/03/25(土) 22:53:36.06ID:azcz0A/s0
崖すごそう
TOYOTAコン超えてそう
998デフォルトの名無しさん (ﾜｯﾁｮｲ 86ca-SHnl)
垢版 |
2023/03/25(土) 23:02:02.23ID:90xyxOUe0
3000人も解けてるけどこのD相当難しい、GTP4も解けてなかったし
2023/03/25(土) 23:09:47.69ID:lg//0IqP0
B4乗ループ最初は思いつかなくて面倒そうだなって思ってchatGPTに投げたら全然違うプログラム書いてきてキレてた
2023/03/25(土) 23:11:23.49ID:oNXBC9Tu0
>>998
同じくDで爆死。数字ごとのパリティまでは
気がついたのだが、長さNのビットベクトル
を10個作ってなんとかしようとしてしまった。
縦と横を入れ換える頭の柔軟性がなかった。
10011001
垢版 |
Over 1000Thread
このスレッドは１０００を超えました。
新しいスレッドを立ててください。
life time: 89日 10時間 23分 46秒
レス数が1000を超えています。これ以上書き込みはできません。
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況