競技プログラミング総合スレ 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/27(日) 00:46:09.44ID:14KOziN70
そうだね、そら何にしても数学は使うよ
デ/アはそもそも数学が下地にあるからね
599デフォルトの名無しさん (ﾜｯﾁｮｲ 9fbd-J0r1)
垢版 |
2022/11/27(日) 00:47:05.59ID:GvaDwkJ10
>>597
誤差の部分よくわからんのよね
どのくらいの誤差が起こり得るのかが
コンピュータの深い部分か何かしらの知識があればわかるんだろうけど

FFTで誤差が出ないから、とりあえず実用範囲で小数計算の誤差は考慮してないな
それだけPythonが数値計算で有能なのかも知れないが
600デフォルトの名無しさん (ﾜｯﾁｮｲ 9fbd-J0r1)
垢版 |
2022/11/27(日) 00:47:32.02ID:GvaDwkJ10
>>598
デ/アって何？？
2022/11/27(日) 00:51:50.68ID:14KOziN70
>>599
きみは何らかの代数ライブラリを使ったのかもしれないけど、おれが「代数解法」と呼んだのは公式解説にある「解法2　微分」のこと
「解法1　三分探索」でも「解法2　微分」にしても、どちらにしても最小値になる回数を見つけてからの計算方法はほぼ同じだから、同じ精度で答えが出力される
よって誤差は関係ない

>>600
データ構造とアルゴリズム
602デフォルトの名無しさん (ﾜｯﾁｮｲ 9fbd-J0r1)
垢版 |
2022/11/27(日) 00:53:59.03ID:GvaDwkJ10
>>601
俺は微分したけど、3分探索はわからないけどLogNとかになるのだとしたら微分したらO(1)だと思うからそっちの方が速そうだけどな


データ構造／アルゴリズム
→わからんかったよ。。
2022/11/27(日) 00:55:09.30ID:vTtL7Ko7M
>>600
データ構造/アルゴリズムの略
604デフォルトの名無しさん (ﾜｯﾁｮｲ 9fbd-J0r1)
垢版 |
2022/11/27(日) 00:56:10.24ID:GvaDwkJ10
>>603
解説聞いたらわかったけど、初見じゃわからんかったよ
2022/11/27(日) 00:58:54.64ID:14KOziN70
すまんな、競プロの界隈だとデ/アってよく使うから当たり前に使っちゃうわ
606デフォルトの名無しさん (ﾜｯﾁｮｲ 9fbd-J0r1)
垢版 |
2022/11/27(日) 00:59:07.32ID:GvaDwkJ10
数学が下地にあるのは確かだけど、日本の学校教育では出てこないようなパズル問題が出てくるところが競プロの好きなところ
607デフォルトの名無しさん (ﾜｯﾁｮｲ 9fbd-J0r1)
垢版 |
2022/11/27(日) 01:00:50.63ID:GvaDwkJ10
>>605
常識だったのか。スラッシュあまり使わない俺はあまり馴染まないかも知れない(と言って1週間後使ってるかもしれない)
競プロ初心者高卒だから、そういう界隈の言葉どんどん教えてくれると嬉しい
2022/11/27(日) 01:06:28.84ID:vTtL7Ko7M
いや、ただのTwitterスラングやで
わからんくて当たり前
2022/11/27(日) 01:16:51.24ID:vTtL7Ko7M
まあプログラマーは一応理工系技術職だし、高校理系標準レベル微積ぐらい扱えた方がいいと思うぜ
2022/11/27(日) 01:35:50.76ID:j8v2EUX60
理系ならフォートランつかえ
611デフォルトの名無しさん (ﾜｯﾁｮｲ bfe2-O5Hl)
垢版 |
2022/11/27(日) 02:20:45.46ID:BLocM/7p0
ワテが3分探索を使わない理由は
・最適化の本で見たことがない
・多次元に拡張できない、教プロ特有な気がするので学習モチベがわかない

こんなところか・・・
2022/11/27(日) 05:04:19.20ID:dLcFXUTDM
今回は入力が整数だから二分探索のが分かりやすい気がした
めぐる式でf(x)とf(x+1)を比較して大きいならok、そうでなければng
最後にf(ok)を出力するだけ
2022/11/27(日) 08:39:17.72ID:uzn6bbq2a
下に凸と想定して二分探索で解けたよ
2022/11/27(日) 11:51:36.21ID:l4mu+o+5a
きんたま
2022/11/27(日) 13:33:50.96ID:BTSTHwm10
>>608
コンピュータサイエンス用語でもない競プロスラングなんだからわからんのが当然だとは思うけど、「競プロの界隈だと」と言ってるのに高卒だからと関係ないことを言い始めるあたりの理解力はちょっと怖い
2022/11/27(日) 16:09:24.87ID:BResG1CfM
無学なものですが、的な表現なんじゃないか
そういう卑下は別にせんでいいとは思うがな
大卒でもプログラミングも競プロもずっと分かってないやつ五万といると思うわ
617デフォルトの名無しさん (ﾜｯﾁｮｲ 9fbd-J0r1)
垢版 |
2022/11/27(日) 22:31:30.18ID:NlD2vvTh0
>>615
高卒の俺でもある程度頑張ってるよって言いたかっただけ

あと、高卒ってベースとなる知識が圧倒的に少ないと感じてるからスラングでもなんでも、そういう中に考え方が潜んでるからそれを学びたいっていう気持ちがあっただけだよ
2022/11/28(月) 17:33:31.00ID:/fwLD4AIM
二分探索って初期値(左と右の)の設定難しくね？
279_dは解の範囲考えてるときに微分すること思い付いた。

1/(n+1)の微分をググったのはちょい恥ずかしい
2022/11/28(月) 21:02:15.01ID:GQvoQd/h0
計算がおかしくならないならでかい値でもよい
難しい考察なしで0からAにしてAC
2022/11/28(月) 21:11:23.21ID:WdPNyywH0
AGC、12月25日に入ったね
それ自体はめでたいことだけど、もうちょっと間隔をバラした方がありがたいような
そしてクリスマスという
2022/11/28(月) 23:37:01.00ID:d041iZGN0
>>619
二分探索で解けることはちっとも明らかじゃないと思うんだがなんで二分探索で解けるの？
https://atcoder.jp/contests/abc279/editorial/5295
これと同じ解き方？
2022/11/29(火) 02:57:37.73ID:fS7qvBJwM
実際クリスマスだからといって何か予定入れることあるかね？
2022/11/29(火) 08:51:22.57ID:iOy5VXiNM
ギャグ抜きにして海外勢も予定入ってるやつ多そうだし、正直どういう判断でクリスマスに入れようと思うのかよくわからんわ
2022/11/29(火) 11:29:42.82ID:Ka2TzeUEa
ようやく問題が揃ったってだけじゃね
寝かせてると他で使われちゃうから新鮮なうちに出さないと
2022/11/29(火) 11:56:47.92ID:Xod1Eynpa
>>621
下に凸ということがわかれば二分探索で解けることは明らかなんじゃね
接線の傾きが右上がりもしくは水平になる最小の値を調べればいい
つまり右下がりなら前半を捨てて右上がりなら後半を捨てるの繰り返し
初期範囲は0からAで行けるしその倍でも比較が一回増えるだけ
2022/11/29(火) 11:57:21.09ID:TK2MqA+bM
クリスマスって年間のイベント日の中でも tier 高いんですか？祝日ですらないけど
2022/11/29(火) 11:57:42.28ID:Xod1Eynpa
>>623
競プロデートすればいいじゃん
2022/11/29(火) 12:03:28.49ID:QobrmxBH0
>>625
ああ、傾き使ってるなら納得
2022/11/29(火) 13:55:24.58ID:Ka2TzeUEa
自分は傾きでなくマイナス1とプラス1の値で比較したから合わなかったんだな
gの変化が1ずつだからってそれでは駄目なんやね
3分探索も知らなかったけど色々勉強になって面白かった
2022/11/29(火) 14:59:09.55ID:FcjH27v8p
AGCを積極的に求めてる程競プロに入れ込んでる層はクリスマスなんかに予定が入ってるわけないだろうと足下を見られてるな
2022/11/29(火) 17:05:58.54ID:ftmXQiba0
例年クリスマスコンあるし今更すぎる
2022/11/29(火) 17:19:52.47ID:QobrmxBH0
日本ローカルな有志コンならともかく、数少ないグローバルなAGCがわざわざXmasに重ねられてるのはちょっとどうかなという気はしちゃうな
AtCoder側の都合はしらんけど、欧米圏だと24日は仕事は早くあがって、クリスマスマーケットも終わって、25日はゆっくり過ごすだけの祝日と相場が決まってる
2022/11/29(火) 18:38:45.42ID:sxQd4OITM
海外勢にこそアピールしたいAtCoder最高コンテンツのはずのAGCとクリスマスコンテストを同列に語られても
2022/11/29(火) 18:47:34.27ID:sxQd4OITM
問題が爆破されないように、という理屈は理解できるが、3週間寝かせるだけで問題が爆発されるようなシビアな世界なのか？というのも気になるな
ARCならまあありそうだが
2022/11/29(火) 20:42:51.50ID:lNSI2iHV0
ABCのC問題
ST各行の・の数だけカウントして比較してるだけで正解なの何でなん(´・ω・｀)
転置して文字比較じゃないと題意を満たさないと思うんだけど
2022/11/29(火) 20:58:40.10ID:lAj9RF5h0
誤った解答だと思うけどそれでACできるの？
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はならず
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況