競技プログラミング総合スレ 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/20(日) 23:34:20.66ID:/fTD/Y1vM
正直BよりDの方が解きやすいまである
焦った
2022/11/20(日) 23:45:52.50ID:YyouSBGa0
Bとかパッと見かなり簡単そうなのに始点が同じ場合だけ考えれば良いことに気づけないと沼にハマって詰む
2022/11/25(金) 16:38:52.84ID:kkQAdZLCa
ABCの過去の問題見てると昔は簡単だったんだな。
C問題くらいまででも今のBより簡単じゃね？と思える
2022/11/25(金) 16:57:42.32ID:hTLzcQKy0
教材の充実や競争の過熱で、同じdiffでも今の方が難しくなってる傾向はあるよ
2022/11/25(金) 18:53:15.81ID:65rNmeKo0
C++使いが問題作ってるから若干C++に有利だな
専用のライブラリが使えたりするし再帰呼出しとかのC++が苦手そうなやつはスタックオーバーフローしない回数になってるし
2022/11/25(金) 19:01:46.01ID:efHi9BuYa
それはしゃーないわ
2022/11/25(金) 19:11:48.40ID:AeK8Z8vPM
横レスなのだが、
C++って割とstack over flowには強いんじゃないの？
興味ある

C++が優遇されているのは同意
もう少し、Pythonの人へ配慮を…
2022/11/25(金) 20:17:30.79ID:Mr2dT9mK0
常に問題の制約が64bitが前提になってるのがまずけしからんわけだ
64bit整数が扱いやすいなんてC/C++、JavaやGo、みたいなコンパイル前提の言語ばっかじゃん
たまには150bitらへんを制約にするとか
正規表現使えば楽勝みたいな問題をもっと出すべき
2022/11/25(金) 21:26:56.40ID:TF+64huAM
>>569
スタックオーバーフローしない回数なんじゃなくてatcoder上でオーバーフローしないってだけじゃないの

atcoderはスタックサイズ上限無制限にしてあるからmemory limit超えない限り落ちない
2022/11/25(金) 22:03:32.16ID:8L23NX370
ノートPC持ってる人多いのか？
仕事はノートPCだけど会社から貸与されてる仕事用のものだから私用に使えないし、
自分のPCは基本的に自宅でしか使わないからデスクトップで十分だしスペック的にもデスクトップがいい
わざわざPC2台持たないし
2022/11/26(土) 00:15:04.34ID:vVgQhOqy0
あっそ
2022/11/26(土) 12:13:25.49ID:tpvuNJrza
ガイジガイジガイジガイジガイジ
ガイジガイジガイジガイジガイジ
ガイジガイジガイジガイジガイジ
ガイジガイジガイジガイジガイジ
ガイジガイジガイジガイジガイジ
2022/11/26(土) 12:57:16.88ID:Ewhb/nSN0
デスクトップPCはかなり機能強めのものを買って機械学習専用機にしていて、出先とかでも使える用のミドルスペックノートPCを普段使いにしているよ
2022/11/26(土) 20:12:54.37ID:pFdUclXK0
競プロやるかーって思ってたけどなんかいまいち評判よくない感じなので見送り気味。プログラミングする人間に頭でっかちはちょっとダメ＞＜
2022/11/26(土) 22:08:05.48ID:rqdm7zQmr
なんだこいつちょくだいかよって思ったらちょくだいだった
2022/11/26(土) 22:42:27.81ID:UyYZD8yR0
D問題、普通に数学解けないと解けない問題が出てきたな
AC出来たからいいけど
A～Cまでは普段と比べてめちゃくちゃ簡単だと感じた
E問題は問題の意味が分からず、残り２０分でようやく意味が分かって時間的に足りないと思ってそっ閉じ
2022/11/26(土) 22:42:29.80ID:9TWm0K7s0
5完
F頑張ればできそうな気はするが時間切れ
2022/11/26(土) 22:43:41.33ID:UyYZD8yR0
https://imgur.com/a/gd38p1G
緑に近づきますように（レート落ちませんように）
2022/11/26(土) 22:45:47.35ID:UyYZD8yR0
>>581
今日プロ始めたばっかのころ（ここ４カ月以内）
DがとけなくてEが解けたっていういこと一回だけあった

それ以来E一回も解けていない
Eに手が届くレベルまで早くいきたい
584デフォルトの名無しさん (ﾜｯﾁｮｲ bfe2-O5Hl)
垢版 |
2022/11/26(土) 22:57:30.63ID:zgsW6Ywu0
D、最適化ライブラリでどうしても10^-3までしかあわないまま80分とかしてダメ元で投げたら通った・・・
2022/11/26(土) 22:59:44.90ID:UyYZD8yR0
>>584
python?どんなライブラリなのか教えてほしい
2022/11/26(土) 23:03:02.04ID:gLSjA9OV0
d問題で最小値を求めるべき関数、ほんとだったら下に凸なことを証明しなきゃいけないんだろうけど、「導関数が0になるとこ一ヶ所しかないからここが答えやろｗ」って解答しちゃった
2022/11/26(土) 23:04:28.90ID:UyYZD8yR0
>>586
俺も
高校時代だったらすぐに証明できただろうけど
わからなかったからmatplotlibで関数の形見て下に凸だって決めつけてしまった
588デフォルトの名無しさん (ﾜｯﾁｮｲ bfe2-O5Hl)
垢版 |
2022/11/26(土) 23:20:38.01ID:zgsW6Ywu0
>>585
scipyのoptimise
589デフォルトの名無しさん (ﾜｯﾁｮｲ 9f02-zuBb)
垢版 |
2022/11/26(土) 23:29:09.61ID:d01dJOWN0
１年ぶり位に復帰したけどインフレやば過ぎワロタ
三分探索が茶とかもう無理ゲ
2022/11/27(日) 00:02:27.32ID:bVOlLaeO0
別に三分探索しなくても解けるからね
591デフォルトの名無しさん (ﾜｯﾁｮｲ bfe2-O5Hl)
垢版 |
2022/11/27(日) 00:11:00.75ID:BLocM/7p0
手計算したくないから、回答と少し違うwolfram先生の解析解の周辺の最小値でやったけど、最後のサンプルがどうやってもあわなくscipyに。実務家的ｗには脳死でoptimize一択。
592デフォルトの名無しさん (ﾜｯﾁｮｲ bfba-Tatu)
垢版 |
2022/11/27(日) 00:29:03.57ID:55T6iy040
Dで10^18制約で誤差10^-6無理じゃね？と思ったら絶対誤差または相対誤差って書いてあることに気付いた
ひょっとして今までの問題も全部そうだったのか
593デフォルトの名無しさん (ﾜｯﾁｮｲ 9fbd-J0r1)
垢版 |
2022/11/27(日) 00:30:45.88ID:GvaDwkJ10
Python しか触ってないからわからないんだけど
他のCとかだと誤差が大きくなって3分探索とか使わないといけなくなるもの？
594デフォルトの名無しさん (ﾜｯﾁｮｲ 9fbd-J0r1)
垢版 |
2022/11/27(日) 00:34:30.35ID:GvaDwkJ10
>>592
微分して0になる点の整数インデックスさえ求められれば
そこからプラマイ5くらいずらして最小値を求めてばいいと思うけど
俺はPythonでインデックスとインデックス＋1の最小値で求めることできたけど
ってか代数的に解ける問題が出てくるんだなってびっくりした
2022/11/27(日) 00:38:57.81ID:14KOziN70
せっかくデ/アのスキルを磨ける競プロをやってるんだから、代数解法よりも三分探索を使って解いてほしいところ
まあ競技的にはとにかく解ければ勝ちなんだけど
596デフォルトの名無しさん (ﾜｯﾁｮｲ 9fbd-J0r1)
垢版 |
2022/11/27(日) 00:42:37.70ID:GvaDwkJ10
>>595
計算量を考察する箇所でも代数的な考察するし

代数だけではどうしようもないということを頭でしっかり認識してからパズル的に解くのが醍醐味だと思うんだけど
2022/11/27(日) 00:44:19.50ID:14KOziN70
>>593
想定解法であれば、3分探索で絞り込むのは「操作回数」だから、誤差が代数解法よりも小さくなるわけではないよ
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
そういう事ね、とりあえず遊びでやってみるか
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況