00:04
AtCoder Beginner Contest 073、A問題、セプテンバー9。問題文、今、日本は9月9日です。
2桁の整数Nが与えられるので、十進法でNにQが含まれるか答えてください。
制約は10以上99以下。入力はNが1つ与えられるだけ。Qが含まれるときは頭が大文字のイエス。
Nが含まれないときは頭が大文字のノー。文字で判定したらいいですかね。
Nイコールインプットプリントイエス。
イフ文字型のQがインNだったらエルスプリントノー。
で、提出してオッケーなはず。2017年9月9日のコンテストですね。はい、ACしたのでB問題いきます。
B問題、シアター。問題文、女医師のお姉ちゃんは劇場の受付を担当しています。
この劇場には席1から席10万までの10万個の席があります。 彼女のメモ書によると今までの間にN組の団体が来て、
I組目の団体は席Liから席Riまでの連続した席に座っています。
今、劇場の席には何人座っているか求めてください。 同じ席に複数の人が座ることはないと。
入力例は以下の形式で標準入力から与えられる。まずN、何組の団体が来ますかっていうのが1行目に来て、そのN組分の団体分、
LとRがそれぞれ開業されて入力されていきます。入力例1はNが1、
1組目の団体というか1組しかいないですね。Lが24、Rが30。 出力例は7。24、25、26、27、28、29、30の席に人が座っており7人ですと。
今、劇場の席には何人座っているか求めてください。なので、 普通にこれNイコールイントのインプットとして
ANSイコールアンサイコールゼロにして、4iインレンジのNで
LとRを入れます。mapのint、input、
.splitでLよりRの方がでかいですよね。だからANSプラスイコールRマイナスLプラス1じゃない?
03:13
プラス1して、4分終わったらプリントANSでいけると思うんですが、一応コードテストしてみましょうか。
入力例1は7が出たらOK。はい、7。 入力例2は
4が出たらOK。4ですね。提出していきます。 演習しました。さあ、疑問のC問題。
C問題。write and erase 問題文。あなたはジョイシのお姉ちゃんと以下のようなゲームをしています。
最初、何も書いていない紙がある。ジョイシのお姉ちゃんが一つの数字を言うので、その数字が紙に書いてあれば紙からその数字を消し、書いていなければその数字を紙に書く。
これをN回繰り返す。その後、紙に書かれている数字がいくつあるかを答える。 ジョイシのお姉ちゃんが言った数字が言った順番にA1からANとして与えられるので、ゲーム終了後に紙に書かれている数字がいくつあるか答えてください。
ゲーム終了後に紙に書かれている数字の個数を出力せよ。入力例はNが3で626、出力例は1。
以下の操作を行うこととなります。紙に6は書かれていないので6を書く。 紙に2は書かれていないので2を書く。紙に6は書かれているので6を消す。
よって最後に書いてあるのは2だけなので答えは1です。 入力例2、Nは4。で、与えられる数字が2、5、5、2ということで出力例は0。
最後に紙に数字が一つも書かれていない場合もあります。 これは
辞書を作ればいいですね。 nイコールイントのインプット。
で、小文字のDICで辞書を作りましょう。
for i in range n
小文字nイコールイントのインプット。
dic
not in 逆だな。
if 小文字n not in DIC だったら
06:05
DICのnは1です。
else nのnがもうすでにDIC書なりに入っていたら DICプラスイコール、DICnプラスイコール1。
で、カウントしていきましょう出現回数を。 ほいで最終的に
偶数ではないやつを計算していけばいいんですが、えっと
あ、MAX10の9乗なんだ、数字が。 辞書の内容物を抽出する法文なんだったっけな。
enumerate じゃなくて、ちょっと調べますね。
python 辞書法文
value とかキーとかアイテムとかがあったはず。 法文、法文。
for k in d.keys もう2つ出しちゃっていいかな。
2つ出すのはアイテム図ですね。 for a b でいいか。
for a b in
dictation じゃない dictionary.items 括弧でいいんですよね。
でその前に ans アンサーを0で法文の外に置いておいて、if あそうか別にこれアイテムの方はいらないのか。
value だけでいいのか。 values でいいか。values で受け取り直そうか。せっかくなので。
せっかくなので。 values
で、じゃあ for v ですね。v indict.values if v%に
victory イコール 0。 偶数だったら ans プラスイコール1。
で print ans
09:03
コピーしてコードテスト。 入力例1は1が出たら ok。
1。入力例2は0が出たら ok。
はい。0。入力例3は2が出たら ok。
極端に大きい数字も出してほしいんですけどね。 コード例に。入力例クリアしたので提出していきます。
6年前なんでちょっと難易度がね、今の c 問題と当時の c 問題だと違うかもしれませんが ac しました。
d 問題やっていきます。 d 問題。ジョイシノズ トラベル。問題文。
アットコーダー国には n 個の町があり、m 本の双方向に移動可能な道で結ばれています。
また、i 本目の道は町 ai と町 bi の間を距離 ci で結んでいます。
ジョイシノお姉ちゃんはこの国の r 個の町 r1 から rr までを訪れることとなりました。
最初に訪れる町までの移動と、最後に訪れる町からの移動は空路で行うが、それ以外は道を使わなければなりません。
町を訪れる順番を道での移動距離が最小となるように決めた場合の移動距離を答えてください。
これが最近の c 問題で出てくるレベルかなっていう印象ですね。
双方向の道なのであれですね幅優先探索など深さ優先探索などで求めるやつかなと思いますが、
あれまだちょっと身についてないんですよね。やっぱり解説見て他の方の提出を見るだけではちょっと身につかないのかなぁと思いつつ解説を見ます。
もう手が出ないのでこれ b 問題違う d 問題
n が 200 以下なので町と町の間の距離はワーシャルフロイド法で求めて問題ない。
ワーシャルフロイド法?何それ調べよう。ワーシャルフロイド法。
ワーシャルフロイド法は重みつき有効グラフの全ペアの最短経路問題を多項式時間で解くアルゴリズムである。
そしてRIの並べ方だがこちらも大文字Rが8以下なのですべての順列について試してみることができる。
順列の生成方法はいろいろ考えられるが深さ優先探索を用いても十分間に合う。
C++で例が書いてますがちょっと他のユーザー解説もあるのでそっちも見て今日終わりにしようと思います。
12:05
前提知識ワーシャルフロイド解法。これもC++ですね。
今回重要な条件があり2小なりイコールラージR小なりイコールmin8かNである。
つまり配列smallrのすべての組み合わせを試すことができる。
C++であればNextPermutation関数ですべての順列を試せる。
あとは2点間の最短距離を高速に求められればいいが、ワーシャルフロイドという手法を使う。
これを使えばオーダーNの3乗で2点間の最短距離が求められるので事前に計算しておく。
ワーシャルフロイド。またちょっと新しいアルゴリズムが。
名前は聞いたことある気がするんですがね。
ということで今回ここまでにしておきましょう。
ではまた次回お疲れ様です。