00:04
AtCoder Beginner Contest 094。 A問題。Cats and Dogs。
問題文。猫と犬が合わせてAプラスB匹います。 このうちA匹は猫であることがわかっていますが、残りのB匹は猫と犬のどちらであるかわかっていません。
このAプラスB匹の中に猫がちょうどX匹いるということはあり得るかどうか判定してください。
猫がちょうどX匹いるということがあり得るならイエスを、あり得ないならばノーを出力せよ。
入力例1見てみましょうか。Aが3、Bが5でXが4。 B5匹のうち猫が1匹、犬が4匹であれば猫の数は合計でXイコール4匹になります。
だからAプラスBがXより大きければ、X以上であればイエスということですね。
A、B、Xイコール、マップ、イント、インプット、ドットスプリット、プリント、全部大文字のイエス、
イフ、AプラスB、ダイナリーイコールX、エルス、ノーでいけるはず。提出。
2018年のコンテストですね。和が出ましたね。
3つ和が出てるな。なんでだ?
以上だったらダメ?問題文もっかいちゃんと見ようか。
の前に、自分の提出したコードをコピペストいて。
よいしょ。あり?
猫と犬が合わせてAプラスB匹います。このうちA匹は猫と犬が合わせて。
2匹すべてが猫であっても猫の数の合計はXイコール6匹に足りません。
ちょうどじゃないからダメなんだね。
3匹すべてが犬であっても猫の数の合計はXイコール2匹より多くなってしまいます。
じゃあ、ANDだね。
AプラスBダイナリーイコールX&AがX以下である。
03:03
状態のみイエスですね。提出。
これで和だったら、よし、ACでした。
ちゃんとコードテストしようって思ってたけど大丈夫でしたね。
B問題。トール・ゲーツ。問題文。
Nプラス1個のマスが左右に一列に並んでいます。
これらのマスには左のマスから順に0からNまでの番号が付けられています。
あなたは最初マスXにいます。
隣り合うマスの間は自由に移動することができ、マス0またはマスNにたどり着くとゴールすることができます。
ただし、Iイコール1からMについて、マスAIには料金所があり、そのためマスAIに移動してくる際には1のコストがかかります。
なお、マス0、マスX、マスNには料金所がないことが保障されます。
ゴールするまでにかかるコストの最小値を求めてください。
NMXと数列Aが与えられますので、とりあえず入れましょう。
NMXイコールマップイントインプットスプリット。
Aイコールリストのマップのイントインプットスプリット。
NMXイコールマップイントインプットスプリット。
NMXイコールマップイントインプットスプリット。
NMXイコールマップイントインプットスプリット。
NMXイコールマップインプットスプリット。
NMXイコールマップインプットスプリット。
NMXイコールマップインプットスプリット。
NMXイコールマップインプットスプリット。
06:23
NMXイコールマップインプットスプリット。
NMXイコールマップインプットスプリット。
NMXイコールマップインプットスプリット。
NMXイコールマップインプットスプリット。
09:26
C問題。
C問題。
メニーメディアンズ。
問題文。
Lが奇数の時、L個の数AIからALの中央値とは?
A1から、あ、AIじゃないね。
A1でしたね。失礼。
A1からALの中で、2分のLプラス1番目に大きい値のことを言います。
ん?
N個の数X1からXNが与えられます。
ここでNは偶数です。
Iイコール1からNに対して、X1からXNからXIのみを除いたもの。
すなわち、X1、X2、XI-1、XIプラス1…XNの中央値をBIとします。
Iイコール1からNに対して、BIを求めてください。
何言ってんの。
Nイコール20万以下。2以上20万以下。
Nは偶数。
XIは1以上10の9乗以下。
N行出力せよ。I行メニューはBIを出力せよ。
え?どういうこと?
XI…Lが奇数の時…
Nは何?N個の数。はいはい。
数列Xの数ですね。なのであんま関係ないな。
ここでNは偶数です。
ん?
Lが奇数の時、Iイコール1からNに対して、XI…
順繰りに取れってことか。
1個目を除外した中央値、2個目を除外した中央値っていうのを出力しろってことですかね。
多分10の9乗だから4分は難しいよみたいな話かな?
入力例1のXは2,4,4,3。
2,4,4,3の1個目は、1個目の2がないので4,4,3ですね。
12:02
4,4,3の中央値は4なので、
2分のIプラス1番目。
Iじゃないわ。2分のLプラス1番目。
2分のLプラス1番目。
3個あって、4でしょ。2番目に大きい値。
リストにすればいいのか?
Nは20万個あるんだな。
これ4分無理か?
1回ちょっとやってみましょうか。
Nイコールイントのインプット。
Xイコールマップのイントのインプット。
リストのマップのイントインプット。
ドットスプリット。
で、Xの4分ですね。
4、はい、インレンジ。
N回出力します。
何を出力するんですか?
プリント。
Xの、そうか、インデックス数が分からないのか。
だから、SP、スプリット変数を用意して、
何かを割るにしないといけない。
何を割るってなると、
Nプラス1かな?
Nプラス1割る2。
で、
Xのi番目を除外したいので、
わけわかんなくなってきた。
毎回Xのコピーを取るのはアリか?
20万回あって、
毎回Xを参照してってなると面倒か?
15:02
もうちょっとで思いつきそうなんですけどね。
スプリット、Nプラス1割る2。
スプリットまで、
ん?そうだね、サム。
いや、サムしちゃダメなのか?
あー、ダメだ。ちょっと詰まっちゃった。
解説見ます。ユーザー解説。
よくよく考えると、中央値となりうる候補は2種類しかない。
配列Xを想像したものを配列Aとすると、
Aの2-1分のNか、
Aの2分のNのどちらかが答えになる。
Aの2-1分のNが答えになる場合は、
消した数がAの2分のNからAのN-1にある場合であり、
Aの2分のNが答えになる場合は、
消した数がA0からAの2-1分のNにある場合である。
ある数を消すときは、相当積みの数の中で最も早く出てくるところが消える。
よってIDXのX番目、
相当積み配列Aの中で数Xが最も早く出てくる座標を使って判別していこう。
一応公式の解説もあるので見ていきますが、
結構古いコンテストの解説って単文なんですよね。
しかもC問題に限って答えねえや。
ABはC++とPythonの解答例を貼ってくれてるのに。
入力を相当したものをY1小なりイコールY2小なりイコール…YNとします。
このときBIを考えます。
相当した後にAIがLI番目に現れるとします。
すなわちYLIイコールAIが成り立ちます。
BIはY1からYN、YLIを除いたY1からYNの中央値であることに注意します。
するとY1小なりイコール…YLIを抜いたYNまでより、
このN-1個の値のうち2分のN番目の値を求めればよいことがわかります。
これはLI小なりイコール2分のNであれば、
Yの2分のN、LI大なりイコール2分のNプラス1であれば、
Yの2分のNになることが確かめられます。
18:01
他の方のデースコードを見ておこうと思います。
さっぱりだなあ。
これなんか数学的な考えっていう感じなんですかね。
ではまた次回お疲れ様です。