初めに
AtCoderに参加した記録を残します。どのような考察をしながら問題に取り組んだかを記録していますので、必ずしも教育的なコードとは限りません。
始めたばかりの人など、どなたかの助けになれば嬉しいです。
コメントなどいただけると嬉しいです！！
成績
ABC297 2冠...。
着想がすごく悪かった...。
目次
A - Job Interview
B - Coloring Matrix
C - Cards Query Problem
A - Job Interview
問題ページ
該当文字をカウントして条件に当てはまるかを判定する問題。
条件１：「良」と評価した面接官が少なくとも１人はいる
条件２：「不可」と評価した面接官がいない
コンテスト中の考察
今回は本当に着想が悪かったので、最初は2進数に変換してbit演算しようとしていた。
もちろんそんなことをする必要はなくて、'o'と'x'の個数を数えて、'o'>0 and 'x' == 0であるかを判定するだけで良い。
コンテスト中のコード
N = int(input())
S = input()
if S.count('o') > 0 and S.count('x') == 0:
print('Yes')
else:
print('No')
改善点
着想面
特になし。
コード面
特になし。
B - Coloring Matrix
問題ページ
行列Aを回転することで条件を満たすようになるかを判定する問題。
条件：A_i_j＝１ ならば B_i_j＝１である
コンテスト中の考察
ここでもかなり着想が悪かった。
回転させる操作が時間かかりそうだと直感的に判断し、回転軌道上の各周の文字を一行に展開し、Bとマッチングするか先頭から見ていくという方法を考えた。この方法だと、まず各周の文字を一行の文字列に直すのがめんどくさい。さらに、もし仮に直しても各周ごとに先頭からマッチングしていくか見る必要があるため、ざっとO(N^5)くらいかかりそうなのでかなり筋が悪い。
そんなめんどくさいことをする必要はなく、回転はせいぜい4種類しかないので、愚直に回転させ、先頭から照合していくことで判定可能である。回転にO(N^2), 照合にO(N^2)かかるので、全体でO(N^2)かかることになるが、制約を考慮すると十分高速である。
A, Bの他に、回転のためにCを用意している。Cを用意することで、代入ミス（参照しているのが回転前の値なのか、回転後の値なのかの管理ミス）を防いでいる。
コンテスト中のコード
def f(N, A, B):
for i in range(N):
for j in range(N):
if A[i][j] == 1:
if B[i][j] == 0:
return False
return True
N = int(input())
A = [[] for _ in range(N)]
B = [[] for _ in range(N)]
C = [[0]*N for _ in range(N)]
for i in range(N):
A[i] = list(map(int, input().split()))
for i in range(N):
B[i] = list(map(int, input().split()))
for k in range(4):
if k % 2 == 0:
for i in range(N):
for j in range(N):
C[i][j] = A[N-1-j][i]
if f(N, C, B):
print('Yes')
exit()
else:
for i in range(N):
for j in range(N):
A[i][j] = C[N-1-j][i]
if f(N, A, B):
print('Yes')
exit()
print('No')
改善点
着想面
特になし。
コード面
回転はもっと効率的にできたらしい。（回転の部分のみ）
正直あんまり理解できてない...
# 入力部分（割愛）
# 回転の関数定義
def rotate(C):
return [list(r) for r in zip(*C)][::-1]
# チェック -> 回転を4セット（割愛）
C - Cards Query Problem
問題ページ
順番にクエリを処理していく問題。
クエリ１：箱jにカードiを入れる
クエリ２：箱iに入っているカードを昇順に出力
クエリ３：カードiが入っている箱の番号を昇順に出力
コンテスト中の考察
パッと見た直感でheapqueueを思いついてしまった。今回本当に最初の着想がとても悪い。
コンテスト中は
方法1. 出力時にsortしてもO(NlogN)かかって、クエリの個数を考えるとO(N^2logN)になる。
方法2. heapqに入れてO(logN)、出力時に中身を全部取り出してO(N)再度入れ直すO(NlogN)になる。
と考え、最初に思い浮かんだheapqueueでの実装を行いTLE。
改善点
着想面
方法1ではなく方法2を採用していればTLEにならずにACしていたらしい。
なぜ方法2ではTLEせず、方法1ではTLEしてしまうのかについてだが、直感的には方法1では、挿入時に毎回順序を考慮している(O(logN)かかっている) が、方法2では、クエリ2, 3の時のみソート(O(NlogN))しているためである。別の言い方をすれば、実際にソートすべきであるのはクエリ2, 3のときに与えられるi番目の要素に対してのみであるのに対し、方法1では本来ソートしなくても良いはずの、入力される全要素に対して順番に並べるという操作をしてしまっているのである。大雑把な計算量見積では同じに見えるが、実際には
ケース1. クエリ1(データの挿入)が少なく、クエリ２、3が多い場合
ケース2. クエリ1(データの挿入)が多く、クエリ２、3が少ない場合
の二つが考えられ、クエリ1が少ない場合はそもそもソートすべきデータの数が少なく、クエリ1が多い場合にはソートする回数が少なくなるのである。
コード面
カードが入っている箱の昇順出力は重複を許さないために集合で管理している。
N = int(input())
Q = int(input())
B = [[] for _ in range(N+1)]
C = [set() for _ in range(2*10**5+1)]
for _ in range(Q):
q = list(map(int, input().split()))
if q[0] == 1:
i, j = q[1], q[2]
B[j].append(i)
C[i].add(j)
elif q[0] == 2:
i = q[1]
B[i].sort()
print(*B[i])
else:
i = q[1]
print(*sorted(list(C[i])))
終わりに
今回時間がなくて少し雑になってしまい申し訳ないです！
書き始めたばかりで拙い部分も多いですが、みなさんと楽しく盛り上がれたらいいなと思っていますので、今後ともよろしくお願いいたします！