競技プログラミングにハマるプログラマのスレ 176

1 ：仕様書無しさん：2024/05/12(日) 23:43:01.26 .net

競技プログラミング、オンラインジャッジ、プログラミングコンテストやCTFに関する雑談スレ
次スレは>>950

AtCoder http://atcoder.jp/
yukicoder http://yukicoder.me/
Codeforces http://codeforces.com/
CodeChef http://codechef.com/
Project Euler http://projecteuler.net/
CLIST http://clist.by/
AtCoder Problems http://kenkoooo.com/atcoder/
AtCoder Clans http://kato-hiro.github.io/AtCoderClans/

前スレ
競技プログラミングにハマるプログラマのスレ 168
https://medaka.5ch.net/test/read.cgi/prog/1711463770/
競技プログラミングにハマるプログラマのスレ 169
https://medaka.5ch.net/test/read.cgi/prog/1711884759/
競技プログラミングにハマるプログラマのスレ 170
https://medaka.5ch.net/test/read.cgi/prog/1712220373/
競技プログラミングにハマるプログラマのスレ 171(旧)
https://medaka.5ch.net/test/read.cgi/prog/1712726816/
競技プログラミングにハマるプログラマのスレ 171(新)
https://medaka.5ch.net/test/read.cgi/prog/1712726828/
競技プログラミングにハマるプログラマのスレ 172
https://medaka.5ch.net/test/read.cgi/prog/1713176839/
競技プログラミングにハマるプログラマのスレ 173
https://medaka.5ch.net/test/read.cgi/prog/1714042920/
競技プログラミングにハマるプログラマのスレ 174
https://medaka.5ch.net/test/read.cgi/prog/1714572646/
競技プログラミングにハマるプログラマのスレ 175
https://medaka.5ch.net/test/read.cgi/prog/1714981816/

535 ：仕様書無しさん：2024/05/13(月) 23:10:57.32 .net

すぬけさんのARCでのDの提出コード
ttps://atcoder.jp/contests/arc177/submissions/53420383

536 ：仕様書無しさん：2024/05/13(月) 23:11:41.22 .net

言われると方針は難しくはないけど、まあめんどいパートはちょこちょこあるしそれに998のバグが挟まると苦しそう

537 ：仕様書無しさん：2024/05/13(月) 23:11:44.08 .net

草生えまくり

538 ：仕様書無しさん：2024/05/13(月) 23:11:52.36 .net

赤diffストリークって続けられるほど問題あるの？
インコだから分からない

539 ：仕様書無しさん：2024/05/13(月) 23:12:26.82 .net

別にマジでスレは卒業したいんだよな
普通にスレのやる気あるデア勢でdiscord作って移住してネトストゴシインコを置き去りにしたい

540 ：仕様書無しさん：2024/05/13(月) 23:12:57.27 .net

本スレに移住するだけで良かったりしない？

541 ：仕様書無しさん：2024/05/13(月) 23:13:01.52 .net

>>538
problems見ればわかるけど赤だけでも300くらいあるし銅以上含めたらもっとある

542 ：仕様書無しさん：2024/05/13(月) 23:13:44.25 .net

すぬけさんもDは解けなかったか

543 ：仕様書無しさん：2024/05/13(月) 23:14:23.50 .net

解けないというかアンレだしやる気起きなかっただけでは

544 ：仕様書無しさん：2024/05/13(月) 23:14:31.10 .net

でもメンタル限界の日に変な書き込みできませんよ

545 ：仕様書無しさん：2024/05/13(月) 23:14:33.28 .net

いたとしたら特定容易

546 ：仕様書無しさん：2024/05/13(月) 23:14:36.74 .net

AのFAってgptなのかなぁ
コードみるとそんな感じがする

547 ：仕様書無しさん：2024/05/13(月) 23:14:58.69 .net

俺はメンタル限界の日に変な書き込みをしているため

548 ：仕様書無しさん：2024/05/13(月) 23:15:09.77 .net

E通してから14分しかなかっただけの話では

549 ：仕様書無しさん：2024/05/13(月) 23:15:43.16 .net

キチゲ発散スレなので

550 ：仕様書無しさん：2024/05/13(月) 23:17:51.50 .net

たしかにGPTっぽい
判定ツール使うと高確率でAI生成されたコードと判定される

551 ：仕様書無しさん：2024/05/13(月) 23:17:58.67 .net

メンタル限界の日に憂さ晴らしにここ来てるわ

552 ：仕様書無しさん：2024/05/13(月) 23:18:36.64 .net

ガイジスレはガイジ達のハッテン場

553 ：仕様書無しさん：2024/05/13(月) 23:19:25.29 .net

discordで馴れ合うのとxで馴れ合うの、違いは何？

554 ：仕様書無しさん：2024/05/13(月) 23:20:01.93 .net

>>550
gpt使うだけでARC-AでFAとれちゃうとなると何とも言えない気持ちになるな

555 ：仕様書無しさん：2024/05/13(月) 23:20:56.57 .net

昨日のARC-Aは実質ABC-CなのでGPTでも解けるのはそう

556 ：仕様書無しさん：2024/05/13(月) 23:21:12.81 .net

灰diffがAIで解かれてそんなに騒ぐ？

557 ：仕様書無しさん：2024/05/13(月) 23:21:25.25 .net

Xで馴れ合えない人がここに集まってるため

558 ：仕様書無しさん：2024/05/13(月) 23:21:25.70 .net

GPT Detectorみたいな感じでググるとたくさん判定ツールでてくるよ

559 ：仕様書無しさん：2024/05/13(月) 23:22:27.62 .net

教授にもツールのことを教えておこう

560 ：仕様書無しさん：2024/05/13(月) 23:23:55.40 .net

AI検知系ツール
誤検知多すぎておわり

561 ：仕様書無しさん：2024/05/13(月) 23:25:22.09 .net

社会不適合エピソードを消費的に披露してキャッキャしてる奴にはなりたくないので
ジェネルシエピソードはここだけにしてる

562 ：仕様書無しさん：2024/05/13(月) 23:27:14.87 .net

ワイはゴシの話をする時はスレで、デアの話をする時はXで強い人(青以上)を相手にするようにしてる

563 ：仕様書無しさん：2024/05/13(月) 23:27:51.95 .net

最近はDiscordが流行ってんの？

564 ：仕様書無しさん：2024/05/13(月) 23:29:19.36 .net

誤検知のせいで単位落として留年したからAIは死ぬまで恨む

565 ：仕様書無しさん：2024/05/13(月) 23:30:53.83 .net

AtCoder Regular Contest - A (300点) で出るようなアドホックな易しめの問題を作ってください。

ChatGPT
問題文:
あなたはある日、買い物リストを作成しています。買い物リストには N 個のアイテムがあり、それぞれのアイテムは 1 から N までの番号が付けられています。
しかし、あなたは急いでいて、買い物リストのアイテムをランダムな順番で記入してしまいました。幸いなことに、あなたはその買い物リストに対して 2 つの操作が可能です。

操作1: リスト内の隣接する 2 つのアイテムの位置を交換する。
操作2: リスト内の先頭と末尾のアイテムの位置を交換する。

最小の操作回数で、買い物リストを番号順に並び替えるプログラムを作成してください。ただし、1 ≦ N ≦ 100 とします。

入力:
最初の行にはアイテムの数 N (1 ≦ N ≦ 100) が与えられます。
2 番目の行には 1 から N までの整数が空白区切りで与えられます。これが買い物リストの初期状態を表します。

出力:
最小の操作回数を出力してください。

制約:
入力される整数はすべて整数であることが保証されます。

566 ：仕様書無しさん：2024/05/13(月) 23:31:48.21 .net

わかる
不真面目イキリは普通にダサいし中高生までが限度

567 ：仕様書無しさん：2024/05/13(月) 23:31:52.87 .net

今日も頑張ってる中学生・高校生尊い

おい！未就学のガキ、小学生、大学生、おっさんは尊くないぜ！

568 ：仕様書無しさん：2024/05/13(月) 23:32:39.71 .net

狂人の真似とて大路を走らば即ち狂人なり

569 ：仕様書無しさん：2024/05/13(月) 23:32:40.17 .net

周りに流されて不真面目イキリしてる大学生は本当にキツいししょうもないやつしかいない

570 ：仕様書無しさん：2024/05/13(月) 23:33:32.72 .net

青以上は強いラインとして微妙だろ
こんな問題も解けないんですよ定期

571 ：仕様書無しさん：2024/05/13(月) 23:33:58.87 .net

君たちはどうイキるか

572 ：仕様書無しさん：2024/05/13(月) 23:36:20.63 .net

水青黄スレ終了

573 ：仕様書無しさん：2024/05/13(月) 23:36:41.85 .net

怠惰な張り付きインコによる数字のマジック定期

574 ：仕様書無しさん：2024/05/13(月) 23:37:27.67 .net

>>565
最初状態を頂点に持つBFSだと思っちゃった
1から順にえっちらおっちら移動させるシミュレーションすればいいのかな？

575 ：仕様書無しさん：2024/05/13(月) 23:37:28.21 .net

>>565
最初状態を頂点に持つBFSだと思っちゃった
1から順にえっちらおっちら移動させるシミュレーションすればいいのかな？

576 ：仕様書無しさん：2024/05/13(月) 23:39:39.25 .net

えっち (〃ﾉдﾉ)

577 ：仕様書無しさん：2024/05/13(月) 23:39:48.47 .net

明らかにA300レベルじゃない問題はNG

578 ：仕様書無しさん：2024/05/13(月) 23:40:35.05 .net

来週のARCも勝つぞ

579 ：仕様書無しさん：2024/05/13(月) 23:41:05.95 .net

機械学習の学習でずっとGPU回してるけど電気代やばそう

580 ：仕様書無しさん：2024/05/13(月) 23:43:47.54 .net

1から順にえっちしても解けんため

581 ：仕様書無しさん：2024/05/13(月) 23:46:09.00 .net

昨日のAみたいなの正当性証明のdiffと思いつくdiffの乖離がでかすぎるから好きじゃないわ
ARC-Aなんて所詮この程度ｗって思って投げるのが正解になってしまう

582 ：仕様書無しさん：2024/05/13(月) 23:48:13.27 .net

「強い人(青以上)」はインコ透けすぎでしょ

583 ：仕様書無しさん：2024/05/13(月) 23:49:16.63 .net

300点のコイン問題が貪欲インコ問出ないとやばいため→AC

584 ：仕様書無しさん：2024/05/13(月) 23:50:22.86 .net

インコ問のcommonの部分

585 ：仕様書無しさん：2024/05/13(月) 23:50:28.16 .net

ああいう証明が難しい貪欲はあまりABC的じゃなくてARC/AGCっぽいんだけど、あまりにもその貪欲を思いつくのが簡単すぎたって感じ

586 ：仕様書無しさん：2024/05/13(月) 23:51:50.35 .net

Bの操作回数を最小化する場合

587 ：仕様書無しさん：2024/05/13(月) 23:51:58.83 .net

前回の双子ARCのAを両替の問題って言ってくれた人のおかげで今回はすぐ貪欲だと分かった

588 ：仕様書無しさん：2024/05/13(月) 23:53:27.03 .net

大きいコインから使う貪欲の正当性ってそんなに気になるもんなの？
同じ金額を選ぶなら後の自由度が高くなるようにするのがいいから...

589 ：仕様書無しさん：2024/05/13(月) 23:54:49.82 .net

>>582
界隈の強いひとにギリギリ認められているのが青コーダーだからね

590 ：仕様書無しさん：2024/05/13(月) 23:55:43.74 .net

今回見たいな回はWA出したら被害結構あるし、そこの気持ち悪さ抱えたまま数分の間に解くのきつくないか

591 ：仕様書無しさん：2024/05/13(月) 23:56:53.90 .net

強い人 (ただしインコ)

592 ：仕様書無しさん：2024/05/13(月) 23:57:41.57 .net

そもそも金額の組み合わせがちょっと違ったら正当じゃないからな
通貨問題典型ではあるが

593 ：仕様書無しさん：2024/05/13(月) 23:58:04.19 .net

貪欲で払えるなら自明に払える(そのように払える)
逆払えるなら、ある払い方の2つの払い方についてより大きな硬貨と小さい硬貨で入れ替えて大きい硬貨を貪欲で選んでいるような払い方にできる？

594 ：仕様書無しさん：2024/05/13(月) 23:58:15.20 .net

>>587
これ書いたの私です　感謝しなさい

595 ：仕様書無しさん：2024/05/13(月) 23:58:36.53 .net

人呼ばわりなのに実態はインコとはこれいかに

596 ：仕様書無しさん：2024/05/13(月) 23:58:51.67 .net

インコイン問題というわけか
スレに媚びすぎ

597 ：仕様書無しさん：2024/05/14(火) 00:00:00.21 .net

いや、必ず入れ替えられるな(それぞれの硬貨が整数倍なので)
じゃあOK

598 ：仕様書無しさん：2024/05/14(火) 00:00:00.55 .net

まあわかる
大銭から払う貪欲の正当性が示せない場合小銭から払う貪欲も試さなあかんが、これなら1ペナ吐くのと期待値変わらんと思って大銭貪欲で未証明subした

599 ：仕様書無しさん：2024/05/14(火) 00:00:43.48 .net

Aにしては簡単すぎて怖いのはわかるけど流石に有名問題すぎるため
BCも同じ感覚でポンポン提出した

600 ：仕様書無しさん：2024/05/14(火) 00:00:49.37 .net

こんな問題も解けないのかみたいな枠で引用されるイメージが強い
インコにしてはできるハイエンド型インコだけど、人間の問題解かせたらやっぱ全然だめだねみたいな

601 ：仕様書無しさん：2024/05/14(火) 00:01:23.16 .net

優インコ:青
インコ大王:黄色タッチ
インコ人間境界線:2100

再掲

602 ：仕様書無しさん：2024/05/14(火) 00:01:27.67 .net

3円玉と5円玉の場合は破綻するので普通に怖いとおもった

603 ：仕様書無しさん：2024/05/14(火) 00:02:10.43 .net

まあ双子なら前半はコーナーケースサンプルに置いてくれるイメージある

604 ：仕様書無しさん：2024/05/14(火) 00:03:12.92 .net

Bは作問歴があれば10^6がジャッジの都合でしかない値だと確信できる

605 ：仕様書無しさん：2024/05/14(火) 00:03:46.50 .net

そういう指定こどふぉで無限回あるから関係ない

606 ：仕様書無しさん：2024/05/14(火) 00:04:42.42 .net

人間の問題とかいう概念好き
ハイエンド型インコもカッコよくて好き

607 ：仕様書無しさん：2024/05/14(火) 00:05:06.91 .net

>>565
これ結局解ける問題なの？

608 ：仕様書無しさん：2024/05/14(火) 00:05:14.40 .net

それぞれの硬貨が整数倍じゃなかったらどうなるの？
2種類とかじゃないと解けなくない？

609 ：仕様書無しさん：2024/05/14(火) 00:06:06.99 .net

部分話問題に帰着されるので色々辛そう
DP復元とかでできると思うけど貪欲では無理

610 ：仕様書無しさん：2024/05/14(火) 00:08:01.42 .net

>>608
コインの種類数次元のDPでどうですか？

611 ：仕様書無しさん：2024/05/14(火) 00:08:25.62 .net

>>607
gptに解答聞いたけど余裕で間違えてそうだから消しちゃった
でも解けるなら流石に既出そう

612 ：仕様書無しさん：2024/05/14(火) 00:08:27.24 .net

今回の200枚以下ならdp[i][j][k]=i番目の支払いまで終わってAをj、Bをk枚使った時のCを使用した数で持てば3枚くらいまでは処理できそう(支払い方が結構多いので遷移ダルいけど)

613 ：仕様書無しさん：2024/05/14(火) 00:09:06.78 .net

>>565
円環上でバブルソートをすると考えて、最適な操作の場合必ずどこかに交換が起きない部分があるのでどこで切るかを全部試す、みたいな？

614 ：仕様書無しさん：2024/05/14(火) 00:10:14.05 .net

インコ作問やめてね

615 ：仕様書無しさん：2024/05/14(火) 00:11:29.08 .net

i種類目のお土産までを買ったとき、(X,Y,Z)円玉が残り(x,y,z)枚
の4次元dpでzは落とせる的な

616 ：仕様書無しさん：2024/05/14(火) 00:12:08.04 .net

円環のバブルソート最小化ってできるの？

617 ：仕様書無しさん：2024/05/14(火) 00:12:50.55 .net

>>613
ARCで出題されたらメタ読みでこれでやるけど交換しない場所があるっていう証明ができない

618 ：仕様書無しさん：2024/05/14(火) 00:12:55.38 .net

nimさんに教えてもらおう

619 ：仕様書無しさん：2024/05/14(火) 00:14:01.52 .net

もしそれでAC射精完了できるのなら普通にARC-Bとかに置ける良問そう

620 ：仕様書無しさん：2024/05/14(火) 00:17:55.50 .net

上界下界が実は達成できます、隣接を見れば見通しが良くなります、区切りを全探索出来ますみたいなのARCで無限回見た

621 ：仕様書無しさん ころころ：2024/05/14(火) 00:24:54.50 .net

交換しない箇所を決め打って転倒数をO(1)で更新か

622 ：仕様書無しさん ころころ：2024/05/14(火) 00:25:41.04 .net

交換しない箇所があることの保証はどうやって証明しますか

623 ：仕様書無しさん ころころ：2024/05/14(火) 00:26:54.50 .net

e8くんのアンチおるやん
twitter.com/aplysiaSheep/status/1789813006848729167?t=7pIwkQiItX0Ley5BpvFjYw&s=19
(deleted an unsolicited ad)

624 ：仕様書無しさん：2024/05/14(火) 00:30:35.77 .net

マシュマロにしか来ない雑魚

625 ：仕様書無しさん：2024/05/14(火) 00:32:43.28 .net

個人的には所謂毒マロを拾うのもどうかと思う

626 ：仕様書無しさん：2024/05/14(火) 00:46:44.13 .net

のだ氏ものん氏ものし氏も毒マロは無視してるからな

627 ：仕様書無しさん：2024/05/14(火) 00:52:45.95 .net

キモいと思うのはお前が嫉妬してるから定期

628 ：仕様書無しさん：2024/05/14(火) 00:54:57.84 .net

競プロ界隈がキモい連中だらけだから、競プロ関係者は競い合うようによりキモくなっている
社長も副社長もキモいのはこのため

629 ：仕様書無しさん：2024/05/14(火) 00:56:53.40 .net

結局TKNDKS+UT+暖色(赤色)という完全なる上位存在への嫉妬ドリブンでしかない

630 ：仕様書無しさん：2024/05/14(火) 01:05:12.23 .net

GPT-4にキモくないように書き直して、ってお願いすればいいだけなのに

631 ：仕様書無しさん：2024/05/14(火) 01:32:22.04 .net

学業、実は楽しいがち

632 ：仕様書無しさん：2024/05/14(火) 05:44:42.82 .net

ラジオ体操第一をして疲弊　ねりゅ

633 ：仕様書無しさん：2024/05/14(火) 06:29:01.35 .net

ガイジスレ終了

634 ：仕様書無しさん：2024/05/14(火) 08:45:38.87 .net

GPT-4oすげえな
もはや人間よりも圧倒的に人語を扱うのが上手い