Atcoder ABC218, 217 振り返り
順序付き集合の問題に当たりました.C++にはあるけどPythonには無い機能でどうするか色々あるデータ構造のようです.今回はとある記事様https://qiita.com/tatyam/items/492c70ac4c955c055602のコードを使わせて頂きました.こういうときにすぐ対応出来るように(あと今Pythonしか書けないし)C++書けるように勉強した方が良さそうです.(時間が無い)
A - Weather Forecast【AC】
言われたとおりやります.
N = int(input()) S = input() print("Yes" if S[N-1]=="o" else "No")
B - qwerty【AC】
chr(96) = aで+1されるごとにb,c...となるのでこれを利用します.
p = [int(i) for i in input().split()] print("".join([chr(96+i) for i in p]))
C - Shapes【AC】
#を平行移動させることが許されているのが厄介です.そのため,#の集団を平行移動出来ないようにグリッドを狭めてやれば良いです.全てが.の行や列があったら,#の集団が上下左右に移動できることになります.よって全て.の行と列を数え,その分はスライスしてグリットを小さくすることで,平行移動出来ないようにします.なお,#は非連結も許されているので,真ん中で.の行や列があってもそれは省略できないことに注意します.
グリッドを狭めたndarrayは,もう平行移動できないので,あとは回転のみになります.ndarrayはrot90(arr, k)で90*k度回転させることが出来ます.
import numpy as np N = int(input()) S = [] T = [] for _ in range(N): S.append(list(input())) for _ in range(N): T.append(list(input())) S = np.array(S) T = np.array(T) def check(f, b, t): for i in range(N): if not np.all(t[i] == "."): f = i break for i in range(N-1, -1, -1): if not np.all(t[i] == "."): b = i break return f, b S_forward_cut = 0 S_back_cut = N S_forward_cut, S_back_cut = check(S_forward_cut, S_back_cut, S) T_forward_cut = 0 T_back_cut = N T_forward_cut, T_back_cut = check(T_forward_cut, T_back_cut, T) ST = S.T S_left_cut = N S_right_cut = 0 S_right_cut, S_left_cut = check(S_right_cut, S_left_cut, ST) TT = T.T T_left_cut = N T_right_cut = 0 T_right_cut, T_left_cut = check(T_right_cut, T_left_cut, TT) S = S[S_forward_cut:S_back_cut+1, S_right_cut:S_left_cut+1] T = T[T_forward_cut:T_back_cut+1, T_right_cut:T_left_cut+1] for i in range(4): new_T = np.rot90(T, i) if S.shape == new_T.shape: if np.all(S == new_T): print("Yes") break else: print("No")
D - Rectangles【AC】
2点決めたら,長方形が一意に定まることを利用します.2点を全探索し,残りの2点が存在するか二分探索で調べれば良いです.
import bisect points = set() N = int(input()) for _ in range(N): x, y = map(int, input().split()) points.add((x, y)) ans = 0 points_list = list(points) for i in range(N-1): for j in range(i+1, N): x1, y1 = points_list[i] x2, y2 = points_list[j] if x1 == x2 or y1 == y2: continue if (x1, y2) in points and (x2, y1) in points: ans += 1 print(ans//2)
A - Lexicographic Order【AC】
sorted(list)はソートされたlistが返ってくるのに対し,list.sort()はlistはソートされますが,返ってくるのはNoneであることに注意します.
a = [i for i in input().split()] if a == sorted(a): print("Yes") else: print("No")
B - AtCoder Quiz【AC】
setは差集合を取ることが出来ます(初めてこの機能を利用しました).残る文字が一つしか無いのでpopして表示させます.
contest = {"ABC", "ARC", "AGC", "AHC"} s = set() for _ in range(3): s.add(input()) print((contest - s).pop())
C - Inverse of Permutation【AC】
join()はリストの要素がstrでないと動かない仕様があるので,Qに設定するときにstrにするようにしています.
N = int(input()) P = [int(i) for i in input().split()] Q = [0 for _ in range(N)] for i in range(N): Q[P[i]-1] = str(i+1) print(" ".join(Q))
D - Cutting Woods【解説AC】
順序付き集合で解く問題です.今回は上述の記事様からのコードを使わせて頂きました.すると簡単に解くことが出来ます.
import math from bisect import bisect_left, bisect_right from typing import Generic, Iterable, Iterator, TypeVar, Union, List T = TypeVar('T') class SortedSet(Generic[T]): 略 L, Q = map(int, input().split()) s = SortedSet([0, L]) for _ in range(Q): c, x = map(int, input().split()) if c == 1: s.add(x) else: print(s.ge(x) - s.lt(x))