ABC332 A~D問題

ABC332


atcoder.jp


A問題　Online Shopping

合計金額を出し、送料がどうなるかを確認して出力すればよいです。

c++

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n,s,k,a,b;
  int count=0;
  cin >> n >> s >> k;
  for (int i=0;i<n;i++){
    cin >> a >> b;
    count+=a*b;
  }
  if (count>=s)cout << count << endl;
  else cout << count+k << endl;
  return 0;
}

python

n,s,k=map(int,input().split())
amount=0
for i in range(n):
  a,b=map(int,input().split())
  amount+=a*b
if amount>=s:
  print(0+amount)
else:
  print(k+amount)

B問題　Glass and Mug

単純に、問題にかかれていることを愚直に実行するコードで通ります。

c++

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int k,g,m,count;
  int a=0;
  int b=0;
  cin >> k >> g >> m;
  for (int i=0;i<k;++i){
    if (a==g)a=0;
    else if (b==0)b=m;
    else{
      count=min(g-a,b);
      b-=count;
      a+=count;
    }
  }
  cout << a << " " << b << endl;
  return 0;
}

python

k,g,m=map(int,input().split())
a=0
b=0
for i in range(k):
  if a==g:
    a=0
  elif b==0:
    b=m
  else:
    count=min(g-a,b)
    b-=count
    a+=count
print(a,b)

C問題　T-shirts

ロゴ入りのTシャツは食事に行く時と競技プログラミングのイベントに行くときのどちらも使えるのに対して、無地のTシャツは食事に行く時しか使えないので、無地のTシャツを優先して使います。

持っているTシャツを使える限り使えるように運用して、足りなくなったら一枚購入するようにし、最終的に何枚必要になるか計算して出力すればいいです。

python

n,m=map(int,input().split())
s=list(input())
rotti=[]
hako=""
for i in range(n):
  if s[i]=="0" and len(hako)>0:
    rotti.append(hako)
    hako=""
  else:
    hako+=s[i]
rotti.append(hako)
A=0
B=0
for i in range(len(rotti)):
  hako=list(rotti[i])
  if hako=="":
    continue
  a=0
  b=0
  for ipp in range(len(hako)):
    if hako[ipp]=="2":
      a+=1
    elif hako[ipp]=="1":
      b+=1
  A=max(A,a)
  B=max(B,b+a)
print(A+max(0,B-m-A))

D問題　Swapping Puzzle

いろいろな解き方があると思いますが、ぼくはグリッドの状態をBFSしていく解き方で解きました。

BFSの時、二次元配列などをそのまま使うときは、メモリの同じIDを共有しないように気をつける必要があります←Pythonは。

import copy
h,w=map(int,input().split())
a=[[]*1 for i in range(h)]
B=[[]*1 for i in range(h)]
for i in range(h):
  a[i]=list(map(int,input().split()))
for i in range(h):
  B[i]=list(map(int,input().split()))
stack=[]
stack.append([copy.deepcopy(a),0])
iti=0
count=0
hako=1
for i in range(h):
  for ipp in range(w):
    count+=a[i][ipp]*hako
    hako*=10
irane=set([count])
rotti=[[0]*w for i in range(h)]
while len(stack)>iti:
  #縦に変更
  check=0
  rotti=copy.deepcopy(stack[iti][0])
  for i in range(h):
    for ipp in range(w):
      if rotti[i][ipp]!=B[i][ipp]:
        check=1
        break
  if check==0:
    print(stack[iti][1])
    break
  for i in range(h-1):
    rotti=copy.deepcopy(stack[iti][0])
    a=[]
    for ipp in range(w):
      a.append(rotti[i][ipp])
    for ipp in range(w):
      rotti[i][ipp]=rotti[i+1][ipp]
    for ipp in range(w):
      rotti[i+1][ipp]=a[ipp]
    count=0
    hako=1
    for a in range(h):
      for b in range(w):
        count+=hako*rotti[a][b]
        hako*=10
    if not count in irane:
      stack.append([copy.deepcopy(rotti),stack[iti][1]+1])
      irane.add(count)
  #横に変更

  for i in range(w-1):
    rotti=copy.deepcopy(stack[iti][0])
    a=[]
    for ipp in range(h):
      a.append(rotti[ipp][i])
    for ipp in range(h):
      rotti[ipp][i]=rotti[ipp][i+1]
    for ipp in range(h):
      rotti[ipp][i+1]=a[ipp]
    count=0
    hako=1
    for a in range(h):
      for b in range(w):
        count+=rotti[a][b]*hako
        hako*=10
    if not count in irane:
      stack.append([copy.deepcopy(rotti),stack[iti][1]+1])
      irane.add(count)
 
  iti+=1
else:
  print(-1)


rotti-coder.hatenablog.com