高橋くんと家族のシャンプー
AtCoder Beginner Contest 243回目、A問題、シャンプー。
問題文、高橋くんの家には高橋くん、高橋くんの父、高橋くんの母の3人が住んでおり、全員が毎晩、風呂で髪を洗います。
風呂には高橋くんの父、高橋くんの母、高橋くんの順に入り、それぞれシャンプーをA、B、Cミリリットル使います。
今朝の時点で、モトルにはVミリリットルのシャンプーが残っていました。
このまま補充しない時、初めてシャンプーが不足するのは、誰が使おうとした時ですか?ということで、V、A、B、Cが与えられます。
初めてシャンプーが不足するのは、高橋くんの父が使おうとしたならばF、母が使おうとしたならばM、高橋くんが使おうとしたならばTを出力せよ。
V、F、M、T、MAP、INT、INPUT、.SPLIT。
While trueでいいや、true、V-F。
FVが0より小さかったらEXIT PRINT Fで同じ文をお母さんと高橋くんの文を作りましょう。
FVが0より小さかったらEXIT PRINT M。
FVが0より小さかったらEXIT PRINT Tで同じ文をお母さんと高橋くんの文を作りましょう。
B問題ヒット&ブロー
問題は長さNの整数列A,Bが与えられます。Aの要素は全て異なります。Bの要素も全て異なります。
次の2つを出力してください。
1.AにもBにも含まれ、その位置も一致している整数の個数。
言い換えるとAiイコールBiを満たす整数Iの個数。
2.AにもBにも含まれるが、その位置は異なる整数の個数。
言い換えるとAiイコールBjを満たす整数の組Ijの個数。
答えを2行出力せよ。1行目には1ドットの個数、2行目には2ドットの個数を出力せよ。
1も数も同じものの個数。
1は違うけど数が同じものが入っているものの個数。
出力例1,Nは4,Aの数字列は1,3,5,2,Bは2,3,1,4,
出力例1,1行目は1,2行目は2,
AにもBにも含まれ、その位置も一致している整数は3の1個だけ。
AにもBにも含まれるが、その位置が異なる整数は1と2の2個。
制約が自由の球状だから。
Nイコールイントのインプット。
Aイコールディストマップ。
イント、インプット、ドット、スプリット。
Bも同じく。
フォーアイレンジN。
アンス1イコール0。
アンス2イコール0。
アイイコールイコールDI。
アンス1にプラスイコール1。
IF AIに
B&AI
これはあれだな。
AIとBIを変数に入れちゃった方が多分軽いですね。
そこまでB問題で考える必要はないと思うけど。
A大文字IとB大文字Iに変えました。
B問題ヒット&ブロー
AIがもしBの列の中にあって、かつこのAIの要素とBIの要素がノットイコールだったら
半数2にプラスイコール1でプリント半数1でいいんじゃない?
コードテスト、入力例1は12が出たら正解。
12、出力、入力例2は00、はい、 入力例3は32が出たら正解。
32ですね。 コードテストをクリアしたので提出してみましょう。
はい、ACしたのでC問題に行きます。 C問題コリジョン2
1は問題文。 xy 座標平面上に n 人の人がいます。人 i は xy yi にいます。
すべての人は異なる地点にいます。 lr からなる長さ n の文字列 s があります。
人 i は si イコール r ならば右向きに、 si イコール l ならば左向きに、一斉に同じ速度で歩き始めます。
ここで右は x 軸の正の向き、左は x 軸の負の向きです。
例えば x1 y1 イコール 2 3
x2 y2 イコール 1 1、x3 y3 イコール 4 1、s イコール r r l の場合は次の図のように動きます。
1番と2番の人が右に、3番の人は左に動いています。
反対の向きに歩いている人同士が同じ地点に来ることを衝突と呼びます。
すべての人が歩き続けた時、衝突は発生しますか?
歩き続けた時なので衝突が発生するかどうかだから
まず y 軸が一緒の人だけを抽出すればいいですね。
とりあえず入力例は
n が与えられて x y が n 個与えられる。
えーどうしたもんですかねぇ。
n が与えられて x y が n 回与えられるから
空のリストにするべきか否か。
x と y の空のリストを作ってみましょうか。
とりあえず。
辞書を作るべきか。
y だけを保存しておきましょうか。
座標リストと y の空のリストを作っておいて
4 y インレンジ n x y イコールマップの
インプットとスプリット。
で、
if y が
in y にある場合
座標.append
あーどうしようかな。
座標.append
いやー難しいねこれは。どうしたもんかねぇ。
座標.append
二重リストにするか。
i プラス一番目の人が
x 座標 y 座標にいますよ。
else y.append y を入れてあげてください。
あーでもこれだと一個目の人の x が与えられないのか。困っちゃった。
x と y やっぱり空の文字列リストでいるか。
x.append 小文字 x
y.append 小文字 y
で文字列 s が与えられます。インプット。
どうしようかな。
r,r,l
多分
これ 4 分 20 ループって
いやギリいけそうな気するな。
2 かける 10 の 5 乗の
20 ループっていけるっけ。ダメな気する。
いけそうな気もする。
y 軸が同じものを抽出したいから
y 軸が同じ。どうやって抽出する?
y 軸 y 軸
for in 連字
y どうしようかな。
大文字 l のリストを作って
for in 連字
というか for y in y
で
if
heart
y.count 小文字 y が
1 より多かったら
l.append
いやー違うな。違うわ。
解説を見ます。
考え方は合っていると思うんだけどな。
まず競技プログラミングを始めたばかりの人は愚直に人を左右に動かしてシミュレーションすることを考えてしまうかもしれません。
しかしこの問題では n 以上
2 かける 10 の 5 乗
x,y 以下
以上 10 の 9 乗以下と
膨大な人数及び空間での話をシミュレートしないといけないため、愚直なシミュレーションでは計算資源が到底足りません。
このような場合、適切な考察によって高速な判定アルゴリズムを構成する必要があります。
そのためにはまずどのような条件の時に衝突が発生するかを定式化するのが大事です。
これなしでは適切なアルゴリズムを構成することができません。
さて、早速衝突が発生する必要十分条件を求めましょう。
すると、適切な考察により
1P と 1Q が衝突する必要十分条件は次の通りとなります。
1P と 1Q の y 座標が同じである。
1P の x 座標が 1Q より小さいならば、1P は右を、1Q は左を向いている。
逆の場合は向きも逆になる。
このように条件を言い換えることで、この問題は上の条件を満たす人の組が存在するかという問題に帰着することができました。
よってフォームで P Q をすべて操作すれば解けると言いたいところですが、
これではオーダー n の事情をかかってしまい TLE するので、さらなる高速化が必要です。
もう少し考察を深めてみましょう。
y 座標が同じ人たちを集めた時、この人たちの間に衝突が発生するのはどのような条件かというのを整理しましょう。
するとこれは右を向いている人のうち一番左にいる人と、左を向いている人のうち一番右にいる人が衝突するかどうかが必要十分条件になっていることがわかります。
言い換えると、y 座標が同じ人からなる集合の中では、上の説明にある2人以外は重要でないということです。
よって2つの、次の2つのキー、値を要素とする連想配列を持って適切計算していけば、衝突の有無を高速に判定できます。
詳細なアルゴリズムは実装例を参考にしてください。
right min キーを k とした時、y イコール k であり、かつ右を向いている人のうち最も x 座標が小さい人。
left max キーを k とした時、y イコール k であり、かつ左を向いている人のうち最も x 座標が大きい人。
計算量は order n あるいは order n log n です。いかに、Pythonでの実装例を貼ります。やったー、Pythonだ。
def x for i
x のリスト、y のリストを作ってそれぞれに x,y の座標をアペンドするまでは良さそうですね。
でいくと、あ、辞書を作ってるんだなぁ。
if si 番目が r だったら、if yi in left max and xi が left max
なんだなんだ。 yi 番目、es r だったら
あーちょっとこれちゃんと読んだら分かりそうなのでちょっとちゃんと読んでおきますね。
これアルゴリズムで言ったら何になるんだろう。名称ないのかなこれ。 じゃあちょっと裏で勉強しておきます。ではまた次回お疲れ様です。