0.はじめに
やっと内定がでて安心している今日この頃。
軽く生地でまとめておいてもいいかなと思いつつ参戦。
ABと順調にACとるも、Cでブレーキ。
やっとACを取れたかと思ったらDが解けずに撃沈。
順調に茶色が濃くなってきまして、-20の776となりました。
1. A - illegal
インプット文字列を5で割った余りを求め
0ならYes、違えばNoを出力して終了。
https://atcoder.jp/contests/abc451/submissions/74458157
2.B - Personnel Change
部門ごとに今期の所属人数と来期の所属人数を集計し差異を計算して出力して終了。
https://atcoder.jp/contests/abc451/submissions/74465959
3.C - Understory
庭の木を高さ毎に持って置き
切る操作をいかに早くするかがポイントの問題。
最初にheapqを使う方法と単純にリストを使う方法とで
どちらを使うか迷い、前社を選択しましたがTLE
後者で作り直したらACとなりました。
選択のミスが悔やまれる結果となりました。
【実装】
1.Qを読み込む
2.ヒープキューqを空で定義
3.以下Q回繰り返し。
-1.X(クエリー記号)とH(クエリーごとの基準値)を読み込む
-2.Xが1の時
-1.ｑにＨを追加
-2.ｑの長さを出力
-3.Xが2の時
-1.ｑが空でない時
-1.ｈにｑの先頭の値を取り出す
-2.ｑが空になるか、ｈがＨを超えるまでｑから値を取り出しｈにセット
-3.ｈがＨを超えていたら、ｑにｈを戻す
-2.ｑの長さを出力
ヒープキューからの出力等で時間がかかるかと思いましたが
結局削除回数は多くても挿入回数と同じになるので、十分間に合いました。
https://atcoder.jp/contests/abc451/submissions/74487391
4.D - Concat Power of 2
最初に取り掛かったときに、良い数字を全列挙して指定番目を出力する事が出来そうと
気づきましたが、結局うまく全列挙が出来ず終了となりました。
コンテスト後解説等見ながら修正しACをとれました。
【実装】
1.Nを入力
～良い整数列挙準備：２の冪を列挙～
2.リストPを空で定義（２の冪を格納）
3.変数p（2の冪計算用）に1をセット
4.以下ブレイクまで繰り返し
-1.Pにpを追加
-2.pに2を掛ける
-3.pが10の9乗を超えたらブレイク
～以上で10の9乗より小さい2の冪がPに格納される～
～良い整数列挙準備：桁数毎の2の冪を格納するリストを初期化＆2の冪を格納～
5.PL（桁数毎の2の冪を格納するリスト）に[]を20個格納
6.Pからvに1つずつ値を取り出し以下の処理
-1.lにvを文字列とした場合の長さ（vの桁数）をセット
-2.lが20以下の時PL[l]にvを追加
～良い整数列挙：桁数毎の良い整数を格納するセットを初期化＆桁数毎に格納しつつ、N番目の数に到達したら出力～
7.Sにセットを20個格納
8.TC（いままで作成した良い整数の数）に0をセット
9.以下i(作成する良い整数の桁数)を１から20まで繰り返し（本問題の制約では本来10までで十分）
～まずはi桁の2の冪を桁数毎のセットに格納～
-1.PL[l]からvに1つずつ値を取り出しS[i]に格納
～j（１～i-1を推移）桁までのPLの値とi-j桁のSの値を組み合わせてS[i]桁に格納していく
-2.jを１～i-1まで1ずつ増やしながら以下処理
-1.p10(組み合わせに使う2の冪の取る桁数)に10**(i-j)をセット
-2.PL[j]からp_vに1つずつ値を取り出し以下処理
-1.S[i-j]からs_valに1つずつ値を取り出しS[i]にp_v*p10+s_valを追加
～桁数iまでの良い整数がN個目かの判断＆必要な処理～
-3.CIにS[i]の長さをセット（i桁目の良い整数の個数）
-4.TC+CIがN以上の時（i桁目の良い整数にN番目の良い整数があるとき）
-1.S[i]をリスト化し、ソートしたものをresにセット
-2.resのN-TC-1番目の値を出力してプログラム終了
-5.TC+CIがNより小さい時TCにCIを加算
上手くすれば普通に全列挙でも行けるようでしたが、上記やり方に落ち着きました。
https://atcoder.jp/contests/abc451/submissions/74510415
以上