ABC153 参戦記

こんばんは、ぱんと申します。

昨日はデザインの記事を初めて書きましたが、その勢いのまま、今日は初めてのプログラミングの記事を書いてしまおうと思います。内容としては、本日行われたABC153についてのものになります。言語はPython3。まず最初に、注意書きなど。

※注意※

・【大前提】この記事はABC153のネタバレを含むので、他人のACコードを見ずに自分で解きたい人は見ないでください。
・当分、競プロはPython3でやると思います。重すぎて困ったら他の言語に手を出し始めるかもしれませんが、それはまたのちのち。
・筆者はプログラミング初心者です。ABC全完してない(今回はDまで)し、今後しばらくはまだできないと思います。
・なので、この記事に書いてある解法は嘘解法かもしれません。発見し次第訂正しますが、「こうやったらとりあえず通った」というだけのもので、私の記事に書いてあることがその問題の本来の解法であるという保証はしません。
・それどころか、解けてないor通ってない問題についても書いちゃいます。他の方の解法を見て自分で実装してみる→通る、までできたら加筆しますが、現実的にそこまでできるかは不明。

わたしのアカウント

melon_ms_mtcc - AtCoder

こちらです。
見たら分かりますけど、灰coderです。底辺からのスタート感すごいですが、頑張ります。それでは、やっていきましょう。

A問題

A - Serval vs Monster

問題概要
サーバルが1匹のモンスターと戦う問題。サーバルの攻撃力は固定。

入力(いずれも整数)
・モンスターの体力H
・サーバルの1回あたりの攻撃力(モンスターに与えられるダメージ)A

出力(整数で)
・サーバルがモンスターに勝つために必要な攻撃の回数

コメントなし→実際の提出

h, a = map(int, input().split())

if h // a == h / a:
 vi = 0
else:
 vi = 1

print(h // a + vi)

コメントあり

h, a = map(int, input().split()) # 入力(HとA、面倒なので小文字にした)を受け取る

if h // a == h / a: # h÷aが整数だったら
 vi = 0 # なんにも足さない
else: # h÷aが整数じゃなかったら
 vi = 1 # 1を足す

print(h // a + vi)

変数viは、足すのが0か1なので2進数みたいだなーと思ってBinaryから取りました。

考察
モンスターの体力Hに対して1回あたりAでえいえいって攻撃していくので、何回攻撃が必要か？と聞かれたら

H ÷ Aが整数→そのままH ÷ Aを出力
H ÷ Aが整数でない→H ÷ Aに1を足して出力

すればいいので上のようなコードになったんですが、よく考えたら

切り上げればええやん

……はい。コンテスト中は脳死で実装してたのがバレましたごめんなさい。
というわけで、切り上げを使って実装するとこちら。→実際の提出

import math

h, a = map(int, input().split())
print(math.ceil(h / a))

math.ceil()は切り上げをしてくれる関数です。参照した記事
っていうか3行で終わるじゃん。泣いた。

B問題

B - Common Raccoon vs Monster

はい、切り替えてB問題をやっていきましょう。

問題概要
アライグマが1匹のモンスターと戦う問題。アライグマはN種類の必殺技を使うことができます。必殺技ごとに減らせる体力量が異なる。

入力(いずれも整数)
・モンスターの体力H
・アライグマが使える必殺技の種類N
・アライグマがi番目の必殺技を使ったとき減らせるモンスターの体力A_i
　(iの範囲：1からNまで)

出力(Yes or No で)
・アライグマが同じ必殺技を2度以上使うことなくモンスターに勝つことができるならYes、できないならNo

コメントなし→実際の提出

h, n = map(int, input().split())
a = list(map(int, input().split()))

if sum(a) >= h:
 print("Yes")
else:
 print("No")

コメントあり

h, n = map(int, input().split()) # 入力の受け取り
a = list(map(int, input().split()))

if sum(a) >= h: # 場合分け
 print("Yes")
else:
 print("No")

考察
アライグマが「同じ必殺技を2度以上使うことなくモンスターに勝つことができる」かどうかのみを判定すればいいので、

(全ての必殺技を使って減らせるモンスターの体力の合計)≧(実際の体力H)

かどうかで場合分けし、上の式を満たすときは「できる」つまりYesと出力すればOKです。
Pythonではlistの中身が整数(int)や浮動小数点数(float)である場合、それをただsumにぶちこむだけでlist全体の和を出してくれます。便利ですね。
→sum関数について詳しくはこちら

C問題

C - Fennec vs Monster

問題概要
フェネックがN体のモンスターと戦う問題。フェネックができるのは次の2種類の行動のみで、全てのモンスターの体力を0以下にすれば勝ち。

攻撃：モンスターを1体選ぶ→そのモンスターの体力を1減らす
必殺技：モンスターを1体選ぶ→そのモンスターの体力を0にする

ただし、必殺技を使える回数には制限がある。

入力(いずれも整数)
・モンスターの数N
・フェネックが必殺技を使える回数K
・i番目のモンスターの体力H_i

出力(整数で)
・モンスターに勝つまでに行う攻撃の回数(必殺技は数えない)の最小値

コメントなし→実際の提出

n, k = map(int, input().split())
h = list(map(int, input().split()))

if n <= k:
 print("0")

else:
 h.sort(reverse=True)
 h_new = h[k:]
 print(sum(h_new))

コメントあり

n, k = map(int, input().split()) # 入力を受け取る
h = list(map(int, input().split()))

if n <= k: # 場合分け
 print("0") # この場合は「攻撃」が必要ない

else:
 h.sort(reverse=True) # 降順にソート
 h_new = h[k:] # k+1番目以降をスライス
 print(sum(h_new)) # 足し算

考察
まず、場合分けについて。

(モンスターの数N) ≦ (フェネックが必殺技を使える回数K)

となるときは必殺技を使い切る前にモンスターを全て倒せるので、攻撃する回数は0でいいです(出力回数は「必要な攻撃回数の最小値」であることに注意)。

そうでない場合は攻撃についても考える必要があるが、攻撃回数を最小にするためには先に必殺技で体力の高いモンスターから倒していけばよい。具体的には

h.sort(reverse=True) # モンスターを体力の高い順にソート
h_new = h[k:] # 必殺技では倒しきれなかったk+1番目以降のモンスターの(体力の)リストを作成

こんな感じですね。体力の高い方からk番目までは必殺技で倒せているはずなので、k+1番目以降のことだけ考えます。

sort関数について詳しくはこちら
h[k:]ってなんやねんって人はこちら

※ここで、k+1番目以降の要素を取り出すためにはh[k+1:]ではなくh[k:]とする(indexがずれている)ことに注意してください。理由はPython(ほかの言語も大抵そうだけど)が0-indexだからです。

また、攻撃では1回に体力を1ずつしか減らせないので、

(攻撃回数) = (攻撃で倒す必要のあるモンスターの体力の合計)

となり、sum(h_new)(モンスターの体力の合計)をすればそれがそのまま出力(攻撃回数)になります。

D問題

D - Caracal vs Monster

問題概要
カラカルがモンスターと戦う問題。最初はモンスターが1体だが、途中で分裂(？)する。普通にこわい。 
1ターンに1体選んで攻撃することができて、攻撃対象のモンスターの体力をXとしたとき

X=1→そのモンスターの体力は0になる
X>1→そのモンスターは消滅し、体力が ⌊X/2⌋のモンスターが新たに2体現れる
（⌊r⌋はrを超えない最大の整数を表す）

という感じ。全てのモンスターの体力を0以下にすればカラカルの勝ち。

入力(いずれも整数)
・モンスターの初期体力H

出力(整数で)
・モンスターに勝つまでに行う攻撃の回数の最小値

コメントなし→実際の提出

import math

h = int(input())

a = math.floor(math.log2(h))
print(2 ** (a+1) -1)

コメントあり

import math

h = int(input())

a = math.floor(math.log2(h)) # 体力の底2での対数を取って小数点以下切り捨て
print(2 ** (a+1) -1) # a ** b は「aのb乗」の意

これは考察がないとコメントありを読んでも意味不明っぽいので考察をきっちり書きます(嘘)。

考察
実装した時は証明とかせず「なんか通りそうだから投げちゃえ！w」って感じでした。てきとう。

なんにも分からなかったので、H = 7とかで実験してみたら規則がありそうでした。実験大事。
具体的に言うとH = 7では

7 → 3, 3 → 3, 1, 1 → 1, 1, 1, 1

というふうに3回で全てのモンスターの体力を1にできて、そのあとは体力1のモンスターが4体いるので残り4回攻撃が必要、つまり3 + 4 = 7回攻撃が必要で、これが最小値となります(この、体力1になったモンスターを最後にまとめて倒すのが今回のミソです)。

これって、最初の「3回で全てのモンスターの体力を1にできる」の部分は実際にやらないと分からないかもしれないけど、そのあと「4回攻撃が必要」なことはなんとなくわかりません？だって3回で全部のモンスターの体力が1になるってことは、3回モンスターを分裂させたわけで。ってことは最初は1体だったモンスターは3 + 1 = 4体になっているはずだから、倒すのには4回の攻撃が必要です。ね？

同様に8もやってみました。

8 → 4, 4 → 4, 2, 2 → 2, 2, 2, 2 → 2, 2, 2, 1, 1 → 2, 2, 1, 1, 1, 1 → 2, 1, 1, 1, 1, 1, 1 →1, 1, 1, 1, 1, 1, 1, 1

おいおい、いきなり大変になりすぎでは？？？
ともかく、全てのモンスターの体力を1にするには7回かかり、完全に倒し切るにはあと8回の攻撃が必要です。

ここでなんとなく気づきました。問題では、モンスターの体力X>1のとき、体力が ⌊X/2⌋(⌊r⌋はrを超えない最大の整数)のモンスターが新たに2体現れると言っています。つまり、Hが2の累乗のときは⌊X/2⌋はいつまでも整数なので、始めのHの値と、最後に残る1の個数が一致する(途中でモンスターたちの体力の合計値が減らないため)のです。これは大進歩。

ってことは2の累乗のときに回数が変わって、それ以外のときは同じ回数なんじゃね？？と考えて、H = 15を調べてみたところ、8と同じような感じを辿って回数も同じになりました。あとはこれを式に落とし込んでいけば良さそうです。具体的には

1  1回
2～3  1 + 2 = 3回
4～7  3 + 4 = 7回
8～15  7 + 8 = 15回

というような感じになるので、一般項を求めると

2^n ～ 2^(n + 1) -1    2^(n + 1) -1回

と算出できそうです。ここで、Hが2の何乗より大きく何乗より小さいのかを調べるため、底が2のlogを取ります。今回はその答えの小数点を切り捨てることで、Hから上の式でいうnを求めます。分かりにくいので具体的にいうと、

log_2(7) = 2.807… → n=2(7は2の2乗より大きく2の3乗より小さい)
よってH=7での答えは 
2^(n+1) -1  =  2^(2+1) -1
                   =  2^3 -1
                   = 7

のように出せるわけですね。これが想定解法なのかは知らん。

E問題(ACできてない)

DPらしいです。DPを習得してACしたら舞い戻ってきて続きを書きます。

DPができないのでできるようになるぞ！！！！の気持ちが詰まった私の奮闘記 Part1はこちら↓

最後まで読んでいただきありがとうございます。またどうぞ。

【おまけ】

ひええ、参戦記書くのってこんな時間かかるんですね。4時間はかけた。
普段から書いてる人たちってなにものなんだろうと思いました。すごすぎる……