第3回アルゴリズム実技検定(PAST)を受験しました
第3回アルゴリズム検定(PAST)を受験しました。
結果は46点だったので、初級の認定でした。
初級認定はさておき、もうちょっと得点したかったな、という感触です。
解き直しはまだですが、当時のお気持ちなどを書いて復習記事とします。
A - ケース・センシティブ
文字列s,tが与えられるので、それが大文字小文字(case)を含めて一致するか、
大文字小文字の違いは無視して一致するか、全く違う文字列かを判定する問題です。
手順を間違えないように比較してあげればOKです。
s = input() t = input() if (s == t) : print("same") elif(s.lower() == t.lower()) : print("case-insensitive") else : print("different")
B - ダイナミック・スコアリング
N人でM個の問題を解くとして、各人が獲得したスコアが動的に変化する問題です。
どのようはタイミングでスコアを獲得するか、またスコアを表示するかは
Q個のクエリで指示されます。
ユーザ1～Nが解答した問題のリストと、
各問題の現在のスコアを保持するようにしました。
今回は解いてなければスコアとして計上しないので、
ユーザ0～N, 問題0～Mとして配列を作成しました。(それぞれ0番がムダになっている)
N,M,Q = map(int,input().split()) scores = [N] * (M+1) scores[0] = 0 # ユーザNは[]の問題を解いた solved_by_user = [] for i in range(N+1) : solved_by_user.append([]) queryes = [] for i in range(Q) : queryes.append(input().split()) for q in queryes : # q = input().split() q_type = q[0] user = int(q[1]) if (q_type == "1") : # 現在のスコアを表示 solved_list = solved_by_user[user] score = 0 for solved in solved_list : score += scores[solved] print(score) else : solved = int(q[2]) solved_by_user[user].append(solved) scores[solved] -= 1
変数名がイマイチで混乱しそうです。
queryの複数形はqueryesじゃなくてqueriesです。
また、solvedが違う意味で2回登場しています。
解説PDFのほうがかなりすっきりしているので、改善の余地ありです。
C - 等比数列
A,R,Nが与えられるので、初項A、公比Rの等比数列の第N項が
109より大きければ"large",そうでなければその値を表示する問題です。
ペナルティはありませんが、2回誤答となりました。
1回目の提出コード
def main() : A,R,N = map(int,input().split()) for i in range(N-1) : if (1000000000 <= A) : print("large") return A = A*R print(A) main()
愚直な実装ですが、"large"とする判定条件が間違っています。
109より大きい、という判定が正しいので、<=としてはNGです。
このコードはWAが1件で、TLEが1件でした。
そもそも等比数列の一般項はA * RN-1 で求められますから、
そういう感じに書き換えることにしました。愚かですよね。
def main() : A,R,N = map(int,input().split()) v = A * pow(R,N-1) if (1000000000 < v) : print("large") else : print(v) main()
このコードではWAはなくなりましたが、TLEとなりました。
今気づきましたが、TLEが10件に増えていました。そうなんだ……
30分ぐらいgoogleを彷徨って、「繰り返し2乗法」というものがあるらしいのでそれを採用することにしました。
Python で繰り返し2乗法を書いてみた｜keyem｜note
この記事に書かれていましたが、pythonのpowにはすでに実装されているようです。
焦りすぎてまったく読んでいませんでした。
てっきり数字が大きくなるとそれでパフォーマンス劣化が起きてるのかと思い込んでいたのですが、
そうではなかったようです。
手元のコードでA,R,Nに109を渡すととても遅かったので、
べき乗の計算途中に109を超えた場合打ち切るようにしました。
def pow2(x, n): ans = 1 # n が 0 になるまで計算を続ける while n: if n % 2: ans *= x if (1000000000 < ans) : return -1 x *= x n >>= 1 return ans def main() : A,R,N = map(int,input().split()) v = pow2(R,N-1) if (v == -1) : print("large") return v = A * v if (1000000000 < v) : print("large") else : print(v) main()
ひとまず勝てばよかろうということで、これにてACです。
考察の甘さが出てしまいました。
D - 電光掲示板
特定の点灯パターンが与えられるので、
それが一体何の数字なんだというアレです。
OCRじゃないですが、なんかそういうノリのやつです。
汚いコードになるのはさておき、コンテスト中は筋肉で解決です。
# def is_blank_col(j) : # if ((j-1) % 4 == 0) : # return True # return False def get_number(j,l1,l2,l3,l4,l5) : if (l1[j+1] == "." and l2[j+1] == "#" and l3[j+1] == "." and l4[j+1] == "." and l5[j+1] == "#" ) : return 1 if (l1[j+1] == "#" and l2[j+1] == "." and l3[j+1] == "#" and l4[j+1] == "#" and l5[j+1] == "#" ) : return 2 if (l1[j+1] == "#" and l2[j+1] == "." and l3[j+1] == "#" and l4[j+1] == "." and l5[j+1] == "#" ) : return 3 if (l1[j+1] == "#" and l2[j+1] == "#" and l3[j+1] == "#" and l4[j+1] == "." and l5[j+1] == "." ) : return 4 if (l1[j+1] == "#" and l2[j+1] == "#" and l3[j+1] == "#" and l4[j+1] == "." and l5[j+1] == "#" ) : if (l1[j+3] == "#" and l2[j+3] == "." and l3[j+3] == "#" and l4[j+3] == "#" and l5[j+3] == "#" ) : return 5 else : return 9 if (l1[j+1] == "#" and l2[j+1] == "." and l3[j+1] == "." and l4[j+1] == "." and l5[j+1] == "." ) : return 7 if (l1[j+1] == "#" and l2[j+1] == "#" and l3[j+1] == "#" and l4[j+1] == "#" and l5[j+1] == "#" ) : if (l1[j+2] == "#" and l2[j+2] == "." and l3[j+2] == "." and l4[j+2] == "." and l5[j+2] == "#" ) : return 0 elif (l1[j+3] == "#" and l2[j+3] == "." and l3[j+3] == "#" and l4[j+3] == "#" and l5[j+3] == "#" ) : return 6 else : return 8 def main() : N = int(input()) l1 = input() l2 = input() l3 = input() l4 = input() l5 = input() out = "" # for j in range(len(l1)) : for i in range(N) : j = 4 * i # print(j, get_number(j,l1,l2,l3,l4,l5)) out += str(get_number(j,l1,l2,l3,l4,l5)) print(out) main()
ヴォエ！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
サンプルのパターン文字列をテキストエディタでタブ区切りにして、
Excelに貼り付けて条件付き書式で判定条件をチェックしました。
1,2,3,4,7は左1列だけチェックすれば判定可能です。
5,9は右1列も追加でチェックしました。
0は左2列、6,8は全チェックです。
E - スプリンクラー
頂点に色のついた無向グラフとクエリが与えられます。
クエリによって行う操作は2種類で、「隣接する頂点の色を変える」「自分の色を変える」です。
頂点数とクエリ数は200以下なので、だいたい何してもよさそうです。
「この頂点にはどの頂点がつながっているか」を保持しておけばOKです。
辺の情報を受け取ったら、そのまま保持+裏返して保持、とすると頂点ごとのリストで管理できるので楽です。
def main() : N,M,Q = map(int,input().split()) connecting = [] for i in range(N) : connecting.append(set()) for i in range(M) : u,v = map(int,input().split()) connecting[u-1].add(v-1) connecting[v-1].add(u-1) # print(connecting) current_colors = [int(i) for i in input().split()] queries = [] for i in range(Q) : queries.append(input().split()) for q in queries : q_type = q[0] node = int(q[1])-1 print(current_colors[node]) if (q_type == "1") : # 隣接ノードを自分の色にする li = list(connecting[node]) for l in li : current_colors[l] = current_colors[node] else : # 自分の色を変更する color = int(q[2]) current_colors[node] = color main()
こっちはちゃんとqueriesになってます。
F - 回文行列
N文字 * N行の文字列が与えられるので、
各行から1文字ピックアップしてN文字の回文が作れるかどうかを判定する問題です。
Nが偶数か奇数かで実装を分けました。
Nが奇数のときは真ん中の文字は何でも良いです。
真ん中から1つ外側の文字(インデックスが減る方と増える方)は回文として成り立つかどうかを調べるために、
同一の文字を含んでいるかどうかを確かめます。
Nが偶数のときは奇数のときの「真ん中はなんでもいい」がないケースですね。
外側を1つずつ調べていって、最後まで破綻が見つからなければ回文として成立します。
同一の文字を含んでいるかどうかは
各行の文字をsetに入れて
集合演算(交差)することにしました。
def main() : N = int(input()) strings = [] for i in range(N) : l = list(input()) strings.append(set(l)) if (N == 1) : print(list(strings[0])[0]) return s = strings[0].intersection(strings[1]) if (N % 2 == 1) : center_index = (N-1) // 2 # 真ん中は何でも良いので、適当に設定する out_str = list(strings[center_index])[0] for i in range(1,center_index+1) : s =strings[center_index-1].intersection(strings[center_index+1]) if (len(s) == 0) : print(-1) return o = list(s)[0] out_str = o + out_str + o print(out_str) else : out_str = "" for i in range((N//2)-1,-1,-1) : s = strings[i].intersection(strings[N-i-1]) # print(i,N-i-1) if (len(s) == 0) : print(-1) return o = list(s)[0] out_str = o + out_str + o print(out_str) main()
このコードを提出する前にループの条件を間違えて盛大にWAとREを叩き出してしまいました。
仕事が終わってから手をつけたので、ちょっと疲れてたのかもしれません。
テストコードが生きたまま提出されてるのでこれもよくないですね。
ということでここまでで46点、だいたい2時間かかりました。
あとはACできませんでした。
G - グリッド金移動
ゴール座標と障害物の座標が与えられるので、
スタート地点(0,0)からゴールまで到達するのに何手かかるかを求める問題です。
BFSで解くのがよさそうです。
盤面全体を+200して考えてみましたが、WAが出て滅亡しました。
BFSは書いたことがなかったこともあって、どうにもできませんでした。
緑を狙うならこういうのは解けないとダメだよなあという気持ちになりました。
H - ハードル走
DPの典型っぽい雰囲気です。
DPは全然できないとわかっていたので、やりませんでした。
そろそろDPからも逃げないようにしたいですね。
I - 行列操作
こんなんnumpyでいい感じになんとかなるだろと思ったら
numpy使ったことなかったのでえらい時間がかかった上に列交換がうまくいきませんでした。。
import numpy as np def main() : N = int(input()) temp_arr = [] for i in range(1,N+1) : temp = [] for j in range(1,N+1) : temp.append(N * (i-1) + j-1) temp_arr.append(temp) # print(temp_arr) arr = np.array(temp_arr) # print(arr) col_swap_list = [int(i) for i in range(N)] row_swap_list = [int(i) for i in range(N)] Q = int(input()) for i in range(Q) : query = input().split() q_type = query[0] if (q_type == "1") : # A,Bの行交換 q_a = int(query[1])-1 q_b = int(query[2])-1 tmp1 = arr[q_a][:].copy() tmp2 = arr[q_b][:].copy() arr[q_a][:] = tmp2 arr[q_b][:] = tmp1 # print(arr) elif (q_type == "2") : # 列交換 q_a = int(query[1])-1 q_b = int(query[2])-1 col_swap_list[q_a],col_swap_list[q_b] = col_swap_list[q_b],col_swap_list[q_a] arr = arr[:,col_swap_list].copy() print(col_swap_list) # tmp1 = arr[:][q_a-1].copy() # tmp2 = arr[:][q_b-1].copy() # print(arr[:][q_a-1],arr[:][q_b-1], arr[q_a-1][:], arr[q_b-1][:]) # arr[:][q_a-1] = tmp2 # arr[:][q_b-1] = tmp1 # は？ print(arr) main()
解説みるとなんとかなりそうですが、
改めて問題文観るとなんともならなさそうなので
精進が足らんなあという感じです。
存在を知ってるライブラリもちょっとは触っておかないとダメだね、というところも痛感しています。
J - 回転寿司
なんとなく見たことありそうで、なんとなく解けそうな問題でしたが
とっかかりが見つけられず断念となりました。
K - コンテナの移動
これもなんとなくなんとかできちゃったりしそうな雰囲気だけは感じましたが
なんやかんやで手を付けずタイムアップとなりました。
L - スーパーマーケット
終盤わちゃわちゃして実は読み飛ばしていました。なにしてんねん。
解ける自信はないです。
M - 行商計画問題
終盤わちゃわちゃしてあんまりちゃんと読んでませんでした。
最近ダイクストラ法をYouTubeで見たので、ワンチャンあったかもしれん。ワンチャンな。
N - 入れ替えと並び替え
なんか見たことありそうなやつで、かつTLEで爆死したことあるやつ～って思ってました。
リストをスライスしてソートしてまたガッチャンコするみたいな操作はだいたい重くてつらいので破滅しました。
O - 輪投げ
Nに注力しようと思ってやめました。
結果
前述の通り、結果は46点だったので、初級の認定でした。
5時間長すぎて死ぬんじゃないかって思ったんですが
意外と最後まで楽しめました。
これはなんかいけそうなやつ～～みたいなのは
なんとなく掴めてる感じがしないでもないので
実装力と考察力を磨いて行きたいですね。
いまダニングクルーガー効果のイキリ山を登ってるなという気持ちです。
