00:04
ゲームフリーク Programming Contest 2023） AtCoder Beginner Contest 317）
A問題。ポーションズ。問題文。
ナオヒロくんはモンスターを飼っています。 モンスターの現在の体力はHです。
また、ナオヒロくんはN種類の傷薬を持っています。 傷薬は効き目の弱い順に1からNまでの番号がついています。
傷薬Nをモンスターに与えると、モンスターの体力がPのN番目分増加します。 ここで、P1小なりP2…だから、小順ですね。が成り立ちます。
ナオヒロくんは傷薬を1つモンスターに与えることで、モンスターの体力をX以上にしたいです。
目標を達成できる傷薬のうち、最も効き目の弱いものの番号を出力してください。
性悪化において、そのような傷薬が存在することが保証されています。 はい、ということでゲームフリーク、ポケモンの会社の
主催というか、プロモーション?の… プロモーションは違うな。
後ろにいるコンテストですね。はい、やっていきます。 なんて言うんだっけ?スポンサー?全然出てこなかったな。
NHK、NHKイコール…
あ、ちょっと待って、お文字になってる。 半数にして、NHKイコールマップイントインプット
ドットスプリット。で、2行目にP、傷薬の効果、イコールリストの
上をコピーします。マップイントインプットドットスプリット。 で、入力例を
コードテストに入れておいて、入力例はNが3、Hが100、K…Kじゃない、Xだ。Xが200。
で、ポーションは50、200、999。出力例は2。 それぞれの傷薬をモンスターに1つ与えた時のモンスターの体力の変化はいかの通りです。
傷薬1をモンスターに与えるとモンスターの体力は100プラス50。 2を与えると100プラス200。3を与えると100プラス999。
与えた後に体力がX、200以上になっている傷薬は傷薬2と傷薬3。 そのうち最も効き目の弱い傷薬である傷薬2が答えになります。
ということで、 モンスター1匹だけですね。
現在の体力がHなので、4分でこのポーションの数を少ない順から足していって、
03:02
その何番目のポーションを足した時に初めて目標のX以上になったら、もうその番号を出力すればいいので、普通に4分でいきます。
SoIinRangeN。
If PのI番目プラスHが
DynallyCallXだったら、exit
print i plus 1。
0インデックスなので。
1番は2が出ました。出力例2は2が出る。 入力例3は4が出る。
提出していきます。 ACしたのでB問題いきます。
B問題ミッシングナンバー。 問題文。
直博くんはNプラス1個の連続する整数を1個ずつ持っていましたが、そのうち1個をなくしてしまいました。
残っているN個の整数が順不動でAのリストとして与えられるので、なくした整数を求めてください。
なお、なくした整数が1位に定まるような入力のみが与えられます。
制約Nが2以上100以下で、Aの数も1以上1000以下なので、これも4分で良さそうですね。
入力例1。Nが3。Aが2、3、5。出力例は4。直博くんははじめ2、3、4、5の4個の整数を持っており、4をなくし2、3、5が残っていました。
Nプラス1個。 連続する整数。
なくした整数が1位に定まるような入力。 だから端っこがなくなることはないんですね。
なので、そんな相当とかは考えなくて、相当じゃないや。
端っこだった場合、1だった場合とか1000だった場合とかを考えなくていいですってことですね。
Nイコールイントのインプット。 Aイコールリストのマップの
イントインプット.スプリットのドット相当でいける?
プリント大文字Aでちょっと確認。 順不動になっているのは入力例2ですね。
06:09
Nが出る。 ソーテッド?
ソート括弧の中に入れるんだっけこれ。 いつもソートとソーテッドの
使い分けがうまくいかないんですよね。 ソーテッドにしてみる。
ソーテッドリストのマップのイントのインプットドットスプリット。 ダメだなぁ。
ん?括弧の数が足りないって言ってる。 言ってるね。
あー出ました出ました。 ソーテッドだったら出ましたので
4iインレンジAの0番目から Aのマイナス1番目プラ1までにしておいて
If I not in 大文字AだったらExit
プリントIでいいんじゃない? 思いついたけど今。
7。 7ですね。入力例3は151。
151。はい。 提出していきます。
はいACしたのでC問題いきます。C問題。 リメンバーリングザデイズ。問題文。
ある地方に1からNの番号がついたN個の街と1からMの番号がついたM本の道路はあります。
うわぁ。 道だ。
I番目の道路は街Aiと街Biを双方向に結び長さはCiです。 道っていうかグラフ?
好きな街からスタートして同じ街を2度以上通らずに別の街へ移動するときの通る道路の長さの和としてあり得る最大値を求めてください。
Nは10個。だから街の数は10個で。
はいはい。Ci。
長さなので
09:04
とりあえずちょっとうろ覚えの知識を入れていきましょうか。
NとMイコールマップの
というか後で調べますね。イントインプット
ドットスプリット
じゅっちゅうはっくこれBFS? 長さ優先探索かなんかなので
でABCC
I番目の道路は
だから長すん? I番目の道路は街Aiと街Biを双方向に結び長さはCiです。
I番目の道路。Cっていうリストがいるな。
Cっていう空のリストとAっていう空のリストとBっていう空のリストがいる。で、方をIインレンジ
M。M?本当?
M本の道路。そうだね。合ってるね。で、えーっと
うーん
そうか。AとB。
いやまあいいか。えーっと
A
B、Cイコールマップの
イントインプット
ドットスプリットで大文字A
ドットアペンド
えーっと
これは
プラス1したほうがいいのか?関係ないな。総和だもんな。あんまり関係ないな。
ふんふんふんふんふん。
んーっと
Cには、大文字のCには普通にドットアペンド
Cするだけでいいんですよ。
AとBに何入れたらいいの?っていう話で
多分AのB番目に
っていう話ですよね。Aの
えー
A番目の道路は町Aiと町Biを双方向に結び
A番目の道路は町Aiと町Biを双方向に結び?
12:08
だから一番目の道路は町Aの1と町Bの1
2番目の道路は町Aの2と町Bの2を繋いでるってこと?
ってことはグラフっていうよりは
はしごうみたいな形になってるってことか。
好きな町からスタートして同じ町を2度以上通らずに別の町へ移動する時の通る道路の長さの和としてあり得る最大値を求めてください。
DPかこれ。
えーーーー
より大きい方を大きい方でとっていくか。
ふーんっと
同じ町を2度以上通らずに
だから
めちゃくちゃ長いやつが
連続してたらもうぐるぐる回る感じ…ぐるぐるの発音おかしかったな。ぐるぐる回る感じでいいんですよね。
極端に短い道路が極端に長い道路の隣にあった場合は
一旦スルーした方がいいのか?
いや、待てよこれ。
全部行ったら良くない?結局。
ん?
4132と移動すると通る道路の長さは1110となります。
あ、ん?
入力例ちゃんと見てなかった。
あーやっぱりグラフになってますね。そりゃそうか。
はしごなわけないわな。
あー図も書いてくれてるわ。
はーい失礼しました。
じゃあどうすんの?えーっと。
Nの数が10個。
Nの数。この場合Nの数関係あるな。10だもんな。10の数スタートだから。
より大きい方大きい方で取るべきなのか。
んーいやちょっと思いつかないですね。解説見るか。早々の諦めが大切。
C問題はDFSで全探索。はぁはぁはぁはぁはぁ。
15:03
やっぱりそっち系でしたね。
具体的には?
この問題はDFSにより解くことができます。現在いる町、既に行ったことのある町の集合、今までに通った道の長さの合計を保持しながら、まだ行ったことのない町へ移動するDFSをします。
計算量はオーダーN×Nの解乗であり、十分高速に動作します。
なお競技プログラミングにおいては実装の簡略化などの理由で、持つべき状態をDFSの筆記数として渡す代わりにグローバル変数を更新するような実装がしばしばなされます。
実装例でPythonがありますね。
リスト0×n±1
Eはどれだ?
町の数かな?
レンジn±1
町、道路かな?
for i in range m
abc mapint input.split
Eのab2c
Eのba2c
はぁーこうやるんだ。ちょっと真似しようか。
nとmイコールマップの
int input.split
Eが二重リストですね。
中のリストに0×n±1
for i in range n±1
n±1にしているのは多分
0インデックスじゃないからオーバーしちゃうからですね。そのまま使うと。0インデックスにしたかったらaとbをそれぞれ-1したらいいよってことだと思います。
で、道路を受け取る。for i in range mabcイコールマップ
int input.split
Eのab2c
Eのba2c
も2つの町をつなげる道路ができました。
で、ansuイコールゼロの
used false × n±1。道路を使ったかどうかですね。used
イコール
リストのfalse × n±1
18:04
で、関数ですね。DFSを作っていきます。
def dfs
括弧 引数はvs
まあ引数名は正直その人その人で違うんであれなんですが
グローバルアンス。グローバルアンスにすることでこの関数内でアンサー変数に干渉できるようになった
used v
usedのv番目イコールトゥルーにします。道路を使いました。
if sだいなりアンサー
イコールアンサーはs。だからanswerイコールマックス
アンサーかsかですね。アンサーの数を更新します。
for i in range 1からn±1まで。
for i in range 1からn±1まで。
で、何をフォーブンするんですか。if not used i and eのvi
if not used vi and eのviの場合
dfs あーえっとなんて言うんだこれ内部構造じゃなくて
関数の中にその関数の名前を入れこさせる技ですねこれ
dfs i カンマ s プラス e の vi
i カンマ e の s プラス vi
何やってるのかちんぷんかんぷんですね現状 逆だ s プラス
e の v s プラス e の vi 番名
でユースト v イコールフォルス これはフォーブンの中フォーブンの外ですね
ユースト v イコールフォルス
21:01
が関数です
for in レンジ1から n プラス1まで 1から n プラス1まで
dfs の i 0 d dfs の i 0で最後プリント
アンス コピーはできたはず実行1110
問題をもう1回出さないと c 入力01110ですね入力で3は20
20入力0には1 1ですね
よいしょはい提出しておいて 何が起きているのかをちょっと最後確認して終わろうと思います
通るか12なんかめっちゃ重いぞ めっちゃ重いぞこれいけるあ tle した
おっとおっと
おっとっと
パイパイで提出してみようかな1回 これでもダメだったらちょっと行動を見直しますねどっか間違えてるかもしれない
パイパイだとやっぱサクサクですねあ14で止まったを一体って言った ああ ac しました
パイソンだと dfs 詰まるんだなぁ で何が起きているのかを確認
n と m を受け取りますいい いいがその道のコストですね道路の長さ
をそれぞれの街の数分
20リストで作ってます で m で道路を受け取りますいいの a いい番目といいの ba 番目がそれぞれ道路
つながっているので c を入れます アンサーイコール0ユーズドは全部フォルスにして n プラス1番目回
1回分 使ったか使ってないかの判定としてリストを使ってますねここだな関数 dfs
アンサーをグローバル変数で定義しておいてユースと部位 はいはい最後の4分で
dfs i 0でスタートしているのは0回目 0番目から始まるよということですね
24:05
ユースと部位まず0番目の街1番目の街がトゥルーになった アンスイコールマックス安生数
s はそうはだね現状のカウントだね だから最後の方分で0になっているんだ第2引数が
フォワーインレンジ1から n プラス1まで 2分のっと言うすと a
もしまだ道路が使われていないフォルスかつ いいの vi 番目
がだからゼロじゃなかったらってことか道路がつながってたら そこからまた dfs を始めるよ
dfs のその引数は i 番目からスタートして
ていうか i 番目からスタートというか続きってことですね 続きからスタートして s プラス
e の vi 番目道路の数たすよ道路の長さたすよ この4分が抜けたら
ユーズとの部位番目はフォルスに戻しますよ初期化しますよってことですね はいで4 i 最後の関数全部完了スタートのいっちゃん最後の判定で
フォアインレンジ1から n プラス1でそれぞれ i 番目スタートの アンサーはゼロから始まりますよ
ですね
これ 読んで解説に読んで
解き方とか答えとかがなんとなくこう 文字じゃなくてイラストとしては出てくるんですけど
これをこういうコードに落とし込むっていうのが本当に 全然できてないな
入れ子にする発想とかも全然なかったもんな dp カーとか言ってましたもんね はい勉強になりましたいつかちょっと空でかけるようになったらいいなぁと思います
ではまた次回お疲れ様です