AtCoder Beginner Contest157を眺めて（解いてないです）

昨日AtCoder Beginner Contest157があった。が参加できなかった。

その理由としては、パソコンの充電が切れてしまったからである。ちょうどそのとき充電器を持ち合わせていなかった。「あとで解こう」と決めて皿洗い開始。

ここでは解いていない茶色コーダーが問題を適当に眺めて初心者コメントを垂れ流す。競プロ上位者にはご容赦されたい。

問題はこちら。

atcoder.jp

第一問　Duplex Printing

2の倍数かそうでないかで終わり。

第二問　Bingo

ビンゴの問題。ビンゴカードと呼ばれた番号が入力として与えられて、ビンゴが達成されているかどうかを判定する。余裕の全探索かなぁ。

第三問　Guess The Number

入力では「○桁目の数字は△である」というデータがM個与えられる。それらのデータを全て満たす最小の0以上の整数が存在するときにはそれを出力し、満たすような整数が存在しないときには-1を返すという問題。

一見簡単そうに見えるけど、細かい制約(?)がいろいろあって面倒そう。(全体が2桁以上の時最上位の桁に0が来てはダメだが、それでも入力データとして1桁目に0であるというデータが与えられ得る。)小さい配慮が必要。

第四問　Friend Suggestion

The Union Findみたいな問題。典型問題でここで相当別れるだろうなぁ、上位層と下位層が。(AtCoder Problemsでみてみると、緑の中でもレートが高い人が解けている。)あとでUnionFindの復習がてら解いてみよう。

第五問　Simple String Queries

圧倒的DP臭がする問題。もう「DPで解いてくれなかったら怒っちゃうからね！！！！」と問題が言っているかのよう。どんな感じのDPがいいんでしょうね。

問題の概要を言ってなかった。

長さNの文字列が与えられる。Q個のクエリを処理せよ。クエリの内容は以下。

• i_q文字目をc_qに変更せよ。もしすでにc_qであるなら変更する必要なし。
• l_q文字目からr_q文字目までの部分文字列中に、一体何種類の文字があるか。

N=500000だから全てのl_q, r_qの組み合わせに対してその答えを保持することは現実的じゃなさそう。よくあるのは端から計算するやつ。

つまり、

• 1文字目からr文字目までに含まれる文字の種類
• l文字目からN文字目までに含まれる文字の種類

のどっちか、もしくは両方を保持しておいてクエリを処理していく。ただこれには問題がある。例えばABABという文字列があった時、１文字目から２文字目までの種類数は２種類、そしてそれ以降も２種類だ。だが、上の感じのDPだとそれに対応できない。３文字目から４文字目に含まれる文字の種類数は？と聞かれても上のデータだけでは判別できない。

もう少し考えて答えが出なかったら、答えをみようかな。

第六問　Yakiniku Optimazation Problem

「まってこれってBeginnerコンテストだよね」と言いたくなるような問題。順位表をみた感じ上位44人しか解けていない。問題は非常に簡単。（僕でも理解できるという点で）

焼肉がN枚ある。それぞれ「焼けにくさ」c_iというパラメータを持っている。焼肉を焼くために熱源を(X, Y)に設置する。それぞれの焼肉が焼ける時間は以下で定められる。

dは「焼肉iと熱源との距離」。

K枚肉を焼きたいのだが、なるべくK枚焼ける時間が最小になるように熱源を設置したい。所要時間の最小値を求めよ。

設定自体は簡単よね。ただそれをどう解くかは別問題。今問題を真剣に考えても時間の無駄になりそうだからやめておこ。

全体的な感想

細かいミスさえしなければいつも通りな印象。自分が目標とするのは５完。今年中には全完を達成したい。