A～Dなら1記事で許されるやろ!ｗ

今回は解説はすべてCythonで書いてます(AtCoderのCyhonはPure python modeなのでPythonのコードのままでもACできるくらいにはとっかかりやすいものです)

C++でのACは自分のコンテスト中の提出履歴を見てもらえると同じ方針で書かれてると思います。

A - Payment

無限に1000円札持ってるの羨ましい...羨ましくない?

1000円札で払える分はすべて払った後に小銭の計算をすれば良さそう。

サンプルは合わせようね(2WA食らった)

cdef:
  int n
n = int(input())
print((1000-(n%1000))%1000)

atcoder.jp

B - Judge Status Summary

C++erは脳死でmap<string, int>でおK。 Pythonerはdictやdefaultdictでやろう。

まあlist.count(string)があるんだけども

cdef:
  int n
  list s
n = int(input())
s = [input()for i in range(n)]
for c in ["AC", "WA", "TLE", "RE"]:
  print(c,'x',s.count(c))

C - H and V

マスは赤く塗ります

(これで少しハマった)

これはbit全探索なる頻出の全探索アルゴリズムです。今回は少し応用が必要なので初めて触る人はけんちょんさんの記事を読んでから取り掛かるといいかも

drken1215.hatenablog.com

今回はこの{行, 列}を赤く塗るかor塗らないを各H,Wに対してみていくと2^H+W 個の候補が発生します。

これを全探索します。

重実装ﾀﾉｼｲ！

import copy
cdef:
  int h,w,k,cnt,ans=0
h,w,k=map(int,input().split())
s=[list(input())for i in range(h)]
for xbit in range(1<<h):
  for ybit in range(1<<w):
    cnt=0
    c = copy.deepcopy(s)
    for i in range(h):
      if xbit>>i&1:
        for j in range(w): c[i][j]='-'
    for i in range(w):
      if ybit>>i&1:
        for j in range(h): c[j][i]='-'
    for i in range(h): 
      cnt+=c[i].count('#')
    if cnt==k:
      ans+=1
print(ans)

atcoder.jp

D - Chat in a Circle

これは考察できるととても気持ちいいやつ

f:id:honehaniwa:20200706022442p:plain — 問題文のやつ

これを見ながら考えるのが一番良さそう。

うーん、降順ソートで上から取る!はもちろんWA。

ではどうするか。

f:id:honehaniwa:20200706023443j:plain — iPad最高!一番好きな考察用紙です!

このように降順にソートしてから最初と2番目に入ってくるやつだけ条件分けして後は前から順番に2回づつ消化するとできそうですね!

サンプルを振り返ると2回使う部分で同じ数字が入ってきてカモフラージュされてるし中々いやらしい

cdef:
  long n, now=0, ans=0
  list a
n=int(input())
a=sorted(list(map(int,input().split())),reverse=True)
for i in range(n):
  if i==0:continue
  ans += a[now]
  if i%2==1:
    now+=1
print(ans)