シコウノストレージ

自分自身の考えを整理するために書いています。

今日のキョウプロ

198D

問題要約

文字列S1,S2,S3の三つが与えられるので、各文字列に対応する数字N1,N2,N3が存在するかを判定しなさい。

 

条件

1:対応する文字列の数字と同じ桁数

2:S1+S2=S3

3:各文字列に同じ文字が含まれる場合のみ同じ数字でなければならない

 

考察

1と2の条件から、0~9までの数字をどの組み合わせにすればよいかという問題に言い換えることができる。

これは最大でも10!通りにしかならないのでTLEにはならない。

 

気を付けること

考察はそれほど難しくはないが、問題は実装のほうでうまく書かないとバグらせて時間がかかってしまうので効率の良い書き方を模索したい。

まず、バグらせそうな部分を列挙する。

1:同じ文字に対しての処理をどうするか

2:先頭が0の場合のコーナーケースに気を付ける

3:気持ち的にはfor文1回で3つの文字列を埋めたい

 

2は気づいていれば問題ないとして、1,3をどう処理するかがちょっとめんどくさい。

同じ文字があるかどうかの判定はmapでもsetでも問題ないが、後で使うときに何文字目の何番目かの情報を持っていないといけなくてそれがめんどくさい。

 

そのため、3のお気持ちと合わせて最初に3つの文字を1列の配列に格納すればどちらの問題も解決。

まぁその処理も少し難しくて,i番目の文字列のj番目というような二次元配列にする。

その配列に一列にした時の配列mのインデックスを入れる。

mには親の番号を入れる(UnionFIndの根を更新するやつみたいな)

などやろうと思えばできないわけではないが、バグらせやすく実装にも時間がかかるため、あまり効率的なやり方ではない。

 

解説のやり方

文字列3とも端っこからmapで重なりを外して、当然昇順ソートになるのでソートされた順番をstring(配列でも可)に保存しておく

ソートされたすべての文字列に対して、0~9の順列を試していく。

これはS1[0]からS3[max]がソートされた文字列の何番目かの情報を取得してきてそれに当てはまる番号を文字列として代入。

最後にS1+S2 = S3の実装の判定をして終わり。

 

189D

問題

文字列SがN個与えられるのでS[i]がANDならAND演算、ORならOR演算をX[i-1]に対して行いY[n]がTrueの数を出力せよ。

ただし

x[0]はTrueまたはFlase

y[0]はx[0]

素数はx,yともにn+1

 

解けなかったので解説見てAC

以下解説

これはi個目にTrue、Falseだった時のTrueの数とFlaseの数を配列に記録しておくDPで解く。

AND は 前回True、今回TのみTrue。

dp[0][i]・・・i番目の時のTrueの数

dp[1][i]・・・i番目の時のFalseの数

ORは前回OR,今回ORのみORの性質を使い

f:id:slwmtin:20210907173230p:plain

 

182D

問題

数列A1~ANが与えられ座標0にいるロボットが,A1,A1+A2,A1+A2+A3.....A1+....ANまで進むときの座標の最大値を求めよ。(Aiは負の数になることもある)

 

考察

負の数になる可能性もあるので、累積和を使えば距離を求めることはできるが最大値を求めることはできない。

また、動く順番が決まっているのでソートはできない。

かといって全探索をしていては間に合わない。

なので、i番目に進む距離の総和とi番目までに進める距離の最大値を記録しておき、N回シミュレートして最大値を算出しておけばよいと考えた。

 

結果それは正解でAC

f:id:slwmtin:20210907230905p:plain