AtCoder Beginner Contest 244 A~D 4完記事

アルゴリズムの学習改善のための自身の備忘録及び学習の一環として記事を書くことにしました.
読んでくれた方で何かありましたら気兼ねなくコメントしてください.お待ちしております.
今回のC問題は普段とことなり、ヒューリスティックてきな問題だと感じた．
普段の問題と同じようなものを期待する方は飛ばしてもいいだろうと思う．

A - Last Letter

問題文

英小文字からなる長さ N の文字列 S が与えられます。S の末尾の文字を出力してください。

制約

• N は整数
• 1≤N≤1000
• S は英小文字からなる長さ N の文字列

入力

入力は以下の形式で標準入力から与えられる。
$N$
$S$

考察

$S$の最後の文字を取り出し出力させれば良い．
やるだけ．

サンプルコード

a.py

n=int(input())
s=input()
print(s[-1])

B - Go Straight and Turn Right

問題文

xy 平面を考えます。x 軸の正の向きを東向き、y 軸の正の向きを北向きとします。
高橋君ははじめ、点 (x,y)=(0,0) にいて東（ x 軸の正の向き）を向いています。
S と R のみからなる長さ N の文字列 $T=t_1,t_2,\dots,t_N$が与えられます。
高橋君は$i=1,2,…,N$の順番で下記を行います。

• $t_i$=S ならば、高橋君はいま向いている方向に距離 1 だけ進む。
• $t_i$=R ならば、高橋君はその場で右に 90 度回転する。その結果、高橋君の向いている方向が下記の通りに変わる。
  • 回転前の向きが東向き（ x 軸の正の向き）ならば、回転後の向きは南向き（ y 軸の負の向き）になる。
  • 回転前の向きが南向き（ y 軸の負の向き）ならば、回転後の向きは西向き（ x 軸の負の向き）になる。
  • 回転前の向きが西向き（ x 軸の負の向き）ならば、回転後の向きは北向き（ y 軸の正の向き）になる。
  • 回転前の向きが北向き（ y 軸の正の向き）ならば、回転後の向きは東向き（ x 軸の正の向き）になる。

上記の手順を終えた後に高橋君がいる点の座標を出力してください。

制約

$1\leq N \leq 10^5 $
$N$は整数
$T$ は$ S$と$ R$ のみからなる長さ $N $の文字列

入力

入力は以下の形式で標準入力から与えられる。
$N \ \ M$
$A_1 \ \ A_2 \ \dots \ \ A_N$
$B_1 \ \ B_2 \ \dots \ \ B_M$

考察

今向いている方向が分かればあとは1歩進むだけである．
東を0とし、回転した回数を数える．4の剰余で今向いている方向が一意に定まる．
最初にいる座標を$ans=[0,0]$とし、x軸方向とy軸方向を管理する．
回転した回数の剰余が$0,2$のいずれかの場合x軸方向、$1,3$のいずれかでy方向の移動を行えばよい．
$0,1$で正の方向、$2,3$で負の方向に移動すれば無駄なく答えを求められる．

サンプルコード

b.py

n=int(input())
t=list(input())
cnt=0
ans=[0,0]
for i in t:
    if i=='R':
        cnt+=1
    else:
        if cnt%4==0:
            ans[0]+=1
        elif cnt%4==1:
            ans[1]-=1
        elif cnt%4==2:
            ans[0]-=1
        else:
            ans[1]+=1
print(*ans)

C - Yamanote Line Game

問題文

高橋君と青木君は 2 人で次の対戦ゲームをします。
高橋君が先手でゲームを始め、ゲームが終了するまでの間、 2 人は交互に 1 以上 2N+1 以下の整数を 1 つずつ宣言します。 どちらかが一度でも宣言した整数は、それ以降どちらも二度と宣言することが出来ません。 先に整数を宣言することが出来なくなった方のプレイヤーの負けとなり、負けなかった方のプレイヤーの勝ちとなります。
このゲームでは必ず高橋君が勝ちます。 高橋君の立場で実際にゲームを行い、ゲームに勝ってください。

制約

$1 \leq N \leq 1000$
$N$は整数

入力

この問題はインタラクティブな問題（あなたの作成したプログラムとジャッジプログラムが入出力を介して対話を行う形式の問題）です。
あなたのプログラムが高橋君の立場で、ジャッジプログラムが青木君の立場でゲームを行います。
まず、あなたのプログラムに標準入力から正の整数 N が与えられます。 その後、ゲームが終了するまで下記の手順を繰り返します。

1. あなたのプログラムが、高橋君が宣言する整数として、1 以上 2N+1 以下の整数を標準出力に出力します。（どちらかのプレイヤーによってすでに宣言されている整数を出力することは出来ません。）
2. ジャッジプログラムによって、青木君が宣言する整数があなたのプログラムに標準入力から与えられます。（どちらかのプレイヤーによってすでに宣言されている整数が入力されることはありません。） ただし、青木君が宣言できる整数が残っていない場合は、代わりに 0 が与えられ高橋君の勝ちでゲームが終了します。

考察

1. Nを受け取る
2. 2N+1以下で既出でない数字を出力
3. 値を受け取る

2，3を繰り返し行う．この時既出の数を出力しないように既出の値をsetで管理すると、$O(1)$で有無が判定出来て高速になる．

サンプル

c.py

n=int(input())
ans=set()
for i in range(n+1):
    for j in range(1,2*n+2):
        if j not in ans:
            print(j)
            ans.add(j)
            break
    k=int(input())
    ans.add(k)

D - Swap Hats

問題文

1,2,3 の番号がついた 3 人の高橋くんがおり、赤・緑・青の色がついた 3 種類の帽子がそれぞれ 1 つずつあります。それぞれの高橋くんは帽子を 1 つかぶっており、高橋くん i がはじめにかぶっている帽子の色は文字 $S_i$で表されます。ここで、R は赤、G は緑、B は青に対応しています。これから、以下の操作をちょうど$10^{18}$回行います。
操作

• 3 人の高橋くんのうち 2 人を選ぶ。2 人はお互いのかぶっている帽子を交換する。

$10^{18}$回の操作の後、高橋くん i が文字 $T_i$に対応する色の帽子をかぶっているようにすることはできますか？

制約

$S_1,S_2,S_3$は R, G, B の並べ替えである
$T_1,T_2,T_3$は R, G, B の並べ替えである

入力

入力は以下の形式で標準入力から与えられる。
$S_1,S_2,S_3$
$T_1,T_2,T_3$

考察

置換の回数を考える．
受け取った時点でSとTが一致している場合、同一箇所を$10^{18}$回入れ替えることでSとTが一致する．
どこか、1カ所のみことなることは制約からあり得ないので考えなくて良い．
2カ所ことなる場合を考える．ことなる箇所を適切に入れ替えると1度の操作でSとTが一致する．この後、奇数回操作をする場合、題意を満たすことは必ずない．
最後にすべて位置がことなる場合、必ず2度の入れ替えでSとTが一致する形を作れる．以降$10^{18}-2$回の操作が可能であるので題意を満たせる．
SとTを比較し、$s[i]==t[i]$, $\ i=0,1,2$を満たす個数を数え0または3であれば"Yes"、それ以外は"No"を出力すれば良い．

サンプル

d.py

s=list(map(str,input().split()))
t=list(map(str,input().split()))

cnt=0
if s[0]!=t[0]:
    cnt+=1
if s[1]!=t[1]:
    cnt+=1
if s[2]!=t[2]:
    cnt+=1

if cnt==0 or cnt==3:
    print("Yes")
else:
    print("No")