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

こんにちは、ぐぐりら(<a href="https://twitter.com/guglilac">@guglilac</a>)です。
AtCoderのABC119に参加しました。

全完は出来なかったですがレートはちょっとだけあがってました。笑

本番後に通したDも含めて、参加記録です。

## A

問題文をよく読んでいないので実在するものをちゃんと考えてしまいました、、、
2019年しか入力されないんですね。。

```python
y, m, d = map(int, input().split("/"))
if y >= 2020:
    print("TBD")
elif y <= 2018:
    print("Heisei")
elif m >= 5:
    print("TBD")
else:
    print("Heisei")
```

## B

```python
N = int(input())
s = 0
for i in range(N):
    m, u = input().split()
    if u == "BTC":
        s += float(m) * 380000
    else:
        s += float(m)

print(s)
```
これは大丈夫だと思います。
intとかにしないようにってところでしょうか

## C
これで時間を取られてDが間に合わずでした。

Nが小さいから全探索なんだろうなーと思って書き始めたのですが、途中でいろいろバグらせてかなしでした。

竹を`(group1,group2,group3,unused)`
の四つのグループに分けます。

$4^8=2^{16}$なので、グループ分けを全通りためしても間に合います。

同じグループになったものは合成し、合成だけでA,B,Cを目指して作ったものが下のコードのtempです。

tempをつくるときの合成魔法のcostを計算し、targetであるA,B,Cとtempを比較して足りない分を残りの魔法で微調整します。その時のcostを最後に足します。

解法としては割と早い段階で思いつけたのですが、`unused`グループ(下のコードでいうと四つ目のインデックス)をcostに入れたりとか、tempに0が入っていると成長魔法とかも使えないことを忘れていたりとかでバグらせて時間をロスしました。

それぞれ
```python
scores[:3]
```
や

```python
if 0 in temp:
  continue

```
に該当します。

ACコード

```python
import itertools
N, A, B, C = map(int, input().split())
target = [C, B, A]
L = []
for i in range(N):
    L.append(int(input()))

products = list(itertools.product([0, 1, 2, 3], repeat=N))

ans = float("inf")
for p in products:
    scores = [[0, 0], [0, 0], [0, 0], [0, 0]]
    for i in range(len(p)):
        scores[p[i]][0] += L[i]
        scores[p[i]][1] += 1
    temp = [elem[0] for elem in scores[:3]]
    cost = sum([10 * (elem[1] - 1) for elem in scores[:3] if elem[1] >= 1])
    if 0 in temp:
        continue
    sorted(temp)
    cost += sum([abs(target[i] - temp[i]) for i in range(3)])
    ans = min(ans, cost)
print(ans)

```

(追記)

```
sorted(temp)
```
の部分は間違ってました。

```
temp=sorted(temp)
```
にしないとソートされないです。

ただ、実はソートしなくてもACになります。
全探索しているので、その中にtempがソートされたものが存在して、最適解を求めるのに害はないからです。

## D

時間内には解けませんでした。

$Q$が$10^5$ぐらいだからxが与えられたら即答しないとあかんのかな、でもxがどの辺りにいるかって即答は出来なくね？とか考えてましたが普通に二分探索すればいいですね。
これもロスの原因でした。かなし。

xが与えられたら、sの近いやつとtの近いやつを持ってきて比較すればいいのはわかったのですが、近いやつがxの右にある場合が〜とか細かいことを考えてしまい、わからず。

解説にあるように、sの近いやつの候補(左にある一番近いやつと右にある一番近いやつ)、tの近いやつの候補(左にある一番近いやつと右にある一番近いやつ)を全部試すのが正解なのですが、この中には明らかに答えになりえないものも含まれています。

こういうのを気にしないで簡単に考えるのが苦手だと感じます。。多少無駄があっても簡単に考えて探索する、という考え方を自然にできるようになりたい。

あとは、端っこの処理も地味にきいてきそう。
両隣で最近の点を取ればいいことがわかっても、ただし端っこの場合は片方しかなくて〜っと考えていると考える体力が失われる気がします。端っこは無限、

```python
import bisect
A, B, Q = map(int, input().split())
INF = float("inf")
s = [-INF] + [int(input()) for i in range(A)] + [INF]
t = [-INF] + [int(input()) for i in range(B)] + [INF]

for q in range(Q):
    x = int(input())
    ans = INF
    a_i = bisect.bisect_right(s, x)
    b_i = bisect.bisect_right(t, x)
    for a in [s[a_i], s[a_i - 1]]:
        for b in [t[b_i], t[b_i - 1]]:
            ans = min(ans, abs(x - a) + abs(b - a), abs(x - b) + abs(b - a))
    print(ans)

```

AtCoder:ABC119に参加した

0 件のコメント:

コメントを投稿

このブログを検索

POPULAR POSTS

SPONSORED LINK

RECENT POSTS

TWEETS

ARCHIVES

LABEL

CONTACT