AtCoder Beginner Contest 136回目
AtCoder Beginner Contest 136回目。A問題。トランスファー。問題文。
水を入れる容器が2つあります。容器1には水をAmlまで入れることができ、水がBml入っています。
容器2には水がCml入っています。容器2から容器1に入るだけ水を移します。
容器2の中には何mlの水が残るでしょうか。ABCが与えられます。
ABCイコールマップイントインプットドットスプリット。
で、Amlまで入れることができ、水がBml入っています。
だからA-Bを取りあえず出して、A-B。
で、水がCml入っています。
で、容器2の中には何mlの水が残るでしょうか。だからC-A-Bですね。
C-A-Bをプリントすればいいはず。
提出します。
和が出た。
A問題とB問題の解説
コードテストします。
あれ?合ってると思ったんだけどな。
入力例1が839の4。4ですよね。
入力例3が0。マイナス2。
プリントマックス0とこれで取ったら大丈夫?
そっか。入るだけやったらオーバーすることがあるんですね。
ACしたのでB問題いきます。
B問題。アンイーブンナンバーズ問題文。整数Nが与えられます。
N以下の正の整数のうち、先頭に0を付けずに受信法で表記したときの桁数が奇数であるようなもののこ数を求めてください。
桁数が奇数。だから1とか100の位とか。
あとは?1000は4桁か。
入力はNが与えられます。N以下の正の整数のうち桁数が奇数。
制約は10の5乗。順繰りで作っていっても良さそうだな。
それで一回やってみましょうか。
C問題の解説
Nイコールイントのインプット。
で、アンスイコール0。
4IインレンジN。
Nプラ1しておこうか。
1以上?N以下の正の整数。
そうですね。0カウントしてないので。
1からNプラス1までで。
IF連の一応STRにしておいて、
I%2がNイコール0だったら、
アンスプライコール1のプリントアンス提出。
ACしたのでC問題いきます。
C問題。ビルド、ステアーズ、階段?
問題文。左右一列にN個のマスが並んでおり、
左からI番目のマスの高さはHIです。
あなたは各マスについて一度ずつ次のいずれかの操作を行います。
マスの高さを1低くするか何もしないか。
操作をうまく行うことで、マスの高さを左から右に向かって
単調比減少にできるか求めてください。
右肩上がりで増やせるかどうか。
入力例はNが5でHの高さは12113。
出力例はES。
左から2番目の2を低くすることで1113という
実質右肩上がりの階段にできます。
入力例2は1321でこれはNO。
Nは10の5乗。HIは10の9乗。4分でいけそうだな。
コードテストで
Nイコールイントのインプット
Lイコールリストのマップの
イントインプット.スプリット
プリントLで確認しておきましょう。
何もしないかマスの高さを1低くするか
4iインレンジ
1スタートのNで
IF Lのi-1番目
どうしようかな。
i-1番目-Lのi番目が
台なり0以上だったら
0以上?1以上かな?
1以上だったら
EXIT.PRINT.NO
何事もなく4分が終わったならPRINT.YES
コードテスト
1個目はYES
2個目はNO
あれ?これと違うね。
マイナス1どうしようかな。
L-1を下げるべきかどうか。
えーっと
1つ差だったら何とかできる。
そっか1回1回アクセスしちゃうと
ややこしくなるのかな?
どうしようかな。
4分の中にJを作りましょう。
Jが大文字のiと大文字のJを作って
Lのi番目と
J
Lのi-1番目
で、これを入れていきたいな。
アペンドしちゃおうかな。
IF
マイナス
どうしたもんですかね。
TMP
1イコールLの0番目
TMP2イコールLの1番目
あー、制約で1以上か。
じゃあちょっとLは1個だけにしといて
TMP2
4分の中にTMP2イコールLのi番目を入れといて
IF
i-1
IF
思いつかないな。
もういちいちアクセスしてみるか。
IF TMP
1が
TMP2より大きかったら
2より大きかったら
Lのi-1
はイコール
TMP
1-1
で、この中でもさらに
1個下げただけじゃダメだったら
もうプリントしちゃおう。
EXIT
プリント
NO
で、他は大丈夫かな。
多分大丈夫だと思うんだけどな。
1個目がNOになっちゃったな。
あ、そうか。TMPを
TMP-イコール1にすればいいんだ。
ERROR
NAME TMP1にしてないね。
TMP-1
もうごちゃごちゃになってるな。
1個目はYES
2個目はNO
NO
0
YES
はーん。
どうしようかな。
1、3、2、1
というか一番最初と一番最後で見比べたらいいのかもしかして。
というわけでもなさそうだな。
いやー、解説見まーす。
もうちょっとで解けそうな感じしましたけどね。
右のマスから順に操作を選ぶことにすると、できるだけ高くしておいた方が後で選択肢が増えるので、何もしなくていいなら何もしない。
そうでなくて右のマスよりもちょうど1高いなら1低くする。そうでないならどう頑張ってもダメなので答えはNO。
はー。
小順じゃなくて高順で計算すればいいのか。
を右から順に行い、うまく構成できればYESを出力することでオーダーNの計算時間で答えを求めることができます。
4分ですね。
また同様の考え方で左から順に行うこともできます。
他の方法としてはI番目までの高さの最大値をMIとしたとき、すべてのIイコール1からNについてHI代なりイコールMI-1が成り立てばYES、そうでなければNOと判定することもできます。
これは機能法によって示すことができます。
実際に?
何これ?
大文字Aの上下反転したあのアスキーアートの笑うときに使う顔文字というか。
なんて読むのこれ。
全小記号ターンA。
あ、これガンダムか。正式名称は?
あ、全小記号なんだ。ガンマとかではなさそうですね。
N1のときは必ず答えはYESです。
回答例が、コード例がないな。
もう一個解説あるので見ますが、Cぷらぷらですね。
単調非現象なので大きくなっていくようにすればいい。
操作ではマスの高さを下げることしかできないため、前半ほど調整が難しくなっていくと予想できる。
なので後ろの方からなるべくマスの高さが高くなるようにマスを下げていって操作が現実、実現できるかを試そう。
うーん。ちょっと他の方の提出例を見つつ勉強しておきます。
では今日はここまで。お疲れ様です。