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

2022/10/02(日) 17:43:58.66

↑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/26(土) 23:04:28.90

>>586
俺も
高校時代だったらすぐに証明できただろうけど
わからなかったからmatplotlibで関数の形見て下に凸だって決めつけてしまった

2022/11/26(土) 23:20:38.01

>>585
scipyのoptimise

2022/11/26(土) 23:29:09.61

１年ぶり位に復帰したけどインフレやば過ぎワロタ
三分探索が茶とかもう無理ゲ

2022/11/27(日) 00:02:27.32

別に三分探索しなくても解けるからね

2022/11/27(日) 00:11:00.75

手計算したくないから、回答と少し違うwolfram先生の解析解の周辺の最小値でやったけど、最後のサンプルがどうやってもあわなくscipyに。実務家的ｗには脳死でoptimize一択。

2022/11/27(日) 00:29:03.57

Dで10^18制約で誤差10^-6無理じゃね？と思ったら絶対誤差または相対誤差って書いてあることに気付いた
ひょっとして今までの問題も全部そうだったのか

2022/11/27(日) 00:30:45.88

Python しか触ってないからわからないんだけど
他のCとかだと誤差が大きくなって3分探索とか使わないといけなくなるもの？

2022/11/27(日) 00:34:30.35

>>592
微分して0になる点の整数インデックスさえ求められれば
そこからプラマイ5くらいずらして最小値を求めてばいいと思うけど
俺はPythonでインデックスとインデックス＋1の最小値で求めることできたけど
ってか代数的に解ける問題が出てくるんだなってびっくりした

2022/11/27(日) 00:38:57.81

せっかくデ/アのスキルを磨ける競プロをやってるんだから、代数解法よりも三分探索を使って解いてほしいところ
まあ競技的にはとにかく解ければ勝ちなんだけど

2022/11/27(日) 00:42:37.70

>>595
計算量を考察する箇所でも代数的な考察するし

代数だけではどうしようもないということを頭でしっかり認識してからパズル的に解くのが醍醐味だと思うんだけど

2022/11/27(日) 00:44:19.50

>>593
想定解法であれば、3分探索で絞り込むのは「操作回数」だから、誤差が代数解法よりも小さくなるわけではないよ

2022/11/27(日) 00:46:09.44

そうだね、そら何にしても数学は使うよ
デ/アはそもそも数学が下地にあるからね

2022/11/27(日) 00:47:05.59

>>597
誤差の部分よくわからんのよね
どのくらいの誤差が起こり得るのかが
コンピュータの深い部分か何かしらの知識があればわかるんだろうけど

FFTで誤差が出ないから、とりあえず実用範囲で小数計算の誤差は考慮してないな
それだけPythonが数値計算で有能なのかも知れないが

2022/11/27(日) 00:47:32.02

>>598
デ/アって何？？

2022/11/27(日) 00:51:50.68

>>599
きみは何らかの代数ライブラリを使ったのかもしれないけど、おれが「代数解法」と呼んだのは公式解説にある「解法2　微分」のこと
「解法1　三分探索」でも「解法2　微分」にしても、どちらにしても最小値になる回数を見つけてからの計算方法はほぼ同じだから、同じ精度で答えが出力される
よって誤差は関係ない

>>600
データ構造とアルゴリズム

2022/11/27(日) 00:53:59.03

>>601
俺は微分したけど、3分探索はわからないけどLogNとかになるのだとしたら微分したらO(1)だと思うからそっちの方が速そうだけどな

データ構造／アルゴリズム
→わからんかったよ。。

2022/11/27(日) 00:55:09.30

>>600
データ構造/アルゴリズムの略

2022/11/27(日) 00:56:10.24

>>603
解説聞いたらわかったけど、初見じゃわからんかったよ

2022/11/27(日) 00:58:54.64

すまんな、競プロの界隈だとデ/アってよく使うから当たり前に使っちゃうわ

2022/11/27(日) 00:59:07.32

数学が下地にあるのは確かだけど、日本の学校教育では出てこないようなパズル問題が出てくるところが競プロの好きなところ

2022/11/27(日) 01:00:50.63

>>605
常識だったのか。スラッシュあまり使わない俺はあまり馴染まないかも知れない(と言って1週間後使ってるかもしれない)
競プロ初心者高卒だから、そういう界隈の言葉どんどん教えてくれると嬉しい

2022/11/27(日) 01:06:28.84

いや、ただのTwitterスラングやで
わからんくて当たり前

2022/11/27(日) 01:16:51.24

まあプログラマーは一応理工系技術職だし、高校理系標準レベル微積ぐらい扱えた方がいいと思うぜ

2022/11/27(日) 01:35:50.76

理系ならフォートランつかえ

2022/11/27(日) 02:20:45.46

ワテが3分探索を使わない理由は
・最適化の本で見たことがない
・多次元に拡張できない、教プロ特有な気がするので学習モチベがわかない

こんなところか・・・

2022/11/27(日) 05:04:19.20

今回は入力が整数だから二分探索のが分かりやすい気がした
めぐる式でf(x)とf(x+1)を比較して大きいならok、そうでなければng
最後にf(ok)を出力するだけ

2022/11/27(日) 08:39:17.72

下に凸と想定して二分探索で解けたよ

2022/11/27(日) 11:51:36.21

きんたま

2022/11/27(日) 13:33:50.96

>>608
コンピュータサイエンス用語でもない競プロスラングなんだからわからんのが当然だとは思うけど、「競プロの界隈だと」と言ってるのに高卒だからと関係ないことを言い始めるあたりの理解力はちょっと怖い

2022/11/27(日) 16:09:24.87

無学なものですが、的な表現なんじゃないか
そういう卑下は別にせんでいいとは思うがな
大卒でもプログラミングも競プロもずっと分かってないやつ五万といると思うわ

2022/11/27(日) 22:31:30.18

>>615
高卒の俺でもある程度頑張ってるよって言いたかっただけ

あと、高卒ってベースとなる知識が圧倒的に少ないと感じてるからスラングでもなんでも、そういう中に考え方が潜んでるからそれを学びたいっていう気持ちがあっただけだよ

2022/11/28(月) 17:33:31.00

二分探索って初期値(左と右の)の設定難しくね？
279_dは解の範囲考えてるときに微分すること思い付いた。

1/(n+1)の微分をググったのはちょい恥ずかしい

2022/11/28(月) 21:02:15.01

計算がおかしくならないならでかい値でもよい
難しい考察なしで0からAにしてAC

2022/11/28(月) 21:11:23.21

AGC、12月25日に入ったね
それ自体はめでたいことだけど、もうちょっと間隔をバラした方がありがたいような
そしてクリスマスという

2022/11/28(月) 23:37:01.00

>>619
二分探索で解けることはちっとも明らかじゃないと思うんだがなんで二分探索で解けるの？
https://atcoder.jp/contests/abc279/editorial/5295
これと同じ解き方？

2022/11/29(火) 02:57:37.73

実際クリスマスだからといって何か予定入れることあるかね？

2022/11/29(火) 08:51:22.57

ギャグ抜きにして海外勢も予定入ってるやつ多そうだし、正直どういう判断でクリスマスに入れようと思うのかよくわからんわ

2022/11/29(火) 11:29:42.82

ようやく問題が揃ったってだけじゃね
寝かせてると他で使われちゃうから新鮮なうちに出さないと

2022/11/29(火) 11:56:47.92

>>621
下に凸ということがわかれば二分探索で解けることは明らかなんじゃね
接線の傾きが右上がりもしくは水平になる最小の値を調べればいい
つまり右下がりなら前半を捨てて右上がりなら後半を捨てるの繰り返し
初期範囲は0からAで行けるしその倍でも比較が一回増えるだけ

2022/11/29(火) 11:57:21.09

クリスマスって年間のイベント日の中でも tier 高いんですか？祝日ですらないけど

2022/11/29(火) 11:57:42.28

>>623
競プロデートすればいいじゃん

2022/11/29(火) 12:03:28.49

>>625
ああ、傾き使ってるなら納得

2022/11/29(火) 13:55:24.58

自分は傾きでなくマイナス1とプラス1の値で比較したから合わなかったんだな
gの変化が1ずつだからってそれでは駄目なんやね
3分探索も知らなかったけど色々勉強になって面白かった

2022/11/29(火) 14:59:09.55

AGCを積極的に求めてる程競プロに入れ込んでる層はクリスマスなんかに予定が入ってるわけないだろうと足下を見られてるな

2022/11/29(火) 17:05:58.54

例年クリスマスコンあるし今更すぎる

2022/11/29(火) 17:19:52.47

日本ローカルな有志コンならともかく、数少ないグローバルなAGCがわざわざXmasに重ねられてるのはちょっとどうかなという気はしちゃうな
AtCoder側の都合はしらんけど、欧米圏だと24日は仕事は早くあがって、クリスマスマーケットも終わって、25日はゆっくり過ごすだけの祝日と相場が決まってる

2022/11/29(火) 18:38:45.42

海外勢にこそアピールしたいAtCoder最高コンテンツのはずのAGCとクリスマスコンテストを同列に語られても

2022/11/29(火) 18:47:34.27

問題が爆破されないように、という理屈は理解できるが、3週間寝かせるだけで問題が爆発されるようなシビアな世界なのか？というのも気になるな
ARCならまあありそうだが

2022/11/29(火) 20:42:51.50

ABCのC問題
ST各行の・の数だけカウントして比較してるだけで正解なの何でなん(´・ω・｀)
転置して文字比較じゃないと題意を満たさないと思うんだけど

2022/11/29(火) 20:58:40.10

誤った解答だと思うけどそれでACできるの？

2022/11/29(火) 20:59:15.21

誤った解答というのは「ST各行の・の数だけカウントして比較」の話ね

2022/11/29(火) 21:00:15.27

それが落ちるケースなかっただけでは

2022/11/29(火) 22:07:29.73

テストケースが弱いことなんてしばしばあるし

2022/11/29(火) 23:04:14.45

マルチテストケースにしてNが小さいところは全部入れれば簡単にテスト強くなるけど
AtCoderはやらないよね

2022/11/30(水) 00:12:33.13

>>635
転地しないと駄目なのはaftercontest 追加されてたけど
点の数だけで通るってマジ？

2022/11/30(水) 09:53:36.46

いつも思うんだけど、そういう作問の不備らしき問題ってどこに通報すればいいの？

2022/11/30(水) 13:22:48.31

ちょくだいにリプ爆しろ

2022/11/30(水) 14:34:30.64

ブロックされそうでこわい

2022/11/30(水) 15:07:15.45

マジでTwitterくらいしかないよね
外国の人かわいそう

2022/11/30(水) 17:02:31.77

解説と同じアルゴリズムだと通るのに愚直に解くとWAになることがあって悩んだことがある
TLEならともかくWAになるはずなかったんだがなあ
なにせ1000000007で割った余りを書きましょうという問題で全部BigDecimalで計算して最後に一度だけ割る解法だったし

2022/11/30(水) 18:55:40.36

へえそうなの
大変だったね

2022/11/30(水) 21:04:42.76

質問するならコードを貼れ
通らないならどっか間違ってんだろとしか言えん

2022/12/02(金) 14:05:45.12

AIに問題文投げただけで正答のコード返してくれるようになったら競プロは終わるのか？

2022/12/02(金) 15:11:52.86

灰茶は完全に死んだね

2022/12/02(金) 20:08:44.19

クリスマスはAGC🤓

2022/12/03(土) 21:56:16.75

クリスマスにちなんだスペシャル問題が出るんだろうな。

2022/12/03(土) 22:40:01.18

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.02

Fで無駄にLCA持ち出して距離を求めようとしたせいで時間浪費したのマジで勿体無くて泣ける　
LCAの項が打ち消されるのに

2022/12/03(土) 22:45:54.74

C簡単すぎてびびったわ(´・ω・｀)
Dは素数の問題だとわかったが何故かいつまてまでも数個ACせんかった(´・ω・｀)

2022/12/03(土) 22:46:49.20

今回はFまでの早解き回だったね　自分もカンストしてみたかった

2022/12/03(土) 22:47:06.24

22:40:00に正解しても得点入らないの

2022/12/03(土) 22:53:22.87

重み付きUnionFindってなんだろう
しらんけど同じようなことをおれは実装してたのかな

2022/12/03(土) 22:53:50.52

小数点以下が切り捨てられて表示されていて実際の提出時刻は22:40:00を僅かに過ぎていたのか
あるいはコンテストの開催期間は[21:00, 22:40)だったのか

2022/12/04(日) 09:19:17.67

これってカンニングやり放題だと思うんだけど意味あるの？
昔は会場で受けてた？

2022/12/04(日) 09:30:54.97

転職の武器になるかな？って思って調べるけどよくわからない
ここのスレ見てても転職できたという報告は全然ないね
募集枠はあるけど採用されないように見えるね

2022/12/04(日) 10:29:38.14

>>660
賢い友人いればカンニングし放題だよ

2022/12/04(日) 10:47:16.13

遊んでた結果副次的に転職出来たらラッキーくらいに思っておくのが賢明でそもそも転職目的で取り組むものじゃない定期

2022/12/04(日) 12:28:16.09

そういう事ね、とりあえず遊びでやってみるか

2022/12/04(日) 14:23:01.52

ChatGPTが解けてるのはただ単に問題文覚えているからだと思うが、AGCの新問を解けるようになったら革命起きそうだな

2022/12/04(日) 14:23:58.59

1万文字をcinで入力して、文字列長を調べたら4095と表示されてしまいました
何故でしょうか？(´；ω；｀)

2022/12/04(日) 14:45:43.34

だからコードを貼れと

2022/12/04(日) 16:28:54.17

途中に空白があって全部入力できてなかったとか

2022/12/04(日) 17:53:44.19

昨日の問題EのcriticalHitがよくわからないんだけど
解説にatcoderのincludeファイルがあるんだけどなんだこれ？
PとQ求めたらこのファイル使うと勝手に計算してくれるの？

2022/12/04(日) 17:56:34.68

chokudai「あれ、AGCも典型じゃね？」

2022/12/04(日) 17:57:37.82

それはAtcoder LibraryっていうAtCoderのジャッジで使えるライブラリなんだけど、初心者には明らかに説明不足だね・・・

2022/12/04(日) 18:03:15.78

>>671
つまり、高速でPとQを解かせるのが本題で、
mod計算はライブラリがあるからそこで時間つかうなよ！って事かね？
使わないと困るケースがあるんだろうけど...理解せずに脳死で覚えた方が良いんかな？

2022/12/04(日) 18:04:20.29

この手のDPにACLの出番あるのかと思ってみたけど、modintか

2022/12/04(日) 18:06:53.79

>>672
別にACL使わなくても自分でスクラッチしてどうにかなるレベルだけど、負になったときの処理とかがめんどいから使った方が楽って感じのノリ

2022/12/04(日) 18:09:27.71

そうだなあ
ACLで実装されてるのは有名アルゴリズムばかりで、ABCでもよく出題されるの多いからライブラリで実装されてるものは理解したほうがいい
ACLは使ってもいいし、使わなくてもいい

まあ、とりあえず問題が解ける程度には理解して使えるようになることをオススメしておくか
特にmodintは便利だと思う
ACLをローカルにインストールすれば、自分のパソコンからも使えるよ

2022/12/04(日) 18:12:21.58

ちなみにおれはC++使ってないし、そういうライブラリは一通り自分で作ってる

2022/12/04(日) 18:14:00.78

休日でぼーっとしすぎて頭が痛い
何かしらウォームアップするか、逆に仮眠取るかしないとAGCやばい気がする

2022/12/04(日) 18:16:11.55

>>677
休日の片頭痛は、だいたいカフェイン不足が原因だろうから、カフェイン摂っておけば治るというのが自説

2022/12/04(日) 18:24:50.23

モンスター爆飲みやなー
翌朝の予定とかもう関係ないね

2022/12/04(日) 20:00:57.71

分数をmodで表現する方法が分からなくて解説見に来た人が何も分からないままだから、「modでの計算はたとえばACLを使うことで求めることができます」みたいな一文とともにACLドキュメントへのリンク欲しいね
そもそも新しく入ってきた人はACLの存在知らないだろうし

2022/12/04(日) 20:09:31.79

小数点の既約分数表現だか、理解するモチベーションが全然わからない

2022/12/04(日) 20:18:03.95

分数のmod表現は最初は数字が非直観的で戸惑うかもしれないけど、やってることは全然難しくないからACL使用前提じゃなくて普通に理解すべき
逆元と繰り返し2乗法理解してれば一瞬で書けるし

2022/12/04(日) 20:40:00.50

>>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;

}

2022/12/04(日) 20:48:19.58

>>683
intで足りてる？

2022/12/04(日) 20:50:00.93

>>684
intって32ビットですよね？
でしたら足りてます

2022/12/04(日) 20:53:07.80

足りてるなら言う事無いですね。