ABC341 A~E問題

F問題あともうひと押し…

atcoder.jp

A問題　Print 341

1010.....1みたいに出力すればいいです。

n=int(input())
for i in range(n):
  print("10",end='')
print("1")

B問題　Foreign Exchange

それぞれの国で両替をできるだけ行うという貪欲で解けます。

n=int(input())
a=list(map(int,input().split()))
for i in range(n-1):
  x,y=map(int,input().split())
  a[i+1]+=(a[i]//x)*y
print(a[n-1])

C問題　Takahashi Gets Lost

全探索で通ります。
陸地である地点全てから行動をして、途中で海にはみださなかった時、その最終地点が現在いる地点として考えられるものです。
Pythonだと、下手な書き方をすると間に合わないらしいですね。

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int h,w,n,a,b,ans=0;
  bool check=true;
  cin >> h >> w >> n;
  string s;
  cin >> s;
  vector<vector<char>>rotti(h,vector<char>(w));
  for(int i=0;i<h;i++)for(int ipp=0;ipp<w;ipp++)cin >> rotti[i][ipp];
  for (int i=0;i<h;i++){
    for(int ipp=0;ipp<w;ipp++){
      if(rotti[i][ipp]=='#')continue;
      a=i;
      b=ipp;
      check=true;
      for(int k=0;k<n;k++){
	if(s[k]=='U'){
	  if(a==0 || rotti[a-1][b]=='#')check=false;
	  else a--;
	}
	else if(s[k]=='R'){
	  if(b+1>=w || rotti[a][b+1]=='#')check=false;
	  else b++;
	}
	else if(s[k]=='D'){
	  if(a+1>=h || rotti[a+1][b]=='#')check=false;
	  else a++;
	}
	else if(s[k]=='L'){
	  if(b==0 || rotti[a][b-1]=='#')check=false;
	  else b--;
	}
	if(check==false)break;
      }
      if(check)ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

D問題　Only one of two

Nの約数の個数、Mの約数の個数、NとMの最小公倍数の個数がわかれば、包除原理で求めることができます。
ですから二分探索で通ります。

#include <bits/stdc++.h>
using namespace std;
long long kouyaku(long long a,long long b){
  while(a>0 && b>0){
    if(a<b)b=b%a;
    else if(a==b)return a;
    else a=a%b;
  }
  return max(a,b);
}
long long koubai(long long a,long long b){
  return a*b/kouyaku(a,b);
}
int main()
{
  long long n,m,k;
  cin >> n >> m >> k;
  long long count=koubai(n,m);
  long long left=min(n,m),right=9223372036854775807,mokuteki;
  while(left+1!=right){
    mokuteki=(left+right)/2;
    if((mokuteki/n+mokuteki/m-(mokuteki/count)*2)<k)left=mokuteki;
    else right=mokuteki;
  }
  cout << right << endl;
  return 0;
}

E問題　Alternating String

セグメントツリーや平衡二分木などで、任意の区間に同じ番号が連続している地点があるかどうかを高速で求めることができるようにすればよいです。

#include <bits/stdc++.h>
using namespace std;
class seguki{
public:
  //1index
  vector<int>num;
  int siz=1;
  void init(int n){
    while(siz<n)siz*=2;
    for (int i=0;i<siz*2+1;i++)num.emplace_back(0);
  }
  void update(int a,int b){
    a=siz+a-1;
    num[a]=b;
    a/=2;
    while(a>=1){
      num[a]=num[a*2]+num[a*2+1];
      a/=2;
    }
  }
  void henkou(int a,int b){
    a=siz+a-1;
    num[a]+=b;
    num[a]%=2;
    a/=2;
    while(a>=1){
      num[a]=num[a*2]+num[a*2+1];
      a/=2;
    }
  }
  int sm_num(int l,int r,int a,int b,int u){
    if(r<=a || b<=l)return 0;
    else if(l<=a && b<=r)return num[u];
    int m=(a+b)/2;
    int L=sm_num(l,r,a,m,u*2);
    int R=sm_num(l,r,m,b,u*2+1);
    return L+R;
  }
};
int main()
{
  int n,t,a,l,r,hako;
  cin >> n >> t;
  string s;
  cin >> s;
  seguki rotti;
  rotti.init(n);
  for (int i=0;i<n-1;i++)if(s[i]==s[i+1])rotti.update(i+1,1);
  for(int q=0;q<t;q++){
    cin >> a >> l >> r;
    if(a==1){
      if(l!=1){
	rotti.henkou(l-1,1);
      }
      if(r!=n){
	rotti.henkou(r,1);
      }
    }
    if(a==2){
      hako=rotti.sm_num(l,r,1,rotti.siz+1,1);
      if(hako==0)cout << "Yes" << endl;
      else cout << "No" << endl;
    }
  }
  return 0;
}