0.はじめに
最近また調子が下降気味なので気合を入れなおしたい今日この頃。
パナ〇ニックグループを冠するコンテストということで難しいのかなーと
思ったら難しかった・・・。
ABは軽く行けましたが、Cでブレーキ。
制約甘いからごり押ししてみましたがTLEを解消できず時間切れ。
レートは-22で710と急落しました。
また600台がみえてきた・・・。
1. A - ABC -> AC
単純に文字列の長さを求めて、真ん中の位置をもめ
真ん中前後の文字列をくっつけて出力してACでした。
https://atcoder.jp/contests/abc427/submissions/70024350
2.B - Sum of Digits Sequence
制約は短いですが素直に都度計算していると
TLEになるかもと思い、一応集計用リストを作りました。
【実装】
1.Nを読み込み
2.回答用リストAを準備（A[N]が答えになる）A[0]は1
3.集計用数値リストBを準備（f(A[i]）をB[i]に格納）B[0]は1
4.変数iを1からNまで繰り返し
-1.変数i毎の回答用変数ansを準備（A[i]に入る値）
-2.変数jを0からi-1まで繰り返し
-1.Bの大きさがj+1より小さい時（まだ回答用変数が未計算）
-1.XにA[j]をセット
-2.計算用変数bに0をセット
-3.Xが0になるまで以下繰り返し(f(X)の計算)
-1.bにX%10を加算
-2.Xを10で割る（切り捨て）
-4.Bにbを追加
-5.ansにbを加算
-2.Bの大きさがj+1以上の時（回答用変数が計算済）
-3.Aにansを追加
5.A[N]を出力
上記実装でACとなりました。
https://atcoder.jp/contests/abc427/submissions/70036283
3.C - Bipartize
Nが10までの制約をたのみに以下の実装をしてみました。
【考え方】(TLE)
1.頂点数と辺の辞書（頂点毎の辺がつながっている頂点リスト）をもとに
2部グラフかを判定する関数chkを準備
2.辺情報を読み込む際、辺の辞書を準備
3.以下、削除する辺の数 iを0～Mまで繰り返し
-1.itertools.combinationsを使い、辺リストから削除する辺の数だけ
削除する辺を選出
-2.辺の辞書から3-1.の辺を削除
-3.関数chkをNと削除後の辞書を渡し2部グラフチェック
2部グラフであれば iを出力して終了
-4.2部グラフでなければ削除した辺を辞書に戻す
上記実装で20問中5問のTLEとなりました。
解説を見て、頂点の白黒全組み合わせに対し、
2部グラフにするために必要な削除する変数を求める実装をして
ACとなりました。
https://atcoder.jp/contests/abc427/submissions/70093985
以上