00:03
AtCoder Beginner Contest 121回目。A問題。ホワイトセルズ。問題文。
H行W列の白色のマス目があります。あなたはH個の行とW個の列を選び、選んだ行または列に含まれるマス目をすべて黒色で塗りつぶします。
白色のマス目はいくつ残るでしょうか。なお、残る白色のマス目の数は行や列の選び方によらないことが証明できます。
入力例32-21。出力例は1。3行2列の白色のマスがあり、2行と1列を選んで黒色で塗りつぶしたとき、白色のマス目は必ず1個だけになります。
3行2列。ああ、小文字型に塗りつぶすってことか。まあ、どこでもいいのか。
32が6。だから2行目に与えられる大文字HWが白色のマス。
一番最初の状態で小文字HWが黒色のマスで、Wゾーンがあるから
マイナス1したらいいのか。かける2、3、32が6、入力例2、5、5、2、3、5、5、25、2、3が6。
5行5列。ちょっと考え方がわかんないな。
32-21。大文字HWイコールマップイントインプットドットスプリット。小文字のHWイコール1行目のコピー。マップイントインプットドットスプリット。
で、どうしようかな。
03:01
大文字HWからそれぞれ小文字HWを引いて、引いて、引いたらどうなる?
5、5、2、3、3、2が6。引いてそれをそれぞれかけたらいいのかな。
プリント、大文字、括弧大文字H-小文字H×括弧大文字W-W。
出力例じゃない、入力例はこれでクリアはできるんですが、6でしょ。
出力例3は0。果たしてこれでうまくいくのかっていうのはちょっと疑問ですね。一応もう提出しちゃおうか。
できなかったらもうちゃんと表を作って消していこうと思う。あ、いけた。提出しましたのでB問題いきます。
B問題。Can you solve this?問題文。N個のソースコードがあり、I個目のソースコードの特徴はAのI1、AのI2、AのIMのM個で、M個の整数で表されます。
また整数B1からBMと整数Cが与えられます。 AのI1×Bの1プラスAのI2×B2…AのIM×BMプラスCがダイナリ0のときに限り、
I個目のソースコードはこの問題に正当するソースコードです。 N個のソースコードのうち、この問題に正当するソースコードの個数を求めてください。
入力がNMCが1行目に与えられ、2行目にBが与えられ、そこからはAが数列として与えられます。
ちょっとよくわかんないなとりあえず nmc ね n m c
で次が b リストマップイントインプットドットスプリットで
リスト a を 毎回とって大丈夫なのかどこかに一塊にしないといけないかはわかんないので
06:00
一旦置いときます 入力例
n が 2 n は何のこのソースコード
n がに m が
さん c がマイナス10 出力例は1以下のように2個目のソースコードのみこの問題に正当します
ああはい2行目に与えられる b の数列 と
産業名以降に与えられる a の数列のそれぞれ同じインデックス数をかけてで足していって でプラス c したのが
0より大きければ 正当だとでそれが何個ですかだから
普通に ns イコールゼロにして
フォアインレンジ 何個って言ってた n 個
n の b 使ったものをコピペしよう b イコールリストのインプットマップイントインプット
ん a ですね a イコールリストのマップのイントインプットドットスプリット
を j インレンジ
m の前に
大文字 sum 合計値を 保存する変数がいる
sum プラスイコール a の j 番目
かける b の j 番目かな
で if sum
プラス c が 0以上だったら cnt ans プラスイコール1
んでプリント
ans 出力例1は1それくれにはに
3は0 0だね ok そうなので提出していきます
09:01
はい ac しましたので c 問題いきます c 問題 エナジードリンクコレクター問題文
栄養ドリンクにレーティング上昇効果があると聞いたたかし君は m 本の栄養ドリンクを買い集めることにしました
栄養ドリンクが売られている店は n 件あり i 件目の店では1本 ai n の栄養ドリンクを b
iphone まで買うことができます 最初で何円あれば m 本の栄養ドリンクを買い集めることができるでしょうか
なお与えられる入力では十分なお金があれば m 本の栄養ドリンクを買い集められる ことが保証されます
c 問題だからナップサックじゃなくて dp かな普通に
かけないって 入力は nm で n 個 a b が与えられます
m が 答えというか
最小の欲しい数ですね 最小金額を出せばいい
どうしようかな と
1本 a アイフォンの栄養ドリンクを b アイフォンまで買うことができます 安い順
にしたらいいんじゃないの普通にこれ フォーゾーザ dp とかしなくても
nm が与えられるこれはマップインとインプットドットスプリット
さっきの問題に解説をそのまま流用します で
大文字 l イコールからのリスト oi インレンジ
n ええ
と 小文字の a と b イコール
マップのインとインプットドットスプリット
で l ドットアペンド カッコ a b
で l ドットそうとしたら
プリント l これで金額分金額順になるんじゃない
なってるね だから
a
でも中の後所を怖いがやってみるか ファイル
12:11
ファイル m がゼロだゼロより大きかったらをやって
アンサーアンサーイコールゼロ a b イコール
l ドットポップ ポップゼロでうまいこといくかな
イフ m マイナス b は
ゼロ以下になっちゃうなら アンス
プラスイコール
かける m でブレークそうでなければ
m マイナスイコール
b でアンスプラスイコール
かける b っていうのを無限にやっていって最後プリントアンスで
いかがでしょうか 12
入力例1は12入力例2は130 130
入力で3は1000うわぁ出力が32ビット整数系に収まらないことがあります 収まらなさそう
なぁ辛うじて 辛うじてちゃんと出てるっぽいので
とりあえず出してみましょうか なんかオーバーしてそうな気がするけどな
パイパイで出さないといけないとかあるかな あーちょっと重そう
6まで行ったけど あーTLE
1回試しにパイパイで出してみましょうか
Pythonとパイパイの使い分けがイマイチよくわかってないけど なんか処理長いやつにはパイパイがいいって
ばあちゃんが言ってた 提出
15:05
考え方は合ってるっぽいですね ただ
あーダメだね引っかかるね だからそもそもパイパイの使い方はこうじゃないってことだな
同じとこで突っかかりましたので解説見てみましょうか c 問題 c 問題
えっと 安い店から順に m 本の柄名取りを買うのが最善です
柄名取りしたがって ai の小さい順に相当して m 本に達するまで前から順に変えるだけ買うことを
シミュレーションすれば答えを求めることができます 相当の方法はいくつかありますが例えば c プラプラではベクターペア
イントイントに組 ai bi をすべて入れて相当関数を呼ぶことで想像することができます
あれ 計算量は相当部分がボトルネックでオーダー n ログ n です
考え方まんまだなぁ ってことはどっかでちょっとオーバーしてるんだなポップが邪魔だったのかな
相当してみず少ない順にやってるポップがいらない 余計だった
うーん ポップ使わないやり方で行ってみますか1回
ind インデックスイコール0から始めて a b イコール l の
ind で i nd プラスイコール1 多分一緒だと思うんですけどね
これでできなかったらちょっと後で c プラプラじゃなくてパイソンで出している他の方のやつを見ようと 思います
一応ぱいぱいで出してみよう
通った エーシースターポップがダメなんだへ
ポップ関数がダメなんだなぁ
なるほどなるほど勉強になりました ありがとうございます
これちなみにパイソンでも通る それちょっと最後に確認して
感覚をつかもうと思いますパイソン 通るねー
パイソンでも通るねー うーん
なるほど わかりましたではまた次回お疲れ様です