00:03
AtCoder Beginner Contest 156回目、A問題、ビギナー。問題文、高橋くんはプログラミングコンテストサイト、BadCoderの会員です。
BadCoderの会員には2つのレーティング、内部レーティングと表示レーティングが割り当てられています。
表示レーティングは、その会員のコンテスト参加回数が10以上の時は内部レーティングに等しく、そうでない時は会員のコンテスト参加回数をKとして、内部レーティングから100×10-Kを引いたものになります。
高橋くんのコンテスト参加回数がNで、表示レーティングがRである時、高橋くんの内部レーティングを求めてください。
出力例は、入力例1、2と2919、出力例1は3719、コンテスト参加回数が10より少ない2であるため、内部レーティングから100×10-2、10-2、イコール800を引いたものが高橋くんの表示レーティングになっています。
よって高橋くんの内部レーティングは2919プラス800。
はいはい。表示内部レーティング。表示レーティングは10以上だったら内部レーティングと同じ。
そうでない時は、会員のコンテスト回数をKとして、内部レーティングから100×10-Kを引いたものになります。
引いたものになりますなのに足すんだな。ちょっとその辺よくわかってないけど。
まあいいや。
NとR。表示レーティングが表示されます。
マップイントインプットドットスプリットでプリントをR。
If Nが代なりイコール10、10回以上だったらそのまま内部レーティングを出せばいい。
そうでなければ、else Rプラス100かけさらにかっこして10-Nかな。
03:06
で、提出。はい、ACしたのでB問題いきます。
B問題、Digits。問題文。整数Nを係数で表した時、何桁になるかを求めてください。
係数表記については、Wikipedia暗いどり、あたいどり?
暗いか。暗いどり奇数法を参照してください。ということでリンクがありますが。
整数Nを係数で表したい時は、そのNを係でひたすら割っていって、余りを右に取っていくんだっけな。左に取っていくんだっけな。
どっちかでいけるはずです。確か。
なので、11と2。Nが11で2進数で表したい時は、1011になりますと。
実力例は4桁なので4ということですね。
さっき言った方法でできるかどうかちょっと試してみましょうか。
NとKがマップイントインプットドットスプリットでSイコールからの文字列にして、リストでいいかLイコールからのリストにして
while N が代なり0の間、l.appendをn%Kでn÷Kで一応プリントLで確認してみたら
1101
逆順ですね。だからその割った余りを入れていって、最後に反転させればN進数、K進数で判定することができます。
出力例2は11101を10進数ででなると7桁ですね。
06:07
入力例3は、だから最終的にこれを今出すのは連Lですね。Lの長さが必要なので。
大丈夫そうなので提出していきます。
ACしたのでC問題いきます。
C問題。ラリーかな。問題文。数直線上にn人の人が住んでいます。
i番目の人が住んでいるのは座標xiです。あなたはn人全員が参加する集会を開くことを考えています。
集会は数直線上の任意の整数値の座標で開くことができ、座標pで集会を開くとき、i番目の人は集会に参加するために
xi-pの事情の体力を消費します。 n人が消費する体力の総和としてあり得る値の最小値を求めてください。
DPとかナップサック問題とかがパッと思い浮かびますけどね。最小値。
いろんなパターンを見ていって、その最小値を求めろっていうのに大体使われている印象があるんですが。
とりあえずコードテストを入れてみましょうか。 nとx。
nイコールintのインプット。 xじゃなくてlにしておこうか。
lイコールリストのマップのイントインプットドットスプリット。
入力例1は1,4。 出力例は5。座標2で集会を開くとき、1番目の人が消費する体力は1-2の事情で1。
2番目の人が消費する体力は4-2の事情で4。 よってこの総和は5です。
これが2人が消費する体力の総和としてあり得るくらいの最小値です。
集会を開くことができるのは整数値の座標だけであることに注意してください。
nが100以下でxも100以下なら、4分でいいかなという気もするんですが。
09:03
整数値の座標で開くことができ、座標pで集会を開くとき、i番目の人が。
だよね、いけそうだね。 1回それでやってみましょうか。
ans イコール 10の9乗とかにしといて。
for i in range
どうしようかな。 min l だとあれかな。
1番目座標に。 多分この範囲内なら
いけそうですよね。 min l から max l までにしといて。
max l プラ 1ぐらいにしておこうか。
で、i plusイコール1。
んーっと。
どうか、二重ループか。 for j in range n。
1個目の方分のとこに
大文字の sum 変数を0で定義しておいて。
問題は x i マイナス p。
p がだから今回 i なんだな。 ちょっとわかりにくいから p って書いておいて。
2個目の方分に i をしといて、で、リストも x に戻して
min x から max x プラス 1まで p 座標を定義します。
で、座標は
x i マイナス p の事情。 x i マイナス p の事情。
12:06
かけるかける2。
これが x p にしといてイコール
x の a 番目マイナス p の事情。
これを sum にプラスイコールしていきます。 x p。
いや、x p しなくていいか。 もう直に
sum に足していきます。
で、最後 ans イコール min
ans か sum か。
で、プリント
sum。で、理論上はいけそうだけど。
はい、問題文1は
0が出てきちゃいましたねー。なんで?
あ、そうか。min で取ってるから
それより小っちゃいっていう意味では
0が出てくるわな。
なんで0が出てくる?
そっか。sum にプラスイコール1してねーや。
プラスイコール9。
5ですね。違うねー。
sum をちょっと
1回1回プリントしてもらいましょうか。
sum
955599。5が出てるな。5が出てるから5でいいんだけど。
5が出てるから5でいいんだけどな。なんで5が出てこない?
ns イコール min の ans
うーん。
なんでだ?
プリント ans
9559
一瞬5が出てる。
5が出てて9になってる。
なんでだ?
sum 0
15:03
sum プラスイコール
ん?
小目の方文で p をプラスイコール1にして
いや1にしなくてもいいのか。
0始まりじゃないから。
うーん。
なんでだ?
プラスイコール
ans イコール min
より小さい方を出す。
sum
5から
9になってるのはなんでだ?
あ、プリント sum 出してるからだ。
プリント ans じゃないと一番最後?
超絶ボンミスですね。
ボンミスというかもう
ただの
コード見間違え。入力2は2354。
2354。
入力例2つクリアしたので提出していきます。
どうだ?
和が出た。和が出た。
2つはですね
12個 ac してて2個
ミスがあります。
問題文もう一回ちょっと見ておきましょうか。
これで解けそうになければちょっと
答えを
解説を見て
今日終わろうと思いますが
座標 p
1
1から100まで。1から100まででも取るかな?
x は n 個。
座標 p の方を100
で取ってみましょうか。
101とかにしといて
これで一回出してみようかな。
多分
ダメだと思うけど。
18:03
あ、ac した。
えーどういうことだろう。
ちょっと理屈わかんないので解説一応見ておきますね。
ccc
範囲をやっぱり多めに広く取ることが大事なんですね。
人が住んでいる座標の中で最も小さいものを l 最も大きいものを r とします。
この時 x 小なり l または r 小なり x となるような座標 x で周回を開くケースを考える必要はありません。
ですよね。
一番小さいものより
さらに小さい座標
または一番大きい座標
よりさらに大きい座標で開く必要はないはずなんですが
さっきの取り方だとあってそうなんだけどな。
というのもそのようなケースでは座標 l や r で周回を開く時と比べて参加するために消費する体力が小さくなることはないからです。
厳密には例えば x イコール r プラス d
d 大なり 0 とかける座標 x で周回を開く場合
相番目の人が周回に参加するために消費する体力は
なんかいっぱい書いてますね。
うーん。
このアイディアをもとに周回開催場所の候補として調べる必要のある座標をたかだか100個まで減らすことができます。
周回の開催場所を一つ固定した時、
ヌニンが消費する体力の相和はオーダー n 回の演算で計算することが可能です。
よって残った開催場所の候補すべてを調べて、最も消費する体力の相和が小さいものを見つけるアルゴリズムが十分高速に動作します。
まあだから今回はその判定範囲が狭めだからマックスでもう取っちゃって範囲内の
で一個ずつ精査していけば解けるよって言ってるんだと思うんですけど
なんでさっきの提出1個目のがダメだったんだろうなっていうのは
min x max x max x プラス1だったら
いけたのかなぁもしかして max x の1個前までしか出ないので1回ちょっとこれプラス1で
4 p インレンジ min x から max x プラス1までで提出
言ったねやっぱりそういうことですね max x その場所に x の一番大きい場所に座標を設定するという正解がどこかにあった
それを1個目のコードでは その設定できていなかったので
21:00
wa になっていたというだけですね
ちょっと外がうるさいので今日この辺にしておきましょうか ではまた次回お疲れ様です