AtCoder Beginner Contest 211回目のA問題
AtCoder Beginner Contest 211回目、A問題、ブラッドプレッシャー、
プレッシャーかな、問題文。収縮期欠圧Aと拡張期欠圧Bが与えられます。平均欠圧Cを求めてください。
ただし平均欠圧は以下のように定義されるとします。Cイコール3分のAマイナスBプラスBでAとBが与えられるのでCを出してくださいですね。
これはそのままやるだけでいいのかな。
一旦、コードテスト面倒なので、そのまま書いてみましょうか。
A、B、イコール、アップ、イント、インプット、ドットスプリット、プリント、C変数だけは用意しておこうか。
プリントCで、CがAマイナスB割る3プラスBで出力します。
ACしたのでB問題に行きます。
B問題、サイクルヒット問題文4つの文字列S1からS4が与えられます。この中にH、2B、3B、HRがそれぞれ1つずつあるか判定してください。
ただし全てのSIはH、2B、3B、HRのいずれかと一致します。
4つの文字列が与えられて、それぞれ別の文字列ですかっていうのを判定しないといけない。
行で分けられてますね。1行目がS1、2行目がS2って感じで分けられてるので、これもなしでいいですね。
コードテスト、4I、インレンジ、だから4回Sイコール、インプット、その前に1行目に空の文字列L、空のリストLを用意しておきます。
L.Append S
で、プリント、イエス、イフ、レン、セット、エル。
これで重複要素がリセットされるので、重複要素がないオリジナルの全部1個だけの状態になるので、
何種類入ってますかに判定されます。 この数が
イコールイコール4だったらイエス、エルスそうでなければノーを出力してください。これでいけるはず。
はい、提出。 ACしたのでC問題に行きます。
C問題直題問題文、文字列Sが与えられます。 このうち8文字を選び下線を引き、下線を引いた文字が左から順にCHOKUDAI
直題となるようにする方法は何通りありますか。 ただし答えは非常に大きくなる可能性があるので、10の9乗プラス7で割った余りを出力してください。
これはさすがにコードテストを入れますね。 聞いている限り何が何やらなので、Sイコールインプット
で、モードを入れておきましょうか。
10の何乗って言ってた?
10の9乗プラス7ね。 9乗プラス7。
入力例がCHCHOKUDAI、出力例は3。
順番をこうで引いていって、
直題という文字列がどれだけ作れるかですね。 左から順にCHOKUDAIになる。
なればどこでもいいので線を引いてください。
わかんねーな。なんだこれ。 辞書?
違うなぁ。 制約Sは8文字以上10の5乗以上以下。
10の5乗だから
多分4分2つだとオーバーしちゃいますね。
下線を引きなので、しかも適当。 だから下線を引く部分が3つ4つあってもいい。
1文字ずつ分かれていても最悪いい状況だから。 単純な二重ループじゃ解けなさそう。
寝起きで頭が動いていないので諦めて、ちょっとこれは普通に解説見ましょうか。
動的計画法DPを使います。
DPのIJをSの合文字目までを使って直題のJ文字目まで選択する方法と定義します。
ここでNイコールSの絶対値、Tイコール直題として残化式、全化式が成り立ちます。
全化式の見方わかんないんだよな。
4分の二重ループを用いて、二重ループ使えるんかい。
IJが小さい順にDPのIJを全て求めることができます。
最終的な答えはDPのN8です。 このアルゴリズムの計算量はオーダーNで十分高速です。
ちょっと他の方の提出コードを見つつ、 DPも学んでいかないとと思います。
とりあえず今日はここまでで勘弁してください。 ではまた次回お疲れ様です。