0.はじめに
ゴールデンウィークも終わりこの後祝日まで
遠い今日この頃。
ABCは順調にいくもDで躓き。
上手い打開策は出てこずに時間切れ。
2分探索の案までは出たものの、上手くプログラムに
昇華できませんでした。
レートは-4と微減し771に。
開始直前に来客がありスタートがちょっと遅れたのですが
それが無ければプラマイ０位には持っていけたのではないかと悔やまれます。
1. A - Array
行列内の指定した位置の値を出力する問題。
指示通りにすっと出力して終了。
https://atcoder.jp/contests/abc457/submissions/75621414
2.B - Arrays
Aの発展系の問題。
表が2次元になりややこしくなっていますが
指示通りにすすっと出力して終了
行の先頭が項目数であることを見落として
失敗しそうだなと思いました。
https://atcoder.jp/contests/abc457/submissions/75624976
3.C - Long Sequence
あとからみるとBの発展形と言えなくもない問題。
指示にある操作を素直に行ってから問題を解こうとすると
大変なことになるのでそこを工夫する問題。
【考え方】
1.i毎の操作により、列Bの長さは、LiCi個増加する
2.Kの値と各行毎のBの値増加数を元にすればどの行にK個目の値があるかわかる
3.X行の中にK個目の値がある時、X-1行目までのLiCiの値をKから引いたK’とすると
K’％L[X]番目（0の時はL[X]個目）の値が求める値となる
と、すんなり解法が見つかりACとなりました。
https://atcoder.jp/contests/abc457/submissions/75631662
4.D - Raise Minimum
各行に対する操作の重みが違う中での最大値判定問題。
2分探索法を使うパターンに思えたのですが、上手くプログラム化できず
ヒープキューを使った強引な方法を試し、あえなくTLEに。
コンテスト後解法をみて、過去問等参考にすれば行けたかもなと思いました。
【実装】
1.N,K,リストA(先頭に[0]付加)
2.関数chk(引数：x 戻り値：True(可能)、False(不可能))
(K回の操作でリストAの値を全てx以上に出来るかを返す)
-1.変数nk(関数内でのAへの操作回数)を0で初期化
-2.iを1からNまで増加させる繰り返し
-1.A[i]がxより小さい時（大きければ操作不要）
-1.nkにx-A[i]+i-1//iを加算
-2.nkがKを超えた場合Falseを返して関数終了
-3.Kを超えずにループが終了すればTrueを返して関数終了
3.変数ok(回答の下限)に1をセット
4.変数ngにA[1]+K+1(回答の上限)をセット
5.以下ng-okが1以上の間繰り返し
-1.mに(ok+ng)//2をセット
-2.chk(m)がTrueの時okにmを、Falseの時ngにmをセット
6.okを出力して終了
https://atcoder.jp/contests/abc457/submissions/75674304
以上