ABC310 (2023/07/15)
〇A問題
Yuto.icon やるだけ
yuichang.iconやる
tako.iconやるだけ
Kaplam.iconやる
TTT.icon やるだけ
CarpDay.icon（きちんと書くと）Pとmin(D)+Qの小さい方
おたふく.icon CarpDay.iconと同様
TK.icon値計算してmin
〇B問題
Yuto.icon 10分くらい，問題文の3番目の条件の意味が分からなかった．
yuichang.iconゴミ。問題文が読めない。値段安くて機能同じでも条件満たすのかよ
tako.icon条件を一個見落として1WA
TTT.icon コンテスト後にACでした。AがBの部分集合であるかをif A in B:と表記するのだと勘違いしていました。ネットで調べてif A <= B:という書き方だと知りました。勉強不足...。
CarpDay.icon知りませんでした．．．if len(A - B) == 0を使っていました．部分集合の判定だけなら，if A <= Bの方が新しい集合作らない分，速そうですね．
Yuto.icon 上に同じく，部分集合の判定方法知りませんでした．
Kaplam.icon値段と性能の数を比べてからiに入っていてjに入ってない性能があるか調べる
CarpDay.icon1ケースWA地獄から抜けられず，B問題解けず(x x)．コンテスト後，ベタに書き直したらAC．計算時間に余裕がある問題は，確実性を重視すべし
おたふく.icon 書いてある通りにitertoolsのpermutationsを利用して全パターンをすべての条件を満たすか試す。TTT.iconと同様に、集合Aが集合Bに含まれるかの判定や、集合Bの中の要素が集合Aに含まれていないかの判定の書き方を調べる。
TK.icon全探索、条件を満たすものがあるか確認する。コストが比較対象以上のもので、機能が部分集合かどうか、そのうえでコストが上回っているまたは機能数が多いかどうかを調べる。
〇C問題
Yuto.icon reverseしてるつもりが，なぜかsortしてて１ペナ．もったいない．．．
yuichang.iconreverseしてsetにそいつがあるか否かを見る
tako.icon反転したやつを別のsetで管理
TTT.icon 上の方々と同じ方針だと思いますが、combinationsで2つTLE。方針を変えて再実装するとTLEは解消されたものの6WAでした。
Kaplam.iconsetに入れて比べる、文字列が中々上手くひっくり返せなくて少し苦戦した。
CarpDay.iconSを集合にして，各要素sの反転がSに存在しない，または反転した文字以下（1文字対策）となる要素数をカウント．解説の「原案者の実装」すばらしい．
おたふく.icon Sを順に見ていって、その文字列とそれを反転させたものが集合sに存在しない時に集合sに追加していく。
TK.icon順番にみて、反転した文字をふくめてセットに追加。以後そのセットを参照して、存在しないもののみカウント
〇D問題
Yuto.icon 全探索するなら計算量は，$ O(n! \ {}_{n-1} C_t)くらい．全探索無理かなと思ってbitDPやろうとしてたけど，沼ったので，一旦全探索書いてみようと思い書いていたらコンテスト終了．．．
yuichang.iconbitDPor順列列挙で解けそうだがBのせいで時間がない。記念にネットの適当なコード投げたらCEした
Kaplam.icon仲のいい人やチームに入っている人数をlistにset入れて管理するのかと思ったけどPythonくんが言うこと聞いてくれる方法がわからなかったので諦めてやりたいことをコピペ連打1118行コードで実装、1/3しか正解出なかったけど楽しかった、探索は再帰
CarpDay.iconDPは無理と考えて全列挙で実装するも，入力例4が自PCでも時間がかかりすぎて解が出力されず．$ 10!を解決して，ギリギリAC.
おたふく.icon N人をTチームに分ける組み合わせを全列挙しようと考えるも、最初に考えた方法では$ (N+T-1)!になってしまう。次にdp的な発想で、同じチーム分けは最初から除いて計算量を削減できるように工夫の方法を考え、1から順にどのチームに入るかを条件を満たすように考え、何通り作れるかを求める。発想としては解説と方針が似ていたが、実装力不足で解けず...。制限時間後に2時間程かけて実装してなんとかAC...。
CarpDay.iconコード拝見しました．自分が当初解きたかった方針だったので，参考になりました．独力でも実装してdeepcopy使ったら（ACでしたが）実行時間かかりすぎ．使わないようにしたら，むっちゃ速くなりました．コンテスト中も似た発想で実装していましたが，メンバーいないT個のチームで初期化していたため，同じ分け方が重複して存在（[(1,2), (3,4))]と[(3,4), (1,2)]が存在） してしまい，別の方法で実装し直しました．
おたふく.icon 自分もsetが同じところを参照してしまい、setに要素を追加すると勝手に別のsetにまで要素が追加されてしまったりして困りました。
TK.iconDPみたいに考えてみたが、あまりまとまらず、グラフ的に考えたり計算してみたりいろいろやっていた
〇E問題
Yuto.icon Dが沼ったので見に来た．30分くらい式変形してみたけど，$ O(N)に落とせなかったのでDに戻る．
CarpDay.icon同じく見に来た．難しそうに見えて実はシンプル，というパターンかな？と思いつつ，Dを優先して終わる．コンテスト後に入力例1でハンドシミュレートしたら，何とあれやん！！綺麗に実装してACでした．B問題が無難に解けていたら，この問題も解けたのに．．．
〇F問題
Yuto.iconこれ以降見てない
CarpDay.iconコンテスト後に確認．$ dp[i][k] をA[i]まで調べて合計を$ k にできる確率としてDPで解こうとしたが，$ \sum_{k=1}^{10}dp[i][k] \not= 1 （1つの状態が，複数のkでカウントされる）ので，状態遷移がうまく表現できず断念．解説見たら，ああbitDPね．気付けなった自分が情けない．早く気付いて，早く実装できるようになりたい．