第二回 アルゴリズム実技検定(PAST) 感想
第二回 アルゴリズム実技検定(PAST) をバーチャル参加で解きました。267分(+7ペナ)でなんとか全部解けました。
感想をTwitterに流そうかと思ったのですが量が多いのとまだ解いてない人のネタバレになってしまうのが怖いのでブログに書きます。
A - エレベーター
B→-1をかける
F→1を引く
みたいにパースしました
B - 多数決
a,b,cという変数を用意して出現回数を数えました
C - 山崩し
AOJ-ICPCにありそう
D - パターンマッチ
正規表現でかっこよく書きたい
E - 順列
言われたとおりにシミュレーションする
F - タスクの消化
その日に実行できるタスクの中で一番ポイントが大きいものを貪欲に選ぶ
priority_queueを使いました
G - ストリング・クエリ
言われたとおりに文字列Sを持つと大変なので {文字、個数} をdequeに入れた
H - 1-9 Grid
いつものダイクストラ
安心感が凄かった
I - トーナメント
N回戦までで終わるからシミュレーションして間に合う
J - 文字列解析
一番やらかしたし一番時間溶かした
パッと見区間dpにしか見えなくて
dp0[l][r]=[l,r)が正しい括弧列になるときの最小コスト
dp1[l][r]=[l,r)で'('が1個余るときの～
dp2[l][r]=[l,r)で')'が1個余るときの～
dp3[l][r]=[l,r)で')('が余るときの～
をやろうとしたら実装が重すぎて1時間溶かしたあともっと簡単なやり方に気づいた(これでもできるよね？)
M - 食堂
やることが分かっても実装がかなり辛いやつ
こういう問題練習すれば強くなるんだろうな～とは思うけどコンテスト以外で解くのはしんどい…
N - ビルの建設
これABCに出してほしい
クエリソートすると一次元セグ木でOK
O - 可変全域木
これも好き(でも既出なのかな)
とりあえず適当に最小全域木を作った後で辺(u,v)を使うことを考える。
u-vパスと辺(u,v)でループができるから、u-vパスの中で一番重みが大きい辺と辺(u,v)をswapすればいい
パスの中で一番重みが大きい辺を探すのはHL分解＋セグ木でできる(この問題HL分解のverifyに使えそう)
感想をTwitterに流そうかと思ったのですが量が多いのとまだ解いてない人のネタバレになってしまうのが怖いのでブログに書きます。
A - エレベーター
B→-1をかける
F→1を引く
みたいにパースしました
B - 多数決
a,b,cという変数を用意して出現回数を数えました
C - 山崩し
AOJ-ICPCにありそう
D - パターンマッチ
正規表現でかっこよく書きたい
E - 順列
言われたとおりにシミュレーションする
F - タスクの消化
その日に実行できるタスクの中で一番ポイントが大きいものを貪欲に選ぶ
priority_queueを使いました
G - ストリング・クエリ
言われたとおりに文字列Sを持つと大変なので {文字、個数} をdequeに入れた
H - 1-9 Grid
いつものダイクストラ
安心感が凄かった
I - トーナメント
N回戦までで終わるからシミュレーションして間に合う
J - 文字列解析
一番やらかしたし一番時間溶かした
パッと見区間dpにしか見えなくて
dp0[l][r]=[l,r)が正しい括弧列になるときの最小コスト
dp1[l][r]=[l,r)で'('が1個余るときの～
dp2[l][r]=[l,r)で')'が1個余るときの～
dp3[l][r]=[l,r)で')('が余るときの～
をやろうとしたら実装が重すぎて1時間溶かしたあともっと簡単なやり方に気づいた(これでもできるよね？)
M - 食堂
やることが分かっても実装がかなり辛いやつ
こういう問題練習すれば強くなるんだろうな～とは思うけどコンテスト以外で解くのはしんどい…
N - ビルの建設
これABCに出してほしい
クエリソートすると一次元セグ木でOK
O - 可変全域木
これも好き(でも既出なのかな)
とりあえず適当に最小全域木を作った後で辺(u,v)を使うことを考える。
u-vパスと辺(u,v)でループができるから、u-vパスの中で一番重みが大きい辺と辺(u,v)をswapすればいい
パスの中で一番重みが大きい辺を探すのはHL分解＋セグ木でできる(この問題HL分解のverifyに使えそう)
