Terada's Blog

フリーランスでソフトウェア開発してます。プログラミング、競プロ、スタートアップなどについて

トップ > AtCoder > ABC119 ただの感想

ABC119 ただの感想

AtCoder Python プログラミング 競プロ

どーもーーー昨日はABCでした。


開始前のツイートですが、見事に不安が的中し、ABのみの2完となってしまいました。。

勉強が全然足りてない！

Cはすごい悔しかったなぁ。。

てなわけで各問題感想文

A:
日付は文字列のまま比較できるとのこと。
でも普通にsplitして月と日を比べましたw
4月は31がないらしいので、月だけ比べれば良いものの、語呂合わせ覚えてなかったのもあったし不安だったので一応日も比べるというアホさw

全く関係ない話ですが、なんたら侍の語呂合わせを覚えたのは、中3で通っていた塾でした。
かなり遅いですね。。


B:
いつも思うのですが、コンテストに参加したら最後に解いていた問題以外記憶から削除されてますw
このデータ構造は？

問題自体は範囲も狭いので普通に足しました。


C:
涙のC。

決しててんで分からないというわけではなかった。しかし解けない。これが恐ろしい。

まず、範囲が3から8ということで、適当に全パターン探れば行けるだろうというところまでは分かった。

しかし、あまり全探索になれていないのもあり、ちょっとほかの方法を探してしまった。

そしてたどり着いたのが、目指す値の一つ目に、全組み合わせを試して一番消費MPが低いものを選ぶ。それを2つめ、3つめにも繰り返し行う、
という謎のアルゴリズム。

実際にはもう少しぐちゃぐちゃした実装をしましたが、通らず。

で、結局模範解答はdfsとかで全探索しているものの、これって8重ループが正義では？と思い以下になりました。

（モバイルなのでインデントが糞）

N, A, B, C = map(int, input().split())
takes = []
for i in range(N):
takes.append(int(input()))
takes = takes+[0,0,0,0,0,0,0]
takes = takes[:8]
g = [A, B, C]
combis = []
for i in range(4):
for j in range(4):
for k in range(4):
for l in range(4):
for m in range(4):
for n in range(4):
for o in range(4):
for p in range(4):
combis.append([i,j,k,l,m,n,o,p])
min_diff = 10**10
for combi in combis:
A,B,C = 0,0,0
for idx, el in enumerate(combi):
if el == 0:
A += takes[idx]
elif el == 1:
B += takes[idx]
elif el == 2:
C += takes[idx]
if A == 0 or B == 0 or C == 0:
continue
A_diff = abs(g[0] - A) + (len([_ for _ in combi if _ == 0]) - 1)*10
B_diff = abs(g[1] - B) + (len([_ for _ in combi if _ == 1]) - 1)*10
C_diff = abs(g[2] - C) + (len([_ for _ in combi if _ == 2]) - 1)*10
diff = A_diff + B_diff + C_diff
min_diff = min(diff, min_diff)
print(min_diff)

教訓は、値が小さければとにかく全探索を考える。
そのためにdfsになれる。
さもなくば、forをめっちゃ書こう、ということ。



D:
Cやってる途中に、もしやこれDが簡単なパターンでは？と思い見てみたら、おお、これは行けそう、と思い手をつけるも途中でやっぱ俺に解けるはずない、と思いやめるという愚行。

こちらはまた解いてみたいと思います。



とにかく、レーティングは上がりました。





次回までにもっと勉強したい。

蟻本のデータ構造のところ、さっぱり分からん。問題がなさすぎて。。