ABC459回答メモ

0.はじめに

　体調の悪さの続く今日この頃。
　ABは順調にとけたけど、CはTLEがとれない・・・。
　いろんな工夫をしてもだめで、ちらっと見たDが解けそうだったので
　残り15分くらいなのに取り組んだところあっさりAC。
　順番間違えたと思いつつコンテスト終了。
　DのACが効きレートは-2の812と緑に残りました。

1. A - Hell, World!

　文字列の問題。
　Sをans変数に一文字ずつ移しつつ
　その途中でX文字目だけうつさないことで
　問題の条件をみたした形でansを出力して終了。

　https://atcoder.jp/contests/abc459/submissions/76028708

2.B - 459

　B問題にたまにある、面倒だけど、考え方はそれほど難しくはない問題。
　処理の前段で、a～zまでの対応する数字を辞書に登録し
　後は読み込んだ文字列毎に数字を検索し結合し
　出力して終了でACとなりました。

　https://atcoder.jp/contests/abc459/submissions/76037809

3.C - Drop Blocks

　TLEが消えずてこずった問題。
　結局コンテスト後解説を見、それでもわからず
　GEMINIに相談して、解説の意味を皿に解説してもらって
　やっと考え方が分かりました。
　【TLEが出てた考え方】
　　1.以下を用意
　　　-1.現在の最低マス位置Ｌ
　　　-2.現在の最高マス位置Ｈ
　　　-3.マス毎のブロック数Ｂ(Ｎ個の配列)
　　　-4.ブロック数毎のマスの数Ｍ（300001個の配列）
　　2.クエリー1の時
　　　-1.Ｂからマスｘの増加前のブロック数ｎを取得
　　　-2.マス毎のブロック数Ｂ[x]に1加算
　　　-3.ブロック数毎のマスの数M[n]から1減算
　　　-4.ブロック数毎のマスの数M[n+1]に1加算
　　　-5.M[n]が0かつ、最低マス位置Lがｎの時、最低マス位置Ｌを1加算
　　　-6.最高マス位置Ｈがｎと同じとき、Ｈに1加算
　　3.クエリー2の時
　　　-1.Ｍ[ｙ+Ｌ]から、Ｍ[Ｈ]の値を加算して出力
　　
　3の集計処理に時間がかかっているのは分かったのでMを辞書化したりと
　工夫しても時間があまり縮まりませんでした。

　コンテスト後解説を読み、改良しました。
　　1-4.をブロック数以上のマスの数とする
　　2-3.の減算は不要となる
　　2-5.の最低マス位置の判定は、M[n]＝Nとなる
　　3-1.の集計は、単純にＭ[ｙ+Ｌ]の出力となる
　　　→ただし、ｙの値が最大値の時を考慮し、Ｍを600000以上に拡張するか
　　　　ｙ+ＬがＱ以上の時は0を出力とする等の処理が必要
　　1-2.のHと2-6の処理は不要となる

　処理を引くことで高速化出来るという発想が新鮮でした。

　https://atcoder.jp/contests/abc459/submissions/76092439

4.D - Adjacent Distinct String

　なんとなく、Ｄにしては簡単な問題でした。
　以下方針で実装してACとなりました。
　・文字ごとの出現数が、偶数の時はSの文字数を2で割った値、奇数の時は、Sの文字数を2で割った値+1、
　　以内であれば、隣接しない文字列を作れる。
　・回答用文字列は、出現数の降順で文字を準備しまず文字列の偶数位置を埋めていき、最後まで来たら
　　奇数列を埋めていく事で作成可能
　　例）aabbbccの場合b3、a2、c2、とし
　　　bをbbb**
　　　cをbbbc　で偶数折り返し
　　　　 bcbb*c
　　　aをbcbabacと埋めて完成

　【実装】
　　1.Sをリストに入れカウンター関数で文字ごとの個数をカウントした辞書Cを作成
　　2.Cを元にリストqに[カウンター数、文字]を格納し、降順にソート
　　3.LにSの長さをセット
　　4.Xにq[0]の内容をセット
　　5.Lが奇数の時
　　　-1.L//2+1がX[0]以上の時
　　　　-1.Yesを出力
　　　　-2.jに0をセット
　　　　-3.リストansに""をL個セット
　　　　-4.(奇数列の埋め)以下iを0からLを超えないまで2ずつカウントアップして繰り返し
　　　　　-1.X[0]が0の時（次の文字に移る）
　　　　　　-1.jに1加算
　　　　　　-2.Xにq[j]をセット
　　　　　-2.ans[i]にＸ［１］をセット
　　　　　-3.X[0]から１減算
　　　　-5.(偶数列の埋め)以下iを1からLを超えないまで2ずつカウントアップして繰り返し
　　　　　-1.X[0]が0の時（次の文字に移る）
　　　　　　-1.jに1加算
　　　　　　-2.Xにq[j]をセット
　　　　　-2.ans[i]にＸ［１］をセット
　　　　　-3.X[0]から１減算
　　　　-6.ansを結合して出力
　　　-2.L//2+1がX[0]より小さい時
　　　　-1.Noを出力
　　6.Lが奇数の時
　　　-1.L//2がX[0]以上の時
　　　　略）5-1-以下の処理と同じ
　　　-1.L//2がX[0]より小さい時
　　　　-1.Noを出力

　なんとなく、偶数奇数の部分もいい感じにまとめられそうではありますが、
　まぁ、ACでした。

　https://atcoder.jp/contests/abc459/submissions/76085631

以上