アルゴリズム実技検定(PAST)が今回に限り無料で受検できるということで、挑戦してみました。
今回はできるだけ時系列に沿って、自分が何を考えていたかを記録に残す感じで。なんとなく。
開始前
Highest水色で現緑コーダーである自分の場合、実力通りなら多分中級で、ワンチャン上級もありだが失敗すると初級もありえそうという微妙な立ち位置。
さすがに初級だとしゃれにならんので、まずはとにかく中級ボーダーである9問を目標と考えていた。
検定開始
開始時刻は21:31。
A - ケース・センシティブ
まず、s, t をそのまま比較して一致したら"same"、次にそれぞれを大文字で揃えて一致したら"case-insensitive"、一致しなければ"different"。
それはいいとして、std::transformやstd::toupperの存在を知らず、一文字ずつcharを演算で変換していったので、面倒くさいなあと思っていた。もうちょっとSTL把握しておかないとなぁ。あるいはこういう問題のときはRubyかなんかでちゃっちゃと解いてしまうという手もあるが、それだとより高難度の問題の一部分にこういう処理が含まれていた場合に困ることになるので、知識として持っているか否かで、結局どこかで差はついてしまう。
21:35:39 AC。残り4:55。
B - ダイナミック・スコアリング
クエリ2で誰がどの問題を解いたか、どの問題が何人に解かれたかを記録しておき、クエリ1でその情報を元に得点を逐次計算すればよい。クエリの数が少ないので余裕で間に合う。
21:42:24 AC。残り4:48。
C - 等比数列
オーバーフローしそうだなと思いつつ、ペナっても大勢に影響はないのでいいやと思ってA * R ^(N - 1)で計算して投げたらやっぱりWA。
オーバーフローに気をつけてRを1つずつ掛けて都度チェックする、で通った。自分は場合分けを一切気にせずやったのだけど、よく考えたらこれC++の暴力で、制約がきつくなると通らない解法。
普段のコンテストだと、こういうのでパフォを数百落としたりもするので、よくない。
21:49:35 AC。残り4:41。
D - 電光掲示板
情報公開後、割と話題になっていた問題。自分はif文列挙で通した。
if (s[0][1 + i * 4] == '.') cout << 1; else if (s[0][2 + i * 4] == '.') cout << 4; else if (s[4][1 + i * 4] == '.') cout << 7; else if (s[1][1 + i * 4] == '#' and s[1][3 + i * 4] == '#') { if (s[2][2 + i * 4] == '.') cout << 0; else if (s[3][1 + i * 4] == '.') cout << 9; else cout << 8; } else if (s[1][1 + i * 4] == '.') { if (s[3][1 + i * 4] == '.') cout << 3; else cout << 2; } else { if (s[3][1 + i * 4] == '.') cout << 5; else cout << 6; }
しかし、これは埋め込みでやるのが定石とのこと。
PASTのDは入力例1をそのままソースコードに貼り付けるのが本質で、それをやってない人は多分面倒って評価になってると思います。
— chokudai(高橋 直大)🌸🍆 (@chokudai) 2020年6月6日
（それさえやれば実装は軽いです）
確かに、[0-9]の範囲だとif文列挙しても対して手間じゃないのだが、これが英大文字小文字とかも含む、とかになるとそれだけで数十個になるから現実的じゃなくなる。
また一つ利口になった。
22:01:56 AC。残り4:29。
E - スプリンクラー
隣接リストでグラフを表現することができれば、クエリで処理すべきことは単純で、N, Q ともに大きくないので言われたことを素直に実装するだけ。
この問題から競プロの経験のありなしが大きく影響する、かもしれない。
22:07:15 AC。残り4:23。
F - 回文行列
i行目とN+1-i行目に同じ文字が含まれていればいい。これもNが大きくないので特に工夫することなく愚直にチェックして間に合う。
22:14:01 AC。残り4:16。
1時間経たずに6問クリア。ここまでは順調であった、が・・・。
空白の？1時間
G問題、えーなんか面倒くさそう・・・。とりあえずパス。
H問題、えーなんか面倒くさそう・・・。とりあえずパス。
I問題、えー全然分からん・・・。とりあえずパス。
J問題、priority_queueでいけるか？と思い実装するも、サンプルすら合わない・・・。とりあえずパス。
K問題、列を切ったり貼ったりする問題。こんなんlistにぶち込めばいけるやろ、と実装してみるが、TLE。よく考えたらlistだと列を切る位置を探すのに線形時間かかってしまうのでだめだった。とりあえずパス。
焦る。焦りまくる。まだ6問しか解けてない。ここで飲み物がなくなったので台所に補充に行ったところで、神の声が降りてくる。
妻「冷凍庫にアイスあるで」
問題を眺めながらアイスを食べる。糖分補給が効いたのどうかは実際わからないが、Gの解法に気づく。
G - グリッド金移動
G - Gold General Goes on the Grid
よくよく考えてみたら、ただのBFSで解ける問題であった・・・。座標が負の方向にも伸びているので、実装上は適当に平行移動させることと、障害物の範囲が-200から200であることから、回り込むことも考えて取るべき座標の範囲は-201から201まで必要なことに注意しつつ実装。（自分は面倒臭がって500*500でとった）
23:33:27 AC。残り2:57。
FからGの間が1時間以上空いてしまった。
H - ハードル走
アイスの残りを食べながら問題を眺める。
はい、ただのDPでした。
ハードルに引っかかる部分の解釈に結構手こずって、サンプルが合わないをしていたが、単純な1次元DPをいわゆる貰うDPで実装。ジャンプ中にゴールするケースを最後に加えて（サンプルが優しい）完了。
23:57:20 AC。残り2:33。
Iはやっぱりわからないので、飛ばす。
J - 回転寿司
落ち着いて考え直すと、先頭から優先で美味しい寿司を食べるのだから、子供が食べた寿司の美味しさは広義単調減少になることに気づく。なので、寿司を食べる子供は二分探索で見つけることができる。
00:06:25 AC。残り2:24。
糖分補給のおかげかどうかはわからないが、ペースが上がってきた。そしてここで9問クリアで中級確定。ほっと一息。
Kは線形時間かかる部分をどう解消すればいいのかばかり考えていて、先に進まず。ひとまず次の問題へ。
L - スーパーマーケット
最初、priority_queueを2つ、一番手前と手前から二番目のために用意して実装しようとした。しかしpriority_queueだと任意の要素を取れないため、一番手前から取った時に二番目から一番目に移る部分を実装できない。
setで作り直すとよさそうで、実装がえらく重くなってしまったし、すべての棚に商品が1個以下になった時を考慮できておらず（2つめのsetが空になる）一度REを出したが、なんとか通す。
00:43:18 AC。残り1:47。
結局通せたのはここまでだった。
K - コンテナの移動
残った問題で一番ACに近そうなのはこれかなと思ってしばらく粘着するが、前述の通りlistに固執してしまったためどうにもならず。
自分でポインタを管理すればいいのでは、ということに気づいたのは、寝床に入ってからであった・・・。残念。
I - 行列操作
終了30分ほど前に、各行と列がどこに移動したかの情報だけを持っておけば良いことに気づく。3のクエリは、偶数回おこなうと元に戻るのでboolで持っておけばよさそう。
しかし、3のクエリで転置した状態で他のクエリが来た時にどうなるのかを詰めきれず。ここで時間切れとなった。
結果
というわけで10問ACで70点、中級という結果に終わった。まあ実力通りで可もなく不可もなくというところ。
感想
純粋に楽しかったですし、改めて得たものもいくつかありました。糖分補給が重要であることも身をもって知れました。（プラシーボかも知れないけど）
もうちょっと精進すれば上級もありそうなので、もし次に受検する機会があれば、上級を目標にしたいです。機会があれば・・・。（会社で団体受検とかできるよう努力する、か・・・。）
