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

競技プログラミング総 ..

586:デフォルトの名無しさん
22/11/27 00:44:19.50 14KOziN70.net
>>582
想定解法であれば、3分探索で絞り込むのは「操作回数」だから、誤差が代数解法よりも小さくなるわけではないよ

587:デフォルトの名無しさん
22/11/27 00:46:09.44 14KOziN70.net
そうだね、そら何にしても数学は使うよ
デ/アはそもそも数学が下地にあるからね

588:デフォルトの名無しさん
22/11/27 00:47:05.59 GvaDwkJ10.net
>>586
誤差の部分よくわからんのよね
どのくらいの誤差が起こり得るのかが
コンピュータの深い部分か何かしらの知識があればわかるんだろうけど
FFTで誤差が出ないから、とりあえず実用範囲で小数計算の誤差は考慮してないな
それだけPythonが数値計算で有能なのかも知れないが

589:デフォルトの名無しさん
22/11/27 00:47:32.02 GvaDwkJ10.net
>>587
デ/アって何？？

590:デフォルトの名無しさん
22/11/27 00:51:50.68 14KOziN70.net
>>588
きみは何らかの代数ライブラリを使ったのかもしれないけど、おれが「代数解法」と呼んだのは公式解説にある「解法2　微分」のこと
「解法1　三分探索」でも「解法2　微分」にしても、どちらにしても最小値になる回数を見つけてからの計算方法はほぼ同じだから、同じ精度で答えが出力される
よって誤差は関係ない
 >>589
データ構造とアルゴリズム

591:デフォルトの名無しさん
22/11/27 00:53:59.03 GvaDwkJ10.net
>>590
俺は微分したけど、3分探索はわからないけどLogNとかになるのだとしたら微分したらO(1)だと思うからそっちの方が速そうだけどな

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

592:デフォルトの名無しさん
22/11/27 00:55:09.30 vTtL7Ko7M.net
>>589
データ構造/アルゴリズムの略

593:デフォルトの名無しさん
22/11/27 00:56:10.24 GvaDwkJ10.net
>>592
解説聞いたらわかったけど、初見じゃわからんかったよ

594:デフォルトの名無しさん
22/11/27 00:58:54.64 14KOziN70.net
すまんな、競プロの界隈だとデ/アってよく使うから当たり前に使っちゃうわ

595:デフォルトの名無しさん
22/11/27 00:59:07.32 GvaDwkJ10.net
数学が下地にあるのは確かだけど、日本の学校教育では出てこないようなパズル問題が出てくるところが競プロの好きなところ

596:デフォルトの名無しさん
22/11/27 01:00:50.63 GvaDwkJ10.net
>>594
常識だったのか。スラッシュあまり使わない俺はあまり馴染まないかも知れない(と言って1週間後使ってるかもしれない)
競プロ初心者高卒だから、そういう界隈の言葉どんどん教えてくれると嬉しい

597:デフォルトの名無しさん
22/11/27 01:06:28.84 vTtL7Ko7M.net
いや、ただのTwitterスラングやで
わからんくて当たり前

598:デフォルトの名無しさん
22/11/27 01:16:51.24 vTtL7Ko7M.net
まあプログラマーは一応理工系技術職だし、高校理系標準レベル微積ぐらい扱えた方がいいと思うぜ

599:デフォルトの名無しさん
22/11/27 01:35:50.76 j8v2EUX60.net
理系ならフォートランつかえ

600:デフォルトの名無しさん
22/11/27 02:20:45.46 BLocM/7p0.net
ワテが3分探索を使わない理由は
・最適化の本で見たことがない
・多次元に拡張できない、教プロ特有な気がするので学習モチベがわかない
こんなところか・・・

601:デフォルトの名無しさん
22/11/27 05:04:19.20 dLcFXUTDM.net
今回は入力が整数だから二分探索のが分かりやすい気がした
めぐる式でf(x)とf(x+1)を比較して大きいならok、そうでなければng
最後にf(ok)を出力するだけ

602:デフォルトの名無しさん (ｱｳｱｳｳｰ Sa5b-DgGg)
22/11/27 08:39:17.72 uzn6bbq2a.net
下に凸と想定して二分探索で解けたよ

603:デフォルトの名無しさん
22/11/27 11:51:36.21 l4mu+o+5a.net
きんたま

604:デフォルトの名無しさん
22/11/27 13:33:50.96 BTSTHwm10.net
>>597
コンピュータサイエンス用語でもない競プロスラングなんだからわからんのが当然だとは思うけど、「競プロの界隈だと」と言ってるのに高卒だからと関係ないことを言い始めるあたりの理解力はちょっと怖い

605:デフォルトの名無しさん
22/11/27 16:09:24.87 BResG1CfM.net
無学なものですが、的な表現なんじゃないか
そういう卑下は別にせんでいいとは思うがな
大卒でもプログラミングも競プロもずっと分かってないやつ五万といると思うわ

606:デフォルトの名無しさん
22/11/27 22:31:30.18 NlD2vvTh0.net
>>604
高卒の俺でもある程度頑張ってるよって言いたかっただけ
あと、高卒ってベースとなる知識が圧倒的に少ないと感じてるからスラングでもなんでも、そういう中に考え方が潜んでるからそれを学びたいっていう気持ちがあっただけだよ

607:デフォルトの名無しさん (ﾌﾞｰｲﾓ MMcf-tDK4)
22/11/28 17:33:31.00 /fwLD4AIM.net
二分探索って初期値(左と右の)の設定難しくね？
279_dは解の範囲考えてるときに微分すること思い付いた。

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

608:デフォルトの名無しさん
22/11/28 21:02:15.01 GQvoQd/h0.net
計算がおかしくならないならでかい値でもよい
難しい考察なしで0からAにしてAC

609:デフォルトの名無しさん
22/11/28 21:11:23.21 WdPNyywH0.net
AGC、12月25日に入ったね
それ自体はめでたいことだけど、もうちょっと間隔をバラした方がありがたいような
そしてクリスマスという

610:デフォルトの名無しさん
22/11/28 23:37:01.00 d041iZGN0.net
>>608
二分探索で解けることはちっとも明らかじゃないと思うんだがなんで二分探索で解けるの？
URLﾘﾝｸ(atcoder.jp)
これと同じ解き方？

611:デフォルトの名無しさん (ﾌﾞｰｲﾓ MM8f-/8MR)
22/11/29 02:57:37.73 fS7qvBJwM.net
実際クリスマスだからといって何か予定入れることあるかね？

612:デフォルトの名無しさん
22/11/29 08:51:22.57 iOy5VXiNM.net
ギャグ抜きにして海外勢も予定入ってるやつ多そうだし、正直どういう判断でクリスマスに入れようと思うのかよくわからんわ

613:デフォルトの名無しさん
22/11/29 11:29:42.82 Ka2TzeUEa.net
ようやく問題が揃ったってだけじゃね
寝かせてると他で使われちゃうから新鮮なうちに出さないと

614:デフォルトの名無しさん
22/11/29 11:56:47.92 Xod1Eynpa.net
>>610
下に凸ということがわかれば二分探索で解けることは明らかなんじゃね
接線の傾きが右上がりもしくは水平になる最小の値を調べればいい
つまり右下がりなら前半を捨てて右上がりなら後半を捨てるの繰り返し
初期範囲は0からAで行けるしその倍でも比較が一回増えるだけ

615:デフォルトの名無しさん
22/11/29 11:57:21.09 TK2MqA+bM.net
クリスマスって年間のイベント日の中でも tier 高いんですか？祝日ですらないけど

616:デフォルトの名無しさん
22/11/29 11:57:42.28 Xod1Eynpa.net
>>612
競プロデートすればいいじゃん

617:デフォルトの名無しさん
22/11/29 12:03:28.49 QobrmxBH0.net
>>614
ああ、傾き使ってるなら納得

618:デフォルトの名無しさん
22/11/29 13:55:24.58 Ka2TzeUEa.net
自分は傾きでなくマイナス1とプラス1の値で比較したから合わなかったんだな
gの変化が1ずつだからってそれでは駄目なんやね
3分探索も知らなかったけど色々勉強になって面白かった

619:デフォルトの名無しさん (ｻｻｸｯﾃﾛ Spcb-YcqY)
22/11/29 14:59:09.55 FcjH27v8p.net
AGCを積極的に求めてる程競プロに入れ込んでる層はクリスマスなんかに予定が入ってるわけないだろうと足下を見られてるな

620:デフォルトの名無しさん
22/11/29 17:05:58.54 ftmXQiba0.net
例年クリスマスコンあるし今更すぎる

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

622:デフォルトの名無しさん
22/11/29 18:38:45.42 sxQd4OITM.net
海外勢にこそアピールしたいAtCoder最高コンテンツのはずのAGCとクリスマスコンテストを同列に語られても

623:デフォルトの名無しさん
22/11/29 18:47:34.27 sxQd4OITM.net
問題が爆破されないように、という理屈は理解できるが、3週間寝かせるだけで問題が爆発されるようなシビアな世界なのか？というのも気になるな
ARCならまあありそうだが

624:デフォルトの名無しさん
22/11/29 20:42:51.50 lNSI2iHV0.net
ABCのC問題
ST各行の・の数だけカウントして比較してるだけで正解なの何でなん(´・ω・｀)
転置して文字比較じゃないと題意を満たさないと思うんだけど

625:デフォルトの名無しさん
22/11/29 20:58:40.10 lAj9RF5h0.net
誤った解答だと思うけどそれでACできるの？

626:デフォルトの名無しさん
22/11/29 20:59:15.21 lAj9RF5h0.net
誤った解答というのは「ST各行の・の数だけカウントして比較」の話ね

627:デフォルトの名無しさん
22/11/29 21:00:15.27 RxTn59Tk0.net
それが落ちるケースなかっただけでは

628:デフォルトの名無しさん
22/11/29 22:07:29.73 FB4pDqos0.net
テストケースが弱いことなんてしばしばあるし

629:デフォルトの名無しさん
22/11/29 23:04:14.45 VWoS6vwd0.net
マルチテストケースにしてNが小さいところは全部入れれば簡単にテスト強くなるけど
AtCoderはやらないよね

630:デフォルトの名無しさん
22/11/30 00:12:33.13 9qvj+6epa.net
>>624
転地しないと駄目なのはaftercontest 追加されてたけど
点の数だけで通るってマジ？

631:デフォルトの名無しさん
22/11/30 09:53:36.46 apN+BzVh0.net
いつも思うんだけど、そういう作問の不備らしき問題ってどこに通報すればいいの？

632:デフォルトの名無しさん
22/11/30 13:22:48.31 5wsyQllOr.net
ちょくだいにリプ爆しろ

633:デフォルトの名無しさん
22/11/30 14:34:30.64 apN+BzVh0.net
ブロックされそうでこわい

634:デフォルトの名無しさん (ｱｳｱｳｳｰ Sa5b-RMO3)
22/11/30 15:07:15.45 Pc+r2fg0a.net
マジでTwitterくらいしかないよね
外国の人かわいそう

635:デフォルトの名無しさん
22/11/30 17:02:31.77 aIG6S061a.net
解説と同じアルゴリズムだと通るのに愚直に解くとWAになることがあって悩んだことがある
TLEならともかくWAになるはずなかったんだがなあ
なにせ1000000007で割った余りを書きましょうという問題で全部BigDecimalで計算して最後に一度だけ割る解法だったし

636:デフォルトの名無しさん
22/11/30 18:55:40.36 o5YY8Hyda.net
へえそうなの
大変だったね

637:デフォルトの名無しさん
22/11/30 21:04:42.76 +1VZTiuO0.net
質問するならコードを貼れ
通らないならどっか間違ってんだろとしか言えん

638:デフォルトの名無しさん
22/12/02 14:05:45.12 u1vu+Orua.net
AIに問題文投げただけで正答のコード返してくれるようになったら競プロは終わるのか？

639:デフォルトの名無しさん
22/12/02 15:11:52.86 U3+Z10Mra.net
灰茶は完全に死んだね

640:デフォルトの名無しさん
22/12/02 20:08:44.19 Nb3LXSL90.net
クリスマスはAGC🤓

641:デフォルトの名無しさん
22/12/03 21:56:16.75 JyCxq0uSM.net
クリスマスにちなんだスペシャル問題が出るんだろうな。

642:デフォルトの名無しさん
22/12/03 22:40:01.18 Uhw018620.net
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:無視するだけ

643:デフォルトの名無しさん
22/12/03 22:44:01.02 IWvgV3l70.net
Fで無駄にLCA持ち出して距離を求めようとしたせいで時間浪費したのマジで勿体無くて泣ける　
LCAの項が打ち消されるのに

644:デフォルトの名無しさん
22/12/03 22:45:54.74 kk6HaUaJ0.net
C簡単すぎてびびったわ(´・ω・｀)
Dは素数の問題だとわかったが何故かいつまてまでも数個ACせんかった(´・ω・｀)

645:デフォルトの名無しさん
22/12/03 22:46:49.20 VCZIA7Uqp.net
今回はFまでの早解き回だったね　自分もカンストしてみたかった

646:デフォルトの名無しさん
22/12/03 22:47:06.24 UdtoWZb20.net
22:40:00に正解しても得点入らないの

647:デフォルトの名無しさん
22/12/03 22:53:22.87 Uhw018620.net
重み付きUnionFindってなんだろう
しらんけど同じようなことをおれは実装してたのかな

648:デフォルトの名無しさん
22/12/03 22:53:50.52 ScHASUx3a.net
小数点以下が切り捨てられて表示されていて実際の提出時刻は22:40:00を僅かに過ぎていたのか
あるいはコンテストの開催期間は[21:00, 22:40)だったのか

649:デフォルトの名無しさん
22/12/04 09:19:17.67 pM2FPSpOa.net
これってカンニングやり放題だと思うんだけど意味あるの？
昔は会場で受けてた？

650:デフォルトの名無しさん
22/12/04 09:30:54.97 pM2FPSpOa.net
転職の武器になるかな？って思って調べるけどよくわからない
ここのスレ見てても転職できたという報告は全然ないね
募集枠はあるけど採用されないように見えるね

651:デフォルトの名無しさん
22/12/04 10:29:38.14 cWum1xSPa.net
>>649
賢い友人いればカンニングし放題だよ

652:デフォルトの名無しさん
22/12/04 10:47:16.13 byXjLF2m0.net
遊んでた結果副次的に転職出来たらラッキーくらいに思っておくのが賢明でそもそも転職目的で取り組むものじゃない定期

653:デフォルトの名無しさん
22/12/04 12:28:16.09 pM2FPSpOa.net
そういう事ね、とりあえず遊びでやってみるか

654:デフォルトの名無しさん
22/12/04 14:23:01.52 NAhGf0YwM.net
ChatGPTが解けてるのはただ単に問題文覚えているからだと思うが、AGCの新問を解けるようになったら革命起きそうだな

655:デフォルトの名無しさん
22/12/04 14:23:58.59 c/97lm9K0.net
1万文字をcinで入力して、文字列長を調べたら4095と表示されてしまいました
何故でしょうか？(´；ω；｀)

656:デフォルトの名無しさん
22/12/04 14:45:43.34 QAdxD5oY0.net
だからコードを貼れと

657:デフォルトの名無しさん
22/12/04 16:28:54.17 9++0/IB+0.net
途中に空白があって全部入力できてなかったとか

658:デフォルトの名無しさん (ｱｳｱｳｳｰ Sa3a-wvAz)
22/12/04 17:53:44.19 pM2FPSpOa.net
昨日の問題EのcriticalHitがよくわからないんだけど
解説にatcoderのincludeファイルがあるんだけどなんだこれ？
PとQ求めたらこのファイル使うと勝手に計算してくれるの？

659:デフォルトの名無しさん (ﾃﾃﾝﾃﾝﾃﾝ MM34-wjaL)
22/12/04 17:56:34.68 NAhGf0YwM.net
chokudai「あれ、AGCも典型じゃね？」

660:デフォルトの名無しさん (ﾜｯﾁｮｲ f8a4-77kT)
22/12/04 17:57:37.82 CGY/STbk0.net
それはAtcoder LibraryっていうAtCoderのジャッジで使えるライブラリなんだけど、初心者には明らかに説明不足だね・・・

661:デフォルトの名無しさん
22/12/04 18:03:15.78 pM2FPSpOa.net
>>660
つまり、高速でPとQを解かせるのが本題で、
mod計算はライブラリがあるからそこで時間つかうなよ！って事かね？
使わないと困るケースがあるんだろうけど...理解せずに脳死で覚えた方が良いんかな？

662:デフォルトの名無しさん
22/12/04 18:04:20.29 NAhGf0YwM.net
この手のDPにACLの出番あるのかと思ってみたけど、modintか

663:デフォルトの名無しさん
22/12/04 18:06:53.79 NAhGf0YwM.net
>>661
別にACL使わなくても自分でスクラッチしてどうにかなるレベルだけど、負になったときの処理とかがめんどいから使った方が楽って感じのノリ

664:デフォルトの名無しさん
22/12/04 18:09:27.71 CGY/STbk0.net
そうだなあ
ACLで実装されてるのは有名アルゴリズムばかりで、ABCでもよく出題されるの多いからライブラリで実装されてるものは理解したほうがいい
ACLは使ってもいいし、使わなくてもいい
まあ、とりあえず問題が解ける程度には理解して使えるようになることをオススメしておくか
特にmodintは便利だと思う
ACLをローカルにインストールすれば、自分のパソコンからも使えるよ

665:デフォルトの名無しさん
22/12/04 18:12:21.58 CGY/STbk0.net
ちなみにおれはC++使ってないし、そういうライブラリは一通り自分で作ってる

666:デフォルトの名無しさん
22/12/04 18:14:00.78 NAhGf0YwM.net
休日でぼーっとしすぎて頭が痛い
何かしらウォームアップするか、逆に仮眠取るかしないとAGCやばい気がする

667:デフォルトの名無しさん
22/12/04 18:16:11.55 CGY/STbk0.net
>>666
休日の片頭痛は、だいたいカフェイン不足が原因だろうから、カフェイン摂っておけば治るというのが自説

668:デフォルトの名無しさん
22/12/04 18:24:50.23 NAhGf0YwM.net
モンスター爆飲みやなー
翌朝の予定とかもう関係ないね

669:デフォルトの名無しさん
22/12/04 20:00:57.71 9++0/IB+0.net
分数をmodで表現する方法が分からなくて解説見に来た人が何も分からないままだから、「modでの計算はたとえばACLを使うことで求めることができます」みたいな一文とともにACLドキュメントへのリンク欲しいね
そもそも新しく入ってきた人はACLの存在知らないだろうし

670:デフォルトの名無しさん
22/12/04 20:09:31.79 EaAmvHmj0.net
小数点の既約分数表現だか、理解するモチベーションが全然わからない

671:デフォルトの名無しさん
22/12/04 20:18:03.95 YKYxvH3hp.net
分数のmod表現は最初は数字が非直観的で戸惑うかもしれないけど、やってることは全然難しくないからACL使用前提じゃなくて普通に理解すべき
逆元と繰り返し2乗法理解してれば一瞬で書けるし

672:デフォルトの名無しさん
22/12/04 20:40:00.50 c/97lm9K0.net
>>656
>>657
普通のコードです
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;
}

673:デフォルトの名無しさん
22/12/04 20:48:19.58 pM2FPSpOa.net
>>672
intで足りてる？

674:デフォルトの名無しさん
22/12/04 20:50:00.93 c/97lm9K0.net
>>673
intって32ビットですよね？
でしたら足りてます

675:デフォルトの名無しさん
22/12/04 20:53:07.80 pM2FPSpOa.net
足りてるなら言う事無いですね。

676:デフォルトの名無しさん
22/12/04 20:59:50.43 CGY/STbk0.net
>>672
ちゃんと10000って表示できるよ
URLﾘﾝｸ(ideone.com)
だからコードじゃなくて、コマンド操作の方法に問題があるんでしょ

677:デフォルトの名無しさん
22/12/04 21:06:26.43 c/97lm9K0.net
>>675
ありがとうございます
 >>676
サクラエディタで１万文字を２行分書いて、それをCtrl＋Aでコピーして
VSCodeに右クリックでペーストしました
この作業で文字がカットされている可能性がありますね
ありがとうございます！！

678:デフォルトの名無しさん
22/12/04 21:07:30.39 pM2FPSpOa.net
入力文字列が怪しそう

679:デフォルトの名無しさん
22/12/04 22:09:18.30 dd1ttyO10.net
期待値の問題ってワンパターン過ぎじゃ、、？
単に水色だとこんなもんで青黄の期待値問題はもっと複雑なの？

680:デフォルトの名無しさん
22/12/05 00:16:09.04 9VPmC7c9M.net
今回BよりAの方がずっと発想ゲーに感じた

681:デフォルトの名無しさん
22/12/05 00:29:08.62 dZQIdR+h0.net
同じ二完でも遅いと全然パフォ伸びないな
絶妙な解きにくさで、ああAGCだなと思った

682:デフォルトの名無しさん
22/12/05 00:35:10.61 9VPmC7c9M.net
>>679
そもそも水diffのDPは丁度EDPCで見るようなレベルだから、実際パターン少ない
もちろん上のdiffで典型度低くて難しい期待値問題はたくさんある

683:デフォルトの名無しさん
22/12/05 00:41:25.45 dZQIdR+h0.net
Aみたいなのは発想でどうにかするより逆順で実験する方が安定するよ

684:デフォルトの名無しさん
22/12/05 01:08:41.64 FvIGflqWr.net
期待値という概念の扱いに慣れてない低学歴が引っかかるから簡単でもdiffは上がる

685:デフォルトの名無しさん
22/12/05 01:09:31.17 gVdVhqi2p.net
青上位　青上位　赤　銅　銀　AC0
は草　
もうレーティング対象青からでも良いんじゃないか

686:デフォルトの名無しさん
22/12/05 01:26:14.28 wV6tNweHa.net
atcoder jumperは下回ったな
A問題最高diffはならず

687:デフォルトの名無しさん
22/12/05 01:29:24.67 ypvg8sem0.net
配点からしてAがむずかしめなのは予想できたし、まあ
水色くらいの人たちならそんぐらい自己判断できるし、まあ水色以上Ratedで良いと思うけどね
それよりARCを3200くらいまでRatedにしてあげたら？って気がしちゃう

688:デフォルトの名無しさん
22/12/05 03:02:28.71 OFDKazG70.net
操作を繰り返して全て同じにしたいときに隣接要素が異なる箇所の個数の変化を考えるのは典型な気がする
Bが重くてつらかった

689:デフォルトの名無しさん
22/12/05 10:20:45.99 DqBKeem4M.net
それは考えたけどほぼ常に2個ずつ減らせるとはわからんかった

690:デフォルトの名無しさん
22/12/05 10:44:48.54 pY2jkv26p.net
下界/上界が必ず達成できる典型という奴だな
自分はABCABC型が3回で揃えられることすら見逃してたせいで詰んでた

691:デフォルトの名無しさん
22/12/05 11:48:54.61 9VPmC7c9M.net
異なる文字同士が隣接している部分の特徴量として使おうってのはまあすぐ思いつくしそれはそこまでの発想じゃないと思うが、ABCABC三回とかがコンテスト中だと意外とソラで気付けない
そうこうしてるうちに別の方針に飛んだりしてかなり時間食う
一方Bは下界と上界がすぐ見えるし、700点問題にしては木となもりの関係性と似ていることに思い至るまでにそんなに飛躍はないように思う
実装パートの方がつらい
その結果が正答数逆転だわ

692:デフォルトの名無しさん
22/12/05 11:49:40.54 9VPmC7c9M.net
>>691
☓部分の
○部分の数を

693:デフォルトの名無しさん
22/12/05 12:49:21.04 xHOM0phNM.net
わかるわ
B発想の割に普通に実装が重い
時間経過でどんどんAC数増えるのも納得

694:デフォルトの名無しさん
22/12/05 13:44:54.25 6+3fZaFZp.net
愚直コードを書いてパソコンに実験させるのが良かったんだろうけど、これくらいの問題なら紙に書いて実験するので大丈夫だろうと高をくくって最小回数を勘違いしてたせいで一生WAが出て地獄だった
パソコンに実験させる習慣が未だにつかない

695:デフォルトの名無しさん (ﾜｯﾁｮｲ f1bd-WJTY)
22/12/05 17:25:12.72 dZQIdR+h0.net
自分もどちらかというと移動中の微妙なスキマ時間に競プロの問題を考えることが多いから、実験はそんなに得意ではないかなあ
高難易度ほど予想解きスキルが必要そうだから、ARC/AGCで戦うのなら練習した方がいいかもね

696:デフォルトの名無しさん
22/12/05 19:41:46.19 MF+Ck4c20.net
AGC、診断人氏が0完とか、もう一般的にかなり優秀な人ですら出れるレベルじゃないのかｗ

697:デフォルトの名無しさん
22/12/05 19:52:29.46 ypvg8sem0.net
水色の底辺なら0完でも温まってるから、逆にレート低いほど出るべき

698:デフォルトの名無しさん
22/12/05 20:16:56.33 F8Lb9jYBp.net
昨日みたいな簡単な問題が無い回だと本書いてる人や赤コーダーみたいな高レベルの人でも0完しちゃうことあるんだなってびっくりした

699:デフォルトの名無しさん
22/12/05 22:13:27.51 dZQIdR+h0.net
AもBも感覚だと普段のABC-Gより難しかったから、0完でも凹まなくていいと思うよ

700:デフォルトの名無しさん
22/12/06 00:38:56.11 2yqxdiTAM.net
赤の0完は流石に戦略やろ
一定時間かけてダメだったら後ろに賭けるしかない
まあ赤でも瞬殺できるわけではない問題だったのは確かだが

701:デフォルトの名無しさん
22/12/07 18:26:11.90 +RxBvimqM.net
赤からすると、終了30分前にA問題解いたとて、って感じだろうからな
最後のギリギリまでC以降に賭けた方がいい

702:デフォルトの名無しさん
22/12/07 20:38:58.44 KlMxIGrW0.net
競プロスレおやすみ～😪今日は少し精進した

703:デフォルトの名無しさん
22/12/07 22:37:11.32 fRJGzVLy0.net
プログラマー板のスレはもうめちゃくちゃだね

704:デフォルトの名無しさん
22/12/07 22:42:32.97 K0BDAES80.net
見に行ったけどなんかすごいことになってた

705:デフォルトの名無しさん
22/12/07 22:50:56.68 K0BDAES80.net
0完で水パフォってところから、AGCのrated制限ってかなり絶妙に設定されてると思ったね
年6開催のころに仮に同じ難易度、all ratedだったら、参加し続けることで一年すべて0完でも緑ぐらいには行きそう

706:デフォルトの名無しさん
22/12/07 23:03:19.10 mi/jvoGH0.net
良い子はあんなスレ見に行っちゃいけません

707:デフォルトの名無しさん
22/12/07 23:22:27.97 K0BDAES80.net
そういえば、この前のAGC-A、最初解法ガチャでMoじゃないか？とか考えたんだけど、それでもできるのかな

708:デフォルトの名無しさん (ｻｻｸｯﾃﾛ Sp88-UA8M)
22/12/07 23:27:50.37 0gV/yTHUp.net
MoチラついたけどA問題でMoが想定解なわけないしな……って思ってすぐ却下しちゃった
テストケース次第では間に合うのかな

709:デフォルトの名無しさん (ﾃﾃﾝﾃﾝﾃﾝ MM34-wjaL)
22/12/07 23:34:14.34 +RxBvimqM.net
想定解を知ったあとだとMoでACできる遷移はすぐ作れる気がするが、それって本質的にMoのおかげで解けたことにはならないんだよな
てかその遷移に思い至るんならMo使わんやろっていう

710:デフォルトの名無しさん (ﾃﾃﾝﾃﾝﾃﾝ MM34-wjaL)
22/12/07 23:35:50.85 +RxBvimqM.net
メタ的にもAGCのAでMoはないだろうし

711:デフォルトの名無しさん
22/12/08 00:19:44.81 qo7J5oAL0.net
昔直大が998244353なら使えるアルゴリズムが1000000007で使えないことがあるのでメタ読み対策で998244353使う的なこと言ってた覚えあるけど具体的に何があるの？
998244353使ってる問題解いてて気になった

712:デフォルトの名無しさん
22/12/08 00:20:24.69 qo7J5oAL0.net
>>950
!extend:checked:vvvvv:1000:512
!extend:checked:vvvvv:1000:512
テンプレからコマンド消えてるのでテンプレに追加してください

713:デフォルトの名無しさん
22/12/08 00:33:13.01 TyHoBXE/0.net
>>711
ACLにもなってるこの畳み込みは 10⁹+7 だとあまり使い物にならない
このアルゴリズムを使うときはほぼ確実に998244353が指定される
URLﾘﾝｸ(atcoder.github.io)

714:デフォルトの名無しさん
22/12/08 00:34:54.52 QbzOT+5k0.net
>>711
畳み込み演算を高速化するFFTの亜種で、数論変換というのがある
普通のFFTは複素数を使うけど、数論変換はずっとmod pで計算するから精度上の問題が生じないのがメリット
p-1 = 2^m * dみたいな形で書いたときにmが大きいpほど扱いやすく、998244353は大きくて、1000000007は小さいから、そこで数論変換を使うかどうかがバレやすい的な話

715:デフォルトの名無しさん
22/12/08 00:38:01.86 QbzOT+5k0.net
>>708
やっぱ一回は思い浮かぶよね
そんなに単純な解だと思わなかったし

716:デフォルトの名無しさん (ﾜｯﾁｮｲ 3f7c-rBUd)
22/12/08 05:37:05.87 JblDKfrH0.net
そもそも1クエリ固定の場合を解けないと話にならなくて、セグ木やらMoやらを考えるのはそのあとでないか

717:デフォルトの名無しさん
22/12/08 10:57:49.64 DNmDkQyIM.net
解既知区間を左右に1伸長したときにまた高速で解を求められれば一クエリでも多クエリでも対応できるから、そこに絞ってまず思考してみるというのも戦術としてはあるだろ
帰納的に考える方が多くの場合少ない思考リソースで問題解けたりするし

718:デフォルトの名無しさん
22/12/08 12:32:11.43 JblDKfrH0.net
言ってることようわからんが結局1クエリ解くことから始めてない？

719:デフォルトの名無しさん
22/12/08 13:06:21.88 bAy1n42uM.net
その1クエリを解くにあたり、Moで多クエリでも高速で処理することを見据えて、1クエリの解を伸長で構成することを試してみるって話
一方、セグ木で解くことを見据えるなら、モノイド性をどこかで見出して区間を併合しながら1クエリの解を構成できないか考えてみるというアプローチになる
メタ的には、多クエリで高速で解ける以上は、1クエリの解き方も限定されてくるだろうって考え方だな
別に数学的知見じゃなくて、ただの問題解く手順のお気持ちみたいなもんだから、わからないんならわからんでいいよ

720:デフォルトの名無しさん
22/12/08 13:14:19.81 bAy1n42uM.net
前回のAも、「多クエリを高速で処理できるんだから簡単な区間の特徴で1クエリ分解けるだろう（そもそもAGC-Aだし）」で想定解に至った人も割といるんじゃないか思っているが、発想的にはそれと似たようなものだと思うわ

721:デフォルトの名無しさん
22/12/08 14:18:33.85 sJ8eTx33a.net
区間の伸長が高速にできるなら、解が自明な長さ0や1の区間から始めるだけでは

722:デフォルトの名無しさん
22/12/08 14:28:51.79 QbzOT+5k0.net
自分がMoを考えたと言ったのは、1クエリ解くにしてもDPみたいに漸化式作れたらやりやすそうだからと思ったからかな
もちろん最初のクエリの答えは自明な区間から出発するよ

723:デフォルトの名無しさん
22/12/08 16:31:38.77 qo7J5oAL0.net
なおだいブログ曰くchatGPT使っていいらしいな
Cまでしか解けないしなんか問題文を変換しなきゃいけないらしいから茶以上だと意味ないけど

724:デフォルトの名無しさん
22/12/08 16:37:54.78 tY+Rj1vk0.net
適当に自動化してA、B、CをChatGPTに瞬殺してもらって良いってことなの？

725:デフォルトの名無しさん
22/12/08 16:46:31.91 tY+Rj1vk0.net
3問目まで自動で解いてくれるなら5分ぐらいは節約できるし多少はパフォ上がるかな

726:デフォルトの名無しさん
22/12/08 17:27:26.68 qo7J5oAL0.net
twitterから拾ってきたやつだけど
・英語版の問題文を与える
・数式等をTeXで書く(A_i, 10^2など)
・入力と出力の例を与える
・AtCoderの問題であることを教える
・Pythonで書かせる
必要があるっぽいから普通に解いたほうがいい気がするな

727:デフォルトの名無しさん
22/12/08 17:31:25.35 tAYudyq3a.net
まだ発展途上とは言えイラストAIもあっちゅう間だったしな。
もう俺みたいな底辺は解く楽しさしか残らねーわ。

728:デフォルトの名無しさん
22/12/08 17:49:40.32 bAy1n42uM.net
>>726
TeXへの変換規則さえちゃんと考えてコーディングしておけば、後は自動化できそうな感じもするな

729:デフォルトの名無しさん
22/12/08 17:54:32.49 bAy1n42uM.net
これからはAIをうまく使う力が重要なのであれば、練習としてそういう解き方を研究するのもありだと思ってるわ

730:デフォルトの名無しさん
22/12/08 18:06:46.91 05iO3Ijva.net
それってデータエンジニアじゃん！
Kaggleじゃん！

731:デフォルトの名無しさん
22/12/08 18:15:38.61 qvBkrjzGp.net
kaggle定期的にやりたくなるけど競プロ諸々との両立が難しくて毎回挫折する

732:デフォルトの名無しさん
22/12/08 22:15:49.90 LtNnKYdG0.net
健常者スレおやすみ🥱

733:デフォルトの名無しさん
22/12/09 07:42:08.88 NQJZdVld0.net
健常者スレおはよう🥱寒いね

734:デフォルトの名無しさん
22/12/09 15:37:29.25 JIsCFDDpM.net
Kaggleって機械学習モデルの精度競争的なイメージが強いけど、AIツールを活用した作業効率化みたいなイメージで話してた

735:デフォルトの名無しさん
22/12/10 12:50:59.26 FEPL+5PW0.net
健常者スレおはよう🥱今日はABCだね

736:デフォルトの名無しさん
22/12/10 16:56:35.59 +Gv2eYfg0.net
ChatGPTをAtCoderのコンテストで使用することが認められるならコンテスト出ないって人を見かけたけど、いまはまだ茶色程度の実力だけど、
仮に暖色程度の実力を備えた競プロAIが登場したとして、AtCoder公式から使用を認められたら、どう反応する人が多いか気になる

737:デフォルトの名無しさん
22/12/10 20:31:32.99 Ns16Znepd.net
まだ未参加なのですが過去問ABCのABまでしか解けないとして参加する意味ありますか？
あとABだけ解けて茶色行けますか？

738:デフォルトの名無しさん
22/12/10 20:44:33.79 TTumudvvd.net
コンテストになれば普段より集中して問題に取り組めるので参加する意味はあります
また参加回数が少ないとレーティングに補正がかかって低くなる仕組みもあります
ABだけでは茶色にはなれません

739:デフォルトの名無しさん
22/12/10 20:45:06.16 9Qn6ryF90.net
>>737
英検とかと違って無料で参加できる実戦だから、練習になるし意味あるよ
強いひとはAtCoder以外にもいろんなコンテストに毎週たくさん参加してたりするよ
ABだけで茶色は無理かな
茶色にいくならCまで余裕もって解いてくださいな

740:デフォルトの名無しさん
22/12/10 20:49:39.55 uF1Xgf00a.net
>>736
URLﾘﾝｸ(www.businessinsider.jp)
この前こんな記事読んだんだけど、やっぱりChatGPTは「考えて答えている」んじゃなくて「それっぽい文字列を吐いているだけ」みたいだから、これからよほどのパラダイムシフトがない限り暖色程度の実力を備えた競プロAIは無理じゃないかな
まあそのパラダイムシフトに立ち会ってみたい気もするけど
 >>737
本番の時間制限あるなかで考えるのも楽しいし、やってみればいいと思うよ

741:デフォルトの名無しさん
22/12/10 20:59:17.91 Ns16Znepd.net
>>738-739
ありがとうございます
練習で参加してみます

742:デフォルトの名無しさん
22/12/10 22:40:05.14 Ns16Znepd.net
ABしか練習してなかったけどCまで解けて、
DはWAが少し出て時間切れでした残念。
でも緊張感あって楽しかったです。

743:デフォルトの名無しさん
22/12/10 22:43:34.37 6Z0a3kvJ0.net
今日は時間内に6完

744:デフォルトの名無しさん
22/12/10 22:49:32.73 tlhyP2tP0.net
普通にE、Fの実装重かったね

745:デフォルトの名無しさん
22/12/10 22:51:50.49 O4kKtbHo0.net
D難しくなりすぎ・・・・。もらう方でやってバク取れず。２重dpでうまくいかない事に気づくまで40分。

746:デフォルトの名無しさん (ﾜｯﾁｮｲ 67b1-URIU)
22/12/10 22:56:44.55 q492UgBQ0.net
寝てたら終わってた草

747:デフォルトの名無しさん (ｽﾌﾟﾌﾟ Sdff-Opz5)
22/12/10 23:04:25.58 Ns16Znepd.net
D解けた人の境界見たら、1245位だったのでかなり難解だったんですね。
ダメ元でサンプル通ったから提出したら当然WAでしたが解説見てもさっぱりでした。
少しずつアルゴリズムというものを勉強したいと思います。

748:デフォルトの名無しさん (ﾜｯﾁｮｲ 4799-70Cd)
22/12/10 23:04:45.70 WdAZ/8IS0.net
editor使わず糞アットコの糞サイトbuiltin editorだけで書いてみた
やっぱり全然だめだな(´・ω・｀)

749:デフォルトの名無しさん (ﾜｯﾁｮｲ 67bd-BsWY)
22/12/10 23:11:10.88 tlhyP2tP0.net
総和が○○のときの△△を求めよ、みたいな形はナップサックDPであることが多いね

750:デフォルトの名無しさん
22/12/11 00:16:52.91 sLVycVhX0.net
同じ問題のレートが１年で50下がってるんだから、Dは茶色下くらいを目指そう

751:デフォルトの名無しさん
22/12/11 01:07:10.13 Jt/PvfWs0.net
よかった
俺の調子が悪かったわけじゃないのか
三重ループまでなんとなくわかってたけど実装が複雑になりそうでできなかった

752:デフォルトの名無しさん
22/12/11 02:02:20.83 pBXkhdRDM.net
Ex見てるがやっぱり分割統治FFTいつまで経っても慣れんな

753:デフォルトの名無しさん
22/12/11 02:54:41.11 7rOr8/1H0.net
愛知ループは三重の三倍難しいと言われてるからな。。

754:デフォルトの名無しさん (ﾜｯﾁｮｲ 7fe6-KKgq)
22/12/11 08:11:02.37 7I6zjj+w0.net
DPや二次元配列などでarray型の生配列を使う例が多いのは慣習的なものですか？
処理が速いとか利点があるのでしょうか？

755:デフォルトの名無しさん
22/12/11 08:55:06.62 Mvtwu1hIa.net
arrayより楽な選択肢なんかある？
arrayじゃダメなときは当然そっち使うにしても

756:デフォルトの名無しさん
22/12/11 09:07:28.08 6A4ez8rK0.net
青安定のために参戦を決めていたのですがぐっすり寝てしまい出れなかったであります🤓

757:デフォルトの名無しさん
22/12/11 18:45:09.52 7I6zjj+w0.net
>>755
デバッグしたい時などにあれこれ配列の中身除くのにｖｅｃｔｏｒ配列の方が扱いやすいなと思って使ってました
解説でもDPでvector使ってることもあればarray配列使ってたりと別れるので好みとは思うのですが
何かarray型を選ぶ利点があるのか素朴な疑問でした
>>arrayじゃダメなときは当然そっち使うにしても
array使ってる例が多い気がしたのでvectorからarrayに変更して試してたのですが
vectorに慣れすぎていて逆に使いづらいと思ってvectorに戻しました
ダメな時に結局vectorにするのでそれなら最初からvectorで統一しようかなと
まだ経験少ないので試行錯誤してみます

758:デフォルトの名無しさん
22/12/11 20:50:40.50 OXIrt9Sb0.net
特に多次元にしたときに顕著だけどarrayの方がvectorより速いし省メモリ

759:デフォルトの名無しさん
22/12/11 21:02:26.53 T9/ITlNya.net
初期値をINFで埋めるとかしたいときは vector でコンストラクタ使うかな　それ以外は生配列
array は使う機会ない

760:デフォルトの名無しさん
22/12/11 21:52:54.88 yzn51s/N0.net
map の key にする時なんかはvectorよりかarrayのが早いパターンが多い気がする

761:デフォルトの名無しさん
22/12/11 21:59:28.13 7I6zjj+w0.net
>>758
多次元、速い、省メモリ
試行錯誤する時に意識して使い比べてみます
 >>759
int a[100]　例
生配列とarray型を混同してましたが生配列の方です
確かにわざわざarray型を宣言して初期化することは無いですね
ありがとうございました

762:デフォルトの名無しさん
22/12/11 22:56:42.06 wyaxD1Cj0.net
2次元までの配列ならvector 使うけど3次元以上になると生配列使う
宣言や初期化で文字数が増えるのが嫌

763:デフォルトの名無しさん
22/12/11 23:05:39.85 AimMYYQ4M.net
そもそも std::vector と std::array って比較するようなものじゃない気が……

764:デフォルトの名無しさん
22/12/11 23:35:42.07 xpQepGE40.net
自分はもっぱらvectorで、生配列もstd::arrayも競プロじゃほとんど使ってないけどそれでTLEやMLEしたことはないし自分が使いやすいほうでいいよ

765:デフォルトの名無しさん
22/12/11 23:44:16.93 wyaxD1Cj0.net
マラソンだと上位人はよくarray使ってる印象

766:デフォルトの名無しさん
22/12/12 00:55:20.18 L4LAFoUJa.net
マラソンは定数倍高速化した分だけループ回数増えてスコア伸びるからじゃね
アルゴなら5msのACも1900msのACも変わらんし、AtCoderでC++使っててarrayならギリギリ通るみたいなのはそもそも他の何かが間違ってると思った方がよさそう

767:デフォルトの名無しさん
22/12/12 05:57:59.81 KG5/v6vGa.net
定数倍高速化してギリギリ通るの、平方分割的な半分嘘解法など？

768:デフォルトの名無しさん
22/12/12 08:27:45.85 tiuAOnkep.net
ミラー・ラビンとかポラード・ローを使った高速な素因数分解アルゴリズムって競プロでの使用頻度どれくらい？
昨日のこどふぉのCの問題設定が微妙でこの高速な素因数分解アルゴリズムじゃないと計算量的に怪しかった(実際は√nの素因数分解アルゴリズムを定数倍高速化するのでも通るっぽい)んだけど存在を忘れてたせいで解けなかった

769:デフォルトの名無しさん
22/12/12 09:29:21.46 Ei5MD97h0.net
自分も解けなかった
自分が解いてきた限りではミラーラビンやロー法じゃないと解けない問題は見たことない
なぜ10^6にしなかったのか謎

770:デフォルトの名無しさん
22/12/12 10:59:24.92 cdBddvHVM.net
高速素因数分解が前提の問題は普通にあるけど AtCoder の rated コンでは出なさそう
Codeforces も基本出さない方針な気がするけど writer の次第だからわからん

771:デフォルトの名無しさん
22/12/13 05:21:16.73 uiBmFvT2p.net
こどふぉ来週の月曜日までほぼ毎日コンテストあるんだけど過密すぎるでしょ

772:デフォルトの名無しさん
22/12/13 09:46:33.18 HgDhzteS0.net
コドゲやるぞやるぞ

773:デフォルトの名無しさん
22/12/16 16:05:11.86 2WRHo5T/p.net
蟻本4.4章の巡回スケジューリング問題(円環上での区間スケジューリング問題)のソートを除いたO(N)解法って何？
円環を切って2つ繋げて区間にして考えるのかなって思ったけど上手くいかない気もするし元の問題が見つからないから確かめることも難しい

774:デフォルトの名無しさん
22/12/16 20:10:17.03 R8AxMjl90.net
各区間を頂点として、蟻本の解法の中で構築してるnextを辺としたグラフを考えると、なもりグラフになっててサイクルをちょうど一つだけ含む
答えはこのグラフ上のパスで表せる
サイクルに含まれない頂点を含む解を考えると、パスの始点と終点を一つ進めたものも有効な解であることが示せるので、
全ての頂点がサイクルに含まれるようなパスだけ考えればいい
あとはサイクルの上でしゃくとり法みたいなことやればできそう
で合ってるかな……？

775:デフォルトの名無しさん
22/12/16 21:07:39.53 R8AxMjl90.net
しゃくとり法しないでもサイクル上の適当な頂点から始めて極大な解を一つ取れば大丈夫か

776:デフォルトの名無しさん
22/12/16 22:19:14.38 1iEDLF9Cp.net
>>774
確かにグラフ上で考えると求める区間の選び方はサイクルに含まれることが必要で、辺の数=頂点の数と全ての頂点の出次数1から全体としてはなもりグラフ的な感じにはなりそうだからだいたいその方針で良さそうっぽいな
ありがとう

777:デフォルトの名無しさん
22/12/17 21:30:59.31 1O9afRlw0.net
全完出ました

778:デフォルトの名無しさん
22/12/17 21:44:36.74 1O9afRlw0.net
2位と3位が2秒差

779:デフォルトの名無しさん
22/12/17 22:41:47.95 Ougsnu4Va.net
Dさぁ、過去問から漁れないと時間的に無理だろ

780:デフォルトの名無しさん
22/12/17 22:48:54.79 8O7j2b6E0.net
D通ったけど難易度高すぎ。E,Fの位置にしとけと。

781:デフォルトの名無しさん
22/12/17 22:49:30.45 Ougsnu4Va.net
つーか、Dって
連結がない頂点がある場合、答えは0じゃないよね？
追加したら二部グラフになりえると思うんだけど
このケース考えて完全に迷走した

782:デフォルトの名無しさん
22/12/17 22:51:41.65 I7m2bma6p.net
E全域木になるの言われたらそうなんだけど見えなかったし精進が足りて無いのかな
Dは数ヶ月前だったらEに置いてあった気もするしインフレしすぎ

783:デフォルトの名無しさん
22/12/17 22:53:14.13 8NnsdriJ0.net
>>781
そうだよ
例えば辺が0個のグラフが与えられたとすると、答えはN*2になる

784:デフォルトの名無しさん
22/12/17 22:53:56.18 8NnsdriJ0.net
あ、N*2ではないわ・・・、すまん

785:デフォルトの名無しさん
22/12/17 22:54:02.71 ZH4mYY1r0.net
D問題
やり方として
・まずは連結グラフに分解する
・連結グラフが3以上だった場合は無理判定をする
・そして各連結グラフ毎に
とりあえず各頂点に黒と白を割り振って、
このグラフそのものが2部グラフになっているかを判定する
2部グラフになっていた場合に、各連結グラフごとに自信が持ってる
反対の色の頂点数-頂点数をanswerに足していく
そして、各連結グラフについては
グラフ1の黒数×グラフ2の黒数
グラフ1の黒数×グラフ2の白数
グラフ1の白数×グラフ2の黒数
グラフ1の白数×グラフ2の白数
の4つを足す
っていう解法を思いついたんだけど、グラフ問題といたことなかったから、各頂点がどの気に属しているかっていう判定ができなかった
俺のやり方、・まずは連結グラフに分解する
さえクリアできテレバこのやり方であっていた？

786:デフォルトの名無しさん
22/12/17 22:55:32.46 ZH4mYY1r0.net
cまでは10分ちょっとでクリアできるようになったけど、
ｄがここ一か月難しい気がする
酒のみすぎかしら

787:デフォルトの名無しさん
22/12/17 22:57:13.17 Ougsnu4Va.net
>>785
そう思ったけど、解説にはその点が触れられてない

788:デフォルトの名無しさん
22/12/17 22:59:39.92 Ougsnu4Va.net
いや、それがあのBとWの入れ替え関数式か。
D解けた人良くここまで計算し切ったね
グラフの計算に二部グラフの計算加えて、
さらに計算式も考えるとかやりきれんよ。

789:デフォルトの名無しさん
22/12/17 23:02:27.38 I7m2bma6p.net
自分は余事象じゃなくて普通に足し合わせたけど、二頂点が異なる連結成分にある場合は後から色を合わせられるから全通りOKっていうのを最初は見逃してた

790:デフォルトの名無しさん
22/12/17 23:05:00.09 ZH4mYY1r0.net
グラフの分解ってどうやるのがいいの？
普通はdfsでグラフは見ていくんだろうけど、
for分で回すのも違うと思うし、unionFindとかで調べることになるの？

791:デフォルトの名無しさん
22/12/17 23:13:31.41 8NnsdriJ0.net
おれはUnionFindつかってないよ
まあ使ったほうが見通しが良いなら使ってもいい 
2部グラフとして考え、連結成分ごとに2色に塗り分けて、色ごとの頂点の数を数えて、組み合わせを計算して足し合わせた
これだけ

792:デフォルトの名無しさん
22/12/17 23:23:39.77 8O7j2b6E0.net
青の人が３完だったらしーからD解けなくても全く問題ない気がする

793:デフォルトの名無しさん
22/12/17 23:28:22.91 M78ib0lA0.net
グラフの分解は、
visited[v]: 頂点vを訪問したか
を用意して、for (int v=0; v<N; v++) で visited[v]がFalseなら、
そのvからbfsをして、visitedを更新しながら、色々やる
という方法でやってる
二部グラフ判定なら、visitedは頂点の色の配列で代用できる

次ページ