ABC 327 （2023/11/04）
〇A問題
Yuto.icon "ab" in S or "ba" in S
kakip.iconinで判定
TK.iconTTT.iconおたふく.icon Yuto.iconさんと同じ方針です.
yuichang.icon頑張って書く
Kaplam.icon前から見る
tako.icon適当に
まーす.iconsetを使わずに愚直に配列で場合分け．
CarpDay.icon今回はスライスうまく使えた，って自画自賛していた．inで済んだな，確かに．．
〇B問題
Yuto.icon pow(16, 16)くらいでpow(10, 18)を越えるので，A = range(0, 20)を全探索したら1WA．なんで...と思って問題文を読み直したら， 正の整数 A って書いてる．見落としてました．くやしい
kakip.iconrange(100)で1WA
TTT.iconおたふく.icon for i in range(1, 17): if B == i**i: print('Yes')としました.
yuichang.iconsqrtl(b)+1までループ
Kaplam.icon最初A^n = Bと見間違えて10^9回せなくねってなった
tako.icon全探索
まーす.iconwhile文で全探索．A^A>=Bとなったら表示．
CarpDay.icon Yuto.iconさんと同じく，見落として1WA．
TK.iconwhileで１から順番にa*aがbを超えるところまで回して、見つかれば出力。前の問題につられてYes,Noで出力してWA1。泣いた。
〇C問題
Yuto.icon やるだけ．研究室の後輩が数独 好きって言ってたな～とか思い出しながら実装．最近B, Cあたりに多い重実装問題を考えると，この問題は比較的軽かった気がする．
kakip.iconsetで数える
TTT.icon 9x9の行・列それぞれをsortして全部一致かつ3x3を長さ9のリストに入れてsortしてそれらが全部一致するならYesという処理を愚直に書きました. 残り時間でDは諦めてCの3x3の行列の抽出をもっと少ない行で書けないか考えていましたが良い案が思いつきませんでした.
yuichang.icon1~9入れたset作っておいてその都度行とかがそれと正しいか判定
Kaplam.iconそれっぽく数える
tako.iconsetで判定
まーす.icon縦，横，ブロックそれぞれfor文を分けてsetで判定．めんどくさい．
おたふく.icon Cの実装問題にしては計算量の工夫も無ければ、実装のテクニックも軽めな印象。行、列、3×3のブロックの各それぞれで条件を満たすかどうか関数に切り出してチェック。
CarpDay.icon数独を解く問題かと思ってときめいたら，単に条件チェックだけでがっかり．set使う．
TK.icon条件を確認する行列マス用のセットを用意。そこに数字を回収してすべて9種あるか確認
〇D問題
Yuto.icon よく分からないので，とりあえず図を書いてにらめっこしてたら閃いた．これ二部グラフで判定できるのでは？？ということでやってみた．二部グラフ判定はみんな大好きUnionFind．サンプルが通ったので提出．一発AC．気持良い～
kakip.iconabc320_Dの自分のコード見ながら書いたらできた。各頂点と繋がっている頂点をリストにいれてみていくやつ すべての頂点が繋がっていない場合を見逃して１ペナ
yuichang.icon判定法試行錯誤してペナ、二部グラフ判定して気づいたらサクッといけた。難しくない？
Kaplam.icondequeでBFSして01入れかえてって感じ、ずっと茶色上限ギリギリから抜けれないの
tako.icon多分Kaplam.iconさんと同じ感じだと思うけど4WAが消えない
まーす.iconDも出来そうだとおもったが，Eの方が可能性があると感じたのでEへ．
おたふく.icon Yuto.iconと同様にあれやんと思い、ニヤニヤしながらAC。ライブラリとして残しておいて正解。
CarpDay.iconグラフの判定問題と気付いたらあとはBFS/DFS．kakip.iconさんと同じく，非連結の場合の処理を書き忘れて1ペナ．
TK.icon最初サイクル検出の問題と思って作って出したらWA３。方針違うのかと思い考え直すと、偶数サイクルの場合問題ないことに気付いた。その後はもう一つの方針に移り時間切れ。考えが甘い。
〇E問題
Yuto.icon なにも分からなかったので，pulpで定式化して出してやろうと思ったけど，pulp.LpVariableを配列の添え字にするとTypeErrorになる．解決方法が分からず撤退．
yuichang.icon愚直したらWAとTLEで最悪><
kakip.icondp[i][j]=j~n回目のコンテストからi個選んだときのレーティングの第一項の分子の最大値としたらできた。コンテスト終了後25秒でAC
まーす.icondpを使うことはすぐにわかった．プログラム中にも書いたが，dp[j]を直近のコンテストから数えてi日までの期間で，j個参加したときのレートの最大値，としてdpを用いた．本番中ずっと逆順で考えていたり，私のプログラムをみたらわかるが，式がキモイのでかなり時間をくった(数式だと簡単だけどね......)．
おたふく.icon 与えられたレーティングの式を変形すれば最大値となる条件に付いて、何か見えるものがあるかひたすら式変形。時間が無いので最終的に1件だけ記念提出。
CarpDay.icon方針はkakip.iconと同じ．初めは第2項まで含めて考えていたが，最適性を満たさないことに気付いて最後に処理する方針に変更．第1項の式変形，楽しかった．
〇F問題
CarpDay.iconディアルガとパルキアの2軸での累積和で求まるが，各軸でO(10^5)になるので不可能．解法思いつかずに終了．諦めて解説読む．ああ，あれか．．きちんと勉強しておくべきでした．．
おたふく.icon 遅延セグメント木のライブラリを整備しておきました