AtCoder:ABC117に参加した-ぐぐりらにっき

とりあえず参加したので記事を書きました。

コンテスト中はDまで解けましたが、Dがあやしいです。

今度またやり直そうと思います。とりいそぎこんなかんじで。。。

## A
```python
x, t = map(int, input().split())
print(x / t)
```
pythonだと`x//t`としない、とかそれぐらいですかね。

## B
```python
N = int(input())
L = list(map(int, input().split()))

if sum(L) > 2 * max(L):
    print("Yes")
else:
    print("No")
```

定理の通り、Lの最大と残りの辺の和の大小を比べればよく、こんなかんじ。

## C
コマをうまく$X_i$をカバーするようにおく問題。

最初、$X_i$の固まっている集団の中心にコマをおいて行きたくなるけど、真ん中におくと行ったり来たりして無駄なので、一つのコマが担当する集団が決まったら、その集団の端っこにおくのが良いことがわかります。

集団に分けたらそれらの端っこにコマをおいて端から舐めていけばいいので、集団の端から端の長さ分だけコストがかかるわけです。

考えやすくするために$X_i$をソートします。

コマが一つだと、$X_i$の最小から最大までの長さ分動かないといけなくて、二つになるとその間のどこか一つの移動を省くことができます。

一般にコマが$N$個あれば$N-1$個の間の移動を省略できるので、ソートした後の$X_{i+1}-X_i$が大きいものから$N-1$個省いていけば残った部分が答えです。

```python
N, M = map(int, input().split())
X = list(map(int, input().split()))
X.sort()
sa = [X[i + 1] - X[i] for i in range(M - 1)]
sa.sort()
if N >= M:
    print(0)
else:
    print(sum(sa[:M - N]))

```
$N\ge M$の部分を忘れて1WAでした。はあ。

## D

コンテスト中にACしたコード。

```python
N, K = map(int, input().split())
A = list(map(int, input().split()))

binary = [bin(a) for a in A]
bin_K = bin(K)
ma_len = max([len(e) for e in binary] + [len(bin_K)]) - 2
B = [e[2:].zfill(ma_len) for e in binary]
bin_K = bin_K[2:].zfill(ma_len)
ans = 0
X = []

flag = False
for i in range(ma_len):
    num_1 = 0
    num_0 = 0
    for j in range(N):
        if B[j][i] == "0":
            num_0 += 1
        else:
            num_1 += 1
    if num_1 >= num_0:
        added = "0"
        if bin_K[i] == "1":
            flag = True
    else:
        if flag:
            added = "1"
        else:
            if bin_K[i] == "1":
                added = "1"
            else:
                added = "0"
    if added == "1":
        ans += 2**(ma_len - i - 1) * num_0
    else:
        ans += 2**(ma_len - i - 1) * num_1
    # X.append(added)

print(ans)
# print("".join(X))

```

* 左から見ていって1と0の個数を数えて少ない方と同じ数字をXにいれる。
* Kの制約で1を入れられない場合は0にする。
* Kの制約では1も0も入れられるけど0をいれた場合は、それ以降はKの制約によらず1も0も入れられる

みたいな解法です。

ですが

ツイッターでも拡散されてましたが、

```
5 2
2 2 0 0 0
```
というケースで6がでてしまいます。(正解は9？)

どうなんでしょう。

Kの中で1がでてきたらそこを0にして、残りを貪欲に求めて足し合わせる、というのを1が立っている全てのbitに対して探索して、最大のものを出すのかなあ、と思ったのですが一回提出してWAとTLEまみれで力尽きました。。。

今度やります。

## 追記

やりました。

AtCoder:ABC117-Dに苦戦したので復習した

AtCoder:ABC117に参加した

0 件のコメント:

コメントを投稿

PROFILE

このブログを検索

POPULAR POSTS

SPONSORED LINK

RECENT POSTS

TWEETS

ARCHIVES

LABEL

CONTACT