00:03
AtCoder Beginner Contest 164
A問題、シープ&ウルフス 問題文、羊がS匹、狼がW匹います。
狼の数が羊の数以上の時、羊は狼に襲われてしまいます。 羊が狼に襲われるならアンセーフ、襲われないならセーフを出力してください。
はい、大なり小なりでの判定ですね。どっちがどっち、SV、SW、SWイコール、マップ、イント、インプット、ドット、スプリット。
で、プリント、アンセーフが、セーフにしとこうか先。
同数でもアンセーフらしいので、左がシープ、右がウルフだから、
IF、シープ、大なり、W、ウルフだったらセーフ、で、ELSE、アンセーフと提出します。
はい、B問題いきましょう。ACしたので、B問題バトル。 高橋くんと青木くんがモンスターを戦わせます。
高橋くんのモンスターは体力がAで攻撃力がBです。 青木くんのモンスターは体力がCで攻撃力がDです。
高橋くん、青木くん、高橋くん、青木くんの順に攻撃を行います。 攻撃とは相手のモンスターの体力の値を自分のモンスターの攻撃力の分だけ減らすことを言います。
このことをどちらかのモンスターの体力が0以下になるまで続けた時、 先に自分のモンスターの体力が0以下になった方の負け、そうでない方の勝ちです。
高橋くんが勝つならイエス、負けるならノーを出力してください。
A、B、C、Dを受け取ります。マップ、イント、インプット、ドット、スプリット。
体力がAとCで攻撃力がBとDなので、ファイル、トゥルー、いつ終わるか分からないやつはファイル文で回す感じでいきましょう。
高橋くんスタートだからまず高橋くんのモンスターの攻撃力Bで青木くんのモンスターの体力Cを削ります。
03:03
CマイナスイコールB。もしこの時点でCが小なりイコール0、0以下になった場合は高橋くんが勝ちなのでプリントイエスをしたらいいですね。
もしCが小なりイコール0だったらエグジットで囲んどいてプリントイエス。
今度はどっちだ。D。違うわ。AマイナスイコールDですね。
これもif文で囲っておいて、ifA小なりイコール0、高橋くんが負けたらノーをプリント。
これで一応いけるはずですがコードテストしておきましょう。
出力0。1はノー。2個目はイエス。イエスですね。提出していきます。
ACしたのでC問題いきましょう。C問題ガチャ。問題文。
くじ引きをN回行い、I回目には種類が文字列SIで表される景品を手に入れました。
何種類の景品を手に入れましたか?
I回目には種類が文字列Sで表される。
何種類の景品を手に入れたか出力せよ。
入力例1。Nが3でオレンジアップル。出力例は2。
入力例2は5。Nが5で全部グレープなので出力は1。
Nイコールイントのインプット。
Lイコールセットのリストのインプット。
4なんちゃらインレンジNプリントレンエルじゃないのか?
C問題こんな単純なことある?
06:09
入力例1は出力2が出たら正解。
2。入力例2はグレープなので1が出たらOK。
1。入力例3は4が出たらOK。
4。一応Lをプリントして確認しておきます。
内容物が合っているかどうか。合っているね。
で、制約は?
2×10の50以下。
でもインプット、アペンドとかでリスト参照はしてないので
これでいけそうではあるので提出していきます。
6、10、13。
あ、いけましたね。ACしたのでD問題いきましょうか。
3年前ってC問題こんなもんなんだな。
たまたまかな。2020年のコンテストですね。
D問題。マルチプルオブ2019。
問題文。1から9までの数字のみからなる文字列Sが与えられます。
次のような条件を満たす整数の組IJ。
1以上I。IはJより小さい。
で、Sの文字数までですね。
の総数を求めてください。
条件。SのI文字目からJ文字目までを受信数の整数としてみるとこの整数は2019の倍数である。
Sの文字数が1以上20万以下なので全部試せばいけそうな気がしますね。
Sは1から9までの数字のみからなる文字列。
条件を満たす整数の組の総数を出力しよう。
条件を満たすのは1、5、5、9、9、13の3個です。
だから文字の1個目から5個目。
5個目から9個目。
9個目から13個目。
で、整数を作ってそれが2019の倍数という判定があったらカウントさせるですね。
ビットセンターン策とかが入りそうな気はしますけどね。
あーでも違うか。
09:00
I文字目からJ文字目だから。
中空きはないのか。
4分の20ループでなんとかなりそうな気はしますけどね。
やってみましょうか一応。
S。
Sイコールインプット文字列としてもらっておいて。
4Yインレンジ。
LSを連Sで関数変数をとっておいて。
4YインレンジLS。
LSマイナス4とかかな。
2019の倍数なので最低4つは欲しいんですよね。
4Yインレンジ。
Iプラス4からLSまでかな。
プリントでちょっとIとJをもらって。
これ何行ある?
1、2、3、4、5、6、7、8、9、10、11、12、13文字列がある。
13文字列があるってことは
えーと
どこだ。どっからだ。
0、1、2、3。
03スタートだな。
04スタートになっているので
Iプラス3ですね。
一番最後が12。
8、9、10、11。
9、10、11、12。
9。
ちょっとわからなくなってきたな。
1、2、3、4、5、6、7、8、9、10、11、12、13だから
インデックスは0から12まででしょ。
8、9、10、11、12。
1個多いので
Iは7まで出して欲しいから
LS-5ですね。
7、8、9、10、11、
ん?7、8
あ、違うわ。9、10、11、12か。
9まで出して欲しいんだ。
9まで出して欲しいから
-3ですね、こっちも。
LS-3までがI。
で、えー
12:04
imientosれておいて
tmp
tempラリーイコール
tmptemporary
tMPtemporary
sのI番目から
sのI番目から
j番目まで。
if
ENT
INT
TMPが
パーセント
2019で
もし2019でこの区切ったところが 割り切れるなら cnt プラスイコール
1 でいっちゃん最後にプリント cnt ですね これでいけるんじゃない
2 2じゃなかったね多分ね3だった ねあれsjプリントsjプリントijsの
i番目からjプラス1番目かなな気が してきたなやっぱそうですねなので
じゃあiプラス4からだな 2だな2のままだな問題はもう一回
よく見ましょうか次のような条件 を満たすi文字目からj文字目まで
を実施数の整数と見るとこの整数 は2019の倍数であるいやあって
そうだけどな11あ一番最後が入って ないってことはjプラ1だなjプラ
1ってことはlsプラス1かjの範囲 がレンジiプラス4からlsプラス1
までこれで全部探索できるはず 3ですねokokで入力例2は2入力例
3は0入力例がクリアできたので 提出していきますどうだろうな
15:22
20万のREが出たREってなんだっけ 実行時エラーWAと違うのかな実行
時エラーちょっと調べよう実行 時エラーkyoproでよく出すRE実行
時エラーについてkyoproで出ると 腹が立つエラートップ3に入る
であろう実行中エラーコンパイル 時にエラーは出ず0除算文字通り
0で他の値を割ることですあれかな そのtmpに入れた2019の倍数かどうか
を測るための区切りのところが 全部0だったとかもあるかもしれない
ですね だからif int tmp ==0だったらcontinue
にしたらどうでしょうかやって みようか201900000000これで1個が
出るはず9まあまあまあ全部0だったら 0が出るねこれで大丈夫だと思
うんですけどね一旦出してみて まだREとかが出るようであれば
ちょっと考えますREだなREだな 同じところはREしてますね配列
変数を存在しないインデックス で指定するああそうかそもそもの
文字数をオーバーしてる可能性が あるのかプラスとかマイナスとか
出しちゃうからめんどくさいな じゃあもういいかマイナス3とか
18:07
考えないで普通にもう全部1から 数えていきましょうLSまででいける
のかなもう1回ちょっと入力例を 1番だけ試してerror invited literal for
int with base if i jからの文字列 になってますって言われたのi
プラス1か4j in range iプラス1から lsまでだと2でしょlsプラス1iプラス1
からlsプラス1まで3ちなみにこの 時のint i jは054983合ってるねちょっと
これで駄目だったら解説見て今日 終わりにしたいと思いますREですね
同じところ実行エラーになってます 解説d問題abctsの長さをnsの左から
k番目の数字をakとします左から kプラス1文字目以降の数字列を
整数とみなしたときの値anプラス 10an-1プラス…をdkとしますする
とijが条件を満たすのはti-1==tjmod2019 のときです各timod2019を計算し
modの値が同じごとに個数を計算 して足したものが答えですこれは
dpで計算できmodごとにm-1割る2を 足せばいいですユーザー解説も
21:10
あるので見てみます似たような 問題を最近解いた覚えがあった
ので解法自体はすぐに思いついた こういう区間数え上げは片方を
全列挙してもう片方を高速に数え 上げるのが定石法ハイを全算割
したときに条件を満たすjが何通り あるかを計算しようnum i i文字
目からn-1文字目までの数という ふうに考えてみようするとiを
固定したときに条件を満たすj というのはnum i-num jプラス1割る
10のi-jプラス1乗が2019の倍数である 個数を数えることになる
ここで2019は3673であることを考える と10で割るということは2と5で割る
ということになり3673の因数の個数 には影響を与えないつまり10で
割る計算は2019の倍数であるかの 判定には関係ないことになる
よって条件はnum i-num jプラス1 が2019の倍数であるかを見れば
よい
さてこれでだいぶやりやすくなった 再計するとiを固定したときに
条件を満たすjはnum i-num jプラス 1が2019の倍数あればいい
なので条件を満たすjは2019の倍数 ということをmod2019で考えるように
するとnum i-num jプラス1イコール 0mod2019num iイコールnum jプラス1
mod2019ということになる
なのでnum iを2019で割った余りと i以降のnum jで2019で割った余り
が等しいjの個数が今回の条件を 満たす
よってcntmこれイコールじゃないん ですよね何なんだろコロンイコール
num jイコールmmod2019であるjの個数 を集計しながら答えを計算して
いくと答え
cnt配列の集計をしながら行うので iはマツビから全探索していく
あとは上の解説とソースコード を見ながら実装については読み
解いていってほしいということで うーんって感じですね
まあc問題まで解けたのでよし としましょう今回はd問題他の方
の提出を見てちょっと落とし込 めそうであればなるほどねとやって
24:03
おこうと思います
ではまた次回お疲れ様です