第七回 アルゴリズム実技検定(PAST)
いつもお世話になっているAtCoder様にお布施すべく、アルゴリズム実技検定(PAST)を受けてみやした。結果は52点で初級でした。
事前に本番の雰囲気をつかむべく過去問を2回分解いていたのですが、どっちも確か同じような点数で、初級はいけそう、中級は奇跡が起きないと厳しい、という感じでした。解けない問題も全く歯が立たないというわけではなくて、行けそうなのに何ケースかWAが取れないというような問題が多くてよく練られているなあと感じました。
ちなみに試験時間は5時間ですが、そんなに集中力が持つはずもなく、実質2時間ぐらいで気持ち的には試験終了していました。
以下では、解けた問題と考えたけど解けなかった問題について、感想を述べたいと思います。
A - チェックディジット
問題文の通り、順番に処理を記述していきました。
B - 蒸気圧
これも問題文の通り実装した気がします。ただ、最初ボールと風船の両方から1ずつ引いていったせいでバグらせたような。解説見ると、の時は答えCだよって書いてあって、ほげえええってなりました。Whileループ回す必要なかったのか…
C - 入力チェック
ここで初めてWA食らいました。確か、入力が0の時にも先頭が不要な0と判定したことが原因でした。 最終的に、以下のif文で先頭に不要な0があるかを判定しました。
if str(int(S)) != S and int(S) != 0:
D - 書き換え
一瞬、書き換えの順番によって結果が変わりうるのかな？と考えましたが、変わらなそうだったので貪欲に先頭からヒットした文字列を書き換えて行きました。何故か一度入力文字列をlist化して、S[i:i+3] == [“a”,“x”,“a”]みたいな判定式をそれぞれ書いたのですが、何で文字列のreplace()使わなかったんだろう…↓ので良かったな…
S.replace(‘axa’, ’…‘).replace(‘ixi’, ’…‘).replace(‘uxu’ , ’…‘).replace(‘exe’, ’…‘).replace(‘oxo’, ’…‘)
E - 青木君のいたずら
全探索しました。青木くんが選びうる全てのkのパターンに対して最終的なXの値を計算したテーブルを用意し、入力されたNがそのどれかにヒットするかで判定しました。
F - ダブルブッキング
日付ごとにミーティング予定をリスト追加していって、入力された日付に既に予定が格納されている場合はダブルブッキングしていないかを判定しました。判定の際、以前のABCで覚えた、max(start1,start2) < min(end1,end2)の考え方を使いました。
G - べき表現
こっから解けない問題ゾーンに入ります。この問題に関しては手も足も出ませんでした。解説に目を通した今も頭の中にクエスチョンマークが出ています。
H - 折れ線グラフ
いろいろ試したんですがACできませんでした。DPという発想に至らなかった…
I - ほくろ
問題見てすらないどす
J - 終わりなき旅
閉路判定の関数をネットで探してきてコピペしてACしてしまいました。実力ではないのでちょっと捻られると蹂躙されると思います。
K - 急ぎ旅
ダイクストラ使ってゴニョゴニョやったけどACできませんでした。解説見ると、なんか解けててもおかしくないのにな…と頭を捻っています。
まとめ
というわけで、PAST初受験でした。面白かったですし、実力テストとして今後もなるべく受けていきたいと思います。
最近自作キーボードにお熱なので、すぐには解き直しをする気力が湧きませんが、いずれやりたいなあ…
以上です。