おはようございます。しほみんです。
久しぶりに競技プログラミングの話します。二か月ぶりですね。
ずいぶん飛びましたが、HHKBプログラミングコンテストです。
自分の競技プログラミングへのスタンスです。
＜自分のプログラミング力＞
・レートは1000程度になりました。緑中堅へ。
・C#でクラスとかつかってアプリケーションは作れます。
＜Atcoderでのスタンス＞
・アルゴリズムについて問題でいろいろ学んでいる。第3回PAST70点で中級取得。
・基本的に本番でやっている。現在60回以上参加、2年目。
・目標はABCのD問題までをちゃんと短時間で解けるようにすること。パフォーマンスは1000以上、できれば水色（1200以上）は欲しい。
今回はABC、30分1WAでした。C問題の凡ミスはもったいなかったです。D問題は頭回らなさ過ぎて無視、E問題は2のn乗をメモ化しなかったからTLEでACできませんでした。パフォーマンスは862で、レートは989→977で微減です。まあレートは1000ちょっとしたをうろうろしています。
久々なんでどうなのかって感じですがA,B,C,E問題を解説します。D問題は頭回らないのでちょっと厳しいので割愛します。
ここから問題です。
A問題
'Y'か'N'の入力と、'a'、'b'、'c'の入力があります。
'Y'なら大文字を、'N'ならそのまま出力してください。
普通に大文字変換するかどうかを考えればよいです。
小文字から大文字に変換するにはint型にして-32すればよいです。
B問題
Ｈ列W行の空間があります。'.'は散らかってない、'#'は散らかっているです。
上下左右2マス連続して散らかってないところに布団が引けます。
何か所布団が引けるか調べてください。
こちらも割と単純で、(0,0)から縦、横に2マス連続で空いているところをカウントしていけばよいです。ただし、W列目は横判定ができないので省いて、H行目は縦判定ができないので省く必要があります。
C問題
長さNの数列があります。
piまでに出てきた数以外の中で0以上の中で最小なのはいくつかをi行で出力しなさい。(iは1-n）
例えば、{1,1,2,0}のときは0,0,0,3が答えになります。最初三つは0がカウントされてないので、0で、最後は0,1,2を除いた中で0以上の最小なので3となります。
まあ、単純に考えると最大、最小を出せばよいってなりそうですが、中抜き数になった場合対応できないです。例えば、1,2,3,5,6,7とあった数の中で0が入ってくると次は4になるのですが、最大と最小だけだと次は8になってしまうので違います。
ではどうするか？コツとしては一度入った数は二度と選ばれないことと、最小の数として選ばれたときのみ、次の最小の数を探す必要があるってことです。
後ろが大事で、要するにとりあえずリストで今まで入った数を記録しておいて、最小の数がはじかれたとき、順次数を足して増やしていってそこがまだ入っているかどうかを見ればよいです。これ自体の計算は不可逆なのでo(N)で済みます。
よって、
最初のindexを0とする。
for文で、まずはiまでに入った数をカウントする。
indexから足し上げる形で調べてそれがカウントされてないなら答え出力で、indexをその数にしておく。
が答えです。
E問題
B問題と同じように配列が与えられます。
この配列において、'.'の位置がK個あるとき、証明の配置は2のK乗になります。
1個以上の証明が照らされたとき、上下左右が照らされるマス数をスコアとします。
このすべての配置におけるスコアの和を100000007で割った数で求めなさい。
問題を理解するのが結構厄介な奴です。しかし、ゆっくり考えればやることはわかります。すべての光を考えていてもらちがあきません。ここでは、それぞれある位置において光るケースがいくつあるか見てみましょう。
つまり、位置（i,j）が照らされる場合はいくつあるかです。この照らされるマスではどこか光れば、縦横でつながっているマスでどこか照らされればよいのです。
つまり、(i,j)が縦横でつながっているマスの数（自身を含む）をSijとすると、2のSij乗から1引いた数通りだけそのマスが照らされてスコアになります。（1引くのは全部照らされない場合）
あとは、全体で照らせるマスの数をallとすると、all-Sij個の電球は関係なく、スコアになります。よって2の(all-Sij)乗をかけます。
まとめると、(i,j)が'.'のとき、その場所が照らされる状況になるマスの数をSij個、全部の手られる電球の数をALL個とすると
(2の(Sij乗) - 1 )×2の(ALL-Sij)乗= 2の（ALL乗）- 2の(ALL-Sij)乗 となります。
あとはそれぞれのケースで計算します。o(HW)で間に合います。
ただ、電球は累積和で残しておき、それぞれの位置ごとでの電球の数を求める工夫が必要ですし、2の〇乗は普通にメモ化で記録しておかないと間に合わないっていうので実装自体は結構壁が高い気がします。
D,E問題でもよくあるそのまま考えると無理だけど逆に考えるとできるパターンの問題でした。まあ、最後の注意事項はきちんと超えないとだめだなあと実感しました。
最後に....
まあC問題までをきちんと考えて解けているのはよいですが、やはりDかE問題は解けないと厳しいですね....
あと久々に書いたから説明雑かもしれないです。詳しくはコードを見てください。
ではでは。
