rotti_coderのプログラミング

A問題　2023

Pythonだとスライスが便利です

s=list(input())
for i in range(len(s)-1):
  print(s[i],end='')
print("4")

#include <bits/stdc++.h>
using namespace std;
int main()
{
  string s;
  cin >> s;
  for (int i=0;i<s.size()-1;i++)cout << s[i];
  cout << 4 << endl;
  return 0;
}

B問題　Tetrahedral Number

全探索で通ります。

n=int(input())
for i in range(n+1):
  for ipp in range(n+1):
    for k in range(n+1):
      if i+ipp+k<=n:
        print(i,ipp,k)

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin >> n;
  for (int a=0;a<=n;a++){
    for (int b=0;b<=n;b++){
      for (int c=0;c<=n;c++){
	if (a+b+c<=n)cout << a << " " << b << " " << c << endl;
      }
    }
  }
  return 0;
}

C問題　Loong Tracking

すべての座標をリストに入れて添字をいい感じにする

n,q=map(int,input().split())
rotti=[]
for i in range(n):
  rotti.append([n-i,0])
count=0
for i in range(q):
  a,b=input().split()
  if a=="1":
    x=rotti[len(rotti)-1][0]
    y=rotti[len(rotti)-1][1]
    if b=="R":
      rotti.append([x+1,y])
    elif b=="L":
      rotti.append([x-1,y])
    elif b=="U":
      rotti.append([x,y+1])
    else:
      rotti.append([x,y-1])
    count+=1
  else:
    print(rotti[n-int(b)+count][0],rotti[n-int(b)+count][1])

D問題　Loong and Takahashi

一番外側から順番にまいていくようにすれば簡単です。

n=int(input())
rotti=[[-1]*n for i in range(n)]
rotti[n//2][n//2]="T"
hako=["R","D","L","U"]
iti=0
a=0
b=0
for i in range(n*n-1):
  rotti[a][b]=i+1
  if hako[iti]=="R" and b+1<n and rotti[a][b+1]==-1:
    b+=1
    continue
  elif hako[iti]=="D" and a+1<n and rotti[a+1][b]==-1:
    a+=1
    continue
  elif hako[iti]=="L" and b-1>=0 and rotti[a][b-1]==-1:
    b-=1
    continue
  elif hako[iti]=="U" and a-1>=0 and rotti[a-1][b]==-1:
    a-=1
    continue
  else:
    iti+=1
    if len(hako)==iti:
      iti=0
  if hako[iti]=="R" and b+1<n:
    b+=1
    continue
  elif hako[iti]=="D" and a+1<n:
    a+=1
    continue
  elif hako[iti]=="L" and b-1>=0:
    b-=1
    continue
  elif hako[iti]=="U" and a-1>=0:
    a-=1
    continue
for i in range(n):
  print(*rotti[i])

E問題　Non-Decreasing Colorful Path

そもそもこの問題だと、書いてある整数が大きい頂点から小さい頂点に行くことは絶対にできないので最初に辺を削除します（値が小さい頂点から大きい頂点しか行けない有向グラフにする）

その後、その頂点に来るまでに何通りの方法があるかDPします。

ここで、同じ数字かつ連結関係にある頂点たちは、まとめて一つの頂点ということにします。

n,m=map(int,input().split())
amount=list(map(int,input().split()))
rotti=[[]*1 for i in range(n)]
same=[[]*1 for i in range(n)]
irane=set()
for i in range(m):
  a,b=map(int,input().split())
  if amount[a-1]==amount[b-1]:
    same[a-1].append(b)
    same[b-1].append(a)
    irane.add(a)
    irane.add(b)
  elif amount[a-1]>amount[b-1]:
    rotti[b-1].append(a)
  else:
    rotti[a-1].append(b)

irane_rotti=set([1])
iti=0
stack=[1]
while len(stack)>iti:
  hako=stack[iti]
  for i in range(len(rotti[hako-1])):
    if rotti[hako-1][i] in irane_rotti:
      continue
    irane_rotti.add(rotti[hako-1][i])
    stack.append(rotti[hako-1][i])
  for i in range(len(same[hako-1])):
    if same[hako-1][i] in irane_rotti:
      continue
    irane_rotti.add(same[hako-1][i])
    stack.append(same[hako-1][i])
  iti+=1

dp=[0]*n
dp[0]=1
stack=[]
a=[]
hako=amount[0]
for i in range(len(amount)):
  if not i+1 in irane_rotti:
    continue
  a.append([amount[i],(i+1)*-1])
a=sorted(a)
for i in range(len(a)):
  stack.append(a[i][1]*-1)
iti=0
irane_num=set()
while len(stack)>iti:
  hako=stack[iti]
  if not hako in irane:
    for i in range(len(rotti[hako-1])):
      dp[rotti[hako-1][i]-1]=max(dp[rotti[hako-1][i]-1],dp[hako-1]+1)
    iti+=1
    continue

  if hako in irane_num:
    iti+=1
    continue
  irane_num.add(hako)
  
  hako2=[hako]
  iti2=0
  irane2=set([hako])
  while len(hako2)>iti2:
    hako=hako2[iti2]
    for i in range(len(same[hako-1])):
      if same[hako-1][i] in irane2:
        continue
      hako2.append(same[hako-1][i])
      irane_num.add(same[hako-1][i])
      irane2.add(same[hako-1][i])
    iti2+=1
  irane2=set()
  count=0
  for i in range(len(hako2)):
    hako=hako2[i]
    count=max(count,dp[hako-1])
    for ipp in range(len(rotti[hako-1])):
      irane2.add(rotti[hako-1][ipp])
      #dp[rotti[hako-1][i]-1]=dp[hako-1]+1
      #stack.append(rotti[hako-1][i])
  for i in range(len(hako2)):
    hako=hako2[i]
    dp[hako-1]=count
  irane2=list(irane2)
  for i in range(len(irane2)):
    hako=irane2[i]
    dp[hako-1]=max(dp[hako-1],count+1)
  iti+=1
print(dp[n-1])

2024-01-29

ABC334 A~E問題

ABC334

A問題　Christmas Presen

条件分岐

a,b=map(int,input().split())
if a>b:
  print("Bat")
else:
  print("Glove")

B問題　Christmas Trees

ｌとｒが負の整数か、それとも正の整数かで３つに場合分けして、いい感じに割り算をします。
条件分岐の内容としては、ｌとｒがどちらも負の整数の場合、片方が負の整数でもう片方が正の整数の場合、２つとも正の整数の場合の３つに場合分けします。

a,m,l,r=map(int,input().split())
l-=a
r-=a
if l<=0 and 0<=r:
  hako=1
else:
  hako=0
if l>=0 and r>=0:
  print(r//m-(l-1)//m+hako)
elif l<0 and r>=0:
  print(r//m+abs(l)//m+hako)
else:
  print(abs(l)//m-(abs(r)-1)//m+hako)

C問題　Socks 2

まず、この問題は、持っている靴下の合計が偶数か奇数かで場合分けします。

もし偶数の場合は全ての靴下を使うことになり、愚直に靴下の色をソートして、前から２つずつをペアにしていけばよいです。

もし奇数の場合は少し面倒なことになります。基本的には偶数のときと同じように、ソートして前から２つずつをペアにしていく…ということをすればいいのですが、奇数の場合は一枚あまることになります。その余る一枚を決めるのが少々めんどくさいところです。

ぼくは、前と後ろから累積和をとり、いい感じにやりました。こうすることで、その靴下を使わないなら奇妙さの総和はいくつになるか…が一回の計算で求まります。

全ての靴下に対してこの計算をすれば答えが出ます。

n,k=map(int,input().split())
a=set(list(map(int,input().split())))
hako=(2*n-k)//2
rotti=[]
for i in range(n):
  if i+1 in a:
    rotti.append(i+1)
  else:
    hako-=1
if len(rotti)%2==0:
  ans=0
  for i in range(len(rotti)//2):
    ans+=abs(rotti[i*2]-rotti[i*2+1])
  print(ans)
  exit()
a=[0]
b=[0]
for i in range(len(rotti)//2):
  a.append(a[i]+abs(rotti[i*2]-rotti[i*2+1]))
for i in range(len(rotti)//2):
  b.append(b[i]+abs(rotti[len(rotti)-1-i*2]-rotti[len(rotti)-1-i*2-1]))
ans=1000000000
for i in range(len(a)):
  ans=min(a[i]+b[len(b)-1-i],ans)
print(ans)

D問題　Reindeer and Sleigh

与えられた配列Rを累積和にします。
そして、クエリが与えられるたびに二分探索で何匹目まで運べるかを求めます。

import bisect
n,q=map(int,input().split())
amount=sorted(list(map(int,input().split())))
rotti=[0]
for i in range(len(amount)):
  rotti.append(rotti[i]+amount[i])
for i in range(q):
  a=int(input())
  hako=bisect.bisect(rotti,a)
  if hako==len(rotti):
    print(len(rotti)-1)
  elif rotti[hako]==a:
    print(hako)
  else:
    print(hako-1)

E問題　Christmas Color Grid 1

制約をみる限り、全てのマスに対して”＃”をおいたときにグリッドの緑の連結成分数がいくつになるかを求めても実行時間は大丈夫そうなので全探索します。

h,w=map(int,input().split())
rotti=[[]*1 for i in range(h)]
for i in range(h):
  rotti[i]=list(input())
rotti2=[[-1]*w for i in range(h)]
done=[[0]*w for i in range(h)]
count=0
for i in range(h):
  for ipp in range(w):
    if done[i][ipp]==1 or rotti[i][ipp]==".":
      continue
    done[i][ipp]=1
    stack=[[i,ipp]]
    iti=0
    count+=1
    while len(stack)>iti:
      a=stack[iti][0]
      b=stack[iti][1]
      rotti2[a][b]=count
      #ue
      if a-1>=0 and done[a-1][b]==0 and rotti[a-1][b]=="#":
        stack.append([a-1,b])
        done[a-1][b]=1
      #migi
      if b+1<w and done[a][b+1]==0 and rotti[a][b+1]=="#":
        stack.append([a,b+1])
        done[a][b+1]=1
      #sita
      if a+1<h and done[a+1][b]==0 and rotti[a+1][b]=="#":
        stack.append([a+1,b])
        done[a+1][b]=1
      #hidari
      if b-1>=0 and rotti[a][b-1]=="#" and done[a][b-1]==0:
        stack.append([a,b-1])
        done[a][b-1]=1
      iti+=1

q=0
p=0
for i in range(h):
  for ipp in range(w):
    if rotti[i][ipp]=="#":
      continue
    q+=1
    hako=[]
    #ue
    if i-1>=0 and rotti[i-1][ipp]=="#":
      hako.append(rotti2[i-1][ipp])
    #migi
    if ipp+1<w and rotti[i][ipp+1]=="#":
      hako.append(rotti2[i][ipp+1])
    #sita
    if i+1<h and rotti[i+1][ipp]=="#":
      hako.append(rotti2[i+1][ipp])
    #hidari
    if ipp-1>=0 and rotti[i][ipp-1]=="#":
      hako.append(rotti2[i][ipp-1])
    hako=set(hako)
    if len(hako)==1:
      p+=count
    elif len(hako)==0:
      p+=count+1
    elif len(hako)==2:
      p+=count-1
    elif len(hako)==3:
      p+=count-2
    elif len(hako)==4:
      p+=count-3


def kouyaku(a,b):
  while a>0 and b>0:
    if a<b:
      b=b%a
    elif a==b:
      return a
    else:
      a=a%b
  return max(a,b)
def koubai(a,b):
  return a*b//kouyaku(a,b)
count=kouyaku(p,q)
p=p//count
q=q//count


for i in range(1000000):
  p+=998244353
  if p%q==0:
    print((p//q)%998244353)
    break

2024-01-28

ABC333 A~E問題

ABC333

A問題　Three Threes

愚直に実行！

n=int(input())
for i in range(n):
  print(str(n),end='')
print()

B問題　Pentagon

気合で条件分岐しました。
Twitterなどで見かけましたが、いい感じの文字列を作り与えられた入力が部分文字列化どうかで判定するスマートなやり方もあるそうですね。

Python

a=list(input())
a=sorted(a)
hako=""
for i in range(2):
  hako+=a[i]
a=0
if hako=="AB":
  a=1
elif hako=="AE":
  a=1
elif hako=="AC":
  a=2
elif hako=="AD":
  a=2
elif hako=="BC":
  a=1
elif hako=="BD" or hako=="BE":
  a=2
elif hako=="CD":
  a=1
elif hako=="CE":
  a=2
elif hako=="DE":
  a=1
b=list(input())
b=sorted(b)
hako=""
for i in range(2):
  hako+=b[i]
b=a
a=0
if hako=="AB":
  a=1
elif hako=="AE":
  a=1
elif hako=="AC":
  a=2
elif hako=="AD":
  a=2
elif hako=="BC":
  a=1
elif hako=="BD" or hako=="BE":
  a=2
elif hako=="CD":
  a=1
elif hako=="CE":
  a=2
elif hako=="DE":
  a=1

if a==b:
  print("Yes")
else:
  print("No")

C問題　Repunit Trio

全列挙が間に合う制約です。

rotti=[]
count=1
for i in range(100):
  rotti.append(count)
  count*=10
  count+=1

hako=[]
for i in range(100):
  for ipp in range(100):
    hako.append(rotti[i]+rotti[ipp])
hako2=[]
for i in range(len(hako)):
  for ipp in range(len(rotti)):
    hako2.append(hako[i]+rotti[ipp])
hako2=sorted(list(set(hako2)))
n=int(input())
print(hako2[n-1])

D問題　Erase Leaves

１から出ている木それぞれをまるごと消すのに何回操作する必要があるかを計算し、一番操作が必要な木ひとつを除き、全て削除すればいいです。

何回操作する必要があるかを求めるには、端の葉からDPを行えばよいです。

n=int(input())
rotti=[[]*1 for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  rotti[a-1].append(b)
  rotti[b-1].append(a)
if len(rotti[0])==1:
  print(1)
  exit()
iti=0
amount=[[1,0]*1 for i in range(n)]
stack=[]
irane=set()
ans=[]
for i in range(1,n):
  if len(rotti[i])==1:
    stack.append(i+1)
    irane.add(i+1)
while len(stack)>iti:
  hako=stack[iti]
  if hako==1:
    iti+=1
    continue
  for i in range(len(rotti[hako-1])):
    if rotti[hako-1][i] in irane:
      continue
    if rotti[hako-1][i]==1:
      ans.append(amount[hako-1][0])
      continue
    amount[rotti[hako-1][i]-1][0]+=amount[hako-1][0]
    amount[rotti[hako-1][i]-1][1]+=1
    if amount[rotti[hako-1][i]-1][1]==len(rotti[rotti[hako-1][i]-1])-1 and rotti[hako-1][i]!=1:
      stack.append(rotti[hako-1][i])
      irane.add(rotti[hako-1][i])
  iti+=1
ans=sorted(ans)
print(sum(ans)-ans[len(ans)-1]+1)

E問題　Takahashi Quest

先に入力をすべて受けとり、ポーションとモンスターで分けてそれぞれのタイプごとにいつ発生するかを配列などにまとめておきます。

一度に持つ量の最大値を最小化するのが目標なので、できるだけ一つのポーションをもっている時間を短くしたいです。ですから、タイプXのモンスターが発生する時、それよりも前の中で一番最近でポーションを入手できるときに入手するようにします。

このような貪欲で解くことができます。

import bisect
n=int(input())
potion=[[]*1 for i in range(n)]
monster=[[]*1 for i in range(n)]
hako2=[]
for i in range(n):
  a,b=map(int,input().split())
  if a==1:
    potion[b-1].append(i)
    hako2.append(i+1)
  else:
    monster[b-1].append(i)
check=0
ans=[]
for i in range(n):
  if len(monster[i])==0:
    continue
  if len(monster[i])>len(potion[i]):
    check=1
    break
  a=len(monster[i])-1
  hako=len(potion[i])
  for ipp in range(len(potion[i])):
    if potion[i][hako-ipp-1]<monster[i][a]:
      ans.append([potion[i][hako-ipp-1],1])
      ans.append([monster[i][a],2])
      a-=1
      if a==-1:
        break
  if a>=0:
    check=1
    break
if check==1:
  print(-1)
  exit()
ans=sorted(ans)
count=0
rotti=0
for i in range(len(ans)):
  if ans[i][1]==1:
    count+=1
    rotti=max(rotti,count)
  else:
    count-=1
print(rotti)
rotti=set()
for i in range(len(ans)):
  if ans[i][1]==1:
    rotti.add(ans[i][0]+1)
ans=[]
for i in range(len(hako2)):
  if hako2[i] in rotti:
    ans.append(1)
  else:
    ans.append(0)
print(*ans)

ちなみに二分探索を使いました。

2024-01-28

ABC332 A~D問題

ABC332

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;
}

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;
}

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

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)