第三回アルゴリズム実技検定（PAST）参加記録
2020/06/06に第三回アルゴリズム実技検定（PAST）を受験しました。
PASTの紹介と自身の復習を兼ねて、参加記録を書きます。
アルゴリズム実技検定（PAST）とは
世界最大級の競技プログラミングコンテストサイトを運営するAtCoder社による、1からプログラムを作成する能力を問う、実践を想定した日本初の検定です。
https://past.atcoder.jp/feature
詳しい説明は上記リンクにありますが、一言で言うと、コーディングの問題がA~Oの15問出題され、点数に応じてランクが認定される資格試験です。
問題数とランクについては以下の通り。
【問題数】15問（1問目=9点／2～3問目=8点／4～6問目=7点／7～15問目=6点）、100点満点
【ランク】エントリー（25-39点）、初級（40-59点）、中級（60-79点）、上級（80-89点）、エキスパート（90-100点）
結果
A~HとJを解いて、合計64点で中級でした。試験時間は5時間なのですが、色々とハマって5時間ぎりぎりまで解いていたので、大変疲れました。AtCoderのレートが緑で中級は妥当なラインなので、実力通りのランクが取れてよかったです。
以下、自分が解いた問題について解説しようと思います。
A - ケース・センシティブ
問題概要
長さ3の英大文字・英小文字のみからなる文字列s,tが与えられます。
s,tが大文字と小文字の違いを含めて一致するなら same を、
そうでなく大文字と小文字の違いを区別しない場合に一致するなら case-insensitive を、以上に該当しないなら different を出力せよ。
入力例
AbC
ABc
出力例
case-insensitive
提出コード
s = gets.chomp
t = gets.chomp
if s == t
puts "same"
elsif s.downcase == t.downcase
puts "case-insensitive"
else
puts "different"
end問題通りに場合分けを行いました。
大文字と小文字の違いを含めて一致するかどうかは、両方の文字列を全て大文字か全て小文字に揃えた場合に一致するかを見ればよいです。
ちなみに実装が楽そうだったのでこの問題はRubyで解きましたが、以降の問題はc++で解いています。
B - ダイナミック・スコアリング
問題概要
M問の問題が出題されるコンテストに、N人が参加する。
コンテストの問題の得点はN−(現時点でこの問題を解いた人数)で表される。
参加者のスコアは、解いた問題の得点の合計である。
例えばN=2, M=1の場合、はじめ問題1の得点は2で、その後参加者1が問題1を解いたとき、問題1の得点は1、参加者1のスコアは1となる。 さらにその後、参加者2が問題1を解いたとき、問題1の得点は0となり、参加者1,2のスコアは0となる。
このとき、Q個のクエリを順番に処理せよ。クエリは1,2のいずれかである
1. 参加者nの現在のスコアを出力する。
2. 参加者nが問題mを解いた。
提出コード
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m,q;
cin >> n >> m >> q;
vector<vector<int>> solved(n,vector<int>());
vector<int> points(m,n);
vector<int> anss;
for (int i = 0; i < q; i++)
{
int qi,ni;
cin >> qi >> ni;
ni--;
if(qi==1){
int sum = 0;
for(int sol : solved[ni]){
sum += points[sol];
}
anss.push_back(sum);
}
else{
int mi;
cin >> mi;
mi--;
points[mi]--;
solved[ni].push_back(mi);
}
}
for(int ans : anss) cout << ans << endl;
}参加者nの現在のスコアはその時点での問題の解かれ具合によって変わるので、必要な情報を保持しておくために、各問題の現在の得点をpointsに、参加者ごとに解いた問題をsolvedに格納しました。
これにより各クエリを、以下のように処理することが出来ます。
1. 参加者nの現在のスコアを出力する。
→ 参加者nが解いた問題リストを見て、それぞれの現在の得点を合計
2. 参加者nが問題mを解いた。
→ 問題mの得点を1点下げ、参加者nが解いた問題リストに問題mを追加
C - 等比数列
問題概要
初項A、公比Rの等比数列の第N項が 10^9より大きければlargeを、
10^9以下ならその値を出力せよ。
制約
1 <= A,R,N <= 10^9
提出コード
#include <bits/stdc++.h>
using namespace std;
int main(){
long long a,r;
int n;
cin >> a >> r >> n;
if(r==1){
cout << a << endl;
return 0;
}
for (int i = 0; i < n-1; i++)
{
if(a > 1000000000 / r){
puts("large");
return 0;
}
a *= r;
}
cout << a << endl;
}AにRをN-1回かけていき、途中で10^9を超える場合は、largeを出力して終了すればよいです。
R=1の場合はAに1を何度かけてもAのままなので、Aを出力します。このときNが最大10^9なので、そのままfor文を回してしまうとTLEするので注意が必要です。
第N項が 10^9より大きいかどうかは、
a*r > 10^9 => a > 10^9/r と変形して判定することで、オーバーフローしないようにしています。(今回の制約では必要ないですが)
D - 電光掲示板
問題概要
Nと、5行4N+1列の文字列で表されるN桁の数字列が与えられるので、
そのN桁の数字列を出力せよ。
入力例
10
.###..#..###.###.#.#.###.###.###.###.###.
.#.#.##....#...#.#.#.#...#.....#.#.#.#.#.
.#.#..#..###.###.###.###.###...#.###.###.
.#.#..#..#.....#...#...#.#.#...#.#.#...#.
.###.###.###.###...#.###.###...#.###.###.出力例
0123456789
提出コード
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
vector<string> s(5);
vector<int> anss;
cin >> n;
for (int i = 0; i < 5; i++) cin >> s[i];
for (int i = 1; i <= n; i++)
{
int cnt = 0;
for (int j = 0; j < 5; j++)
{
for (int k = 4*i-3; k < 4*i; k++)
{
if(s[j][k]=='#') cnt++;
}
}
if(cnt==7) anss.push_back(7);
if(cnt==8) anss.push_back(1);
if(cnt==9) anss.push_back(4);
if(cnt==13) anss.push_back(8);
if(cnt==11){
if(s[3][4*i-3]=='#') anss.push_back(2);
else if(s[1][4*i-1]=='#') anss.push_back(3);
else anss.push_back(5);
}
if(cnt==12){
if(s[1][4*i-3]=='#' && s[1][4*i-1]=='.') anss.push_back(6);
else if(s[3][4*i-3]=='#') anss.push_back(0);
else anss.push_back(9);
}
}
for(int ans:anss) cout << ans;
cout << endl;
}数字を構成する'#'の個数を数えて場合分けを行いました。構成する'#'の個数が同じだった場合は、特定の位置が'#'かどうかを見て、更に場合分けを行なっています。
解答例を見て知ったのですが、以下のように入力例で与えられた文字列をそのまま配列に格納し、4桁ずつ見てどの数字と一致するかを確認すれば、面倒な場合分けをせずに済みます。
string digits[5] = {
".###..#..###.###.#.#.###.###.###.###.###.",
".#.#.##....#...#.#.#.#...#.....#.#.#.#.#.",
".#.#..#..###.###.###.###.###...#.###.###.",
".#.#..#..#.....#...#...#.#.#...#.#.#...#.",
".###.###.###.###...#.###.###...#.###.###.",
}E - スプリンクラー
問題概要
N頂点M辺の無向グラフが与えられ、各頂点にはそれぞれ色が塗られている。それぞれの頂点にはスプリンクラーが設置されている。 頂点iにあるスプリンクラーを起動すると、頂点iに隣接する全ての頂点の色がスプリンクラー起動時点の頂点iの色で塗り替えられる。
このとき、Q個のクエリを順番に処理せよ。クエリは1,2のいずれかである。
1. 頂点xの現在の色を出力し、頂点xにあるスプリンクラーを起動する。
2. 頂点xの現在の色を出力し、頂点xの色をyで上書きする。
提出コード
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m,q;
cin >> n >> m >> q;
vector<vector<int>> g(n,vector<int>());
for (int i = 0; i < m; i++)
{
int u,v;
cin >> u >> v;
u--;
v--;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> c(n);
for (int i = 0; i < n; i++) cin >> c[i];
vector<int> anss;
for (int i = 0; i < q; i++)
{
int qi,x;
cin >> qi >> x;
x--;
if(qi==1){
anss.push_back(c[x]);
for(int rin: g[x]) c[rin] = c[x];
}
else{
anss.push_back(c[x]);
int y;
cin >> y;
c[x] = y;
}
}
for(int ans:anss) cout << ans << endl;
}グラフの情報を隣接リストで持っておき、スプリンクラーを起動したときに、隣接する頂点を全て列挙して色を塗り替えました。
F - 回文行列
問題概要
整数N及び小文字アルファベットからなるN × N行列aが与えられる。
以下の条件を満たすような長さNの文字列Sをいずれか1つ出力せよ。
条件を満たす文字列が存在しない場合は -1 を出力せよ
・文字列Sは英小文字から構成される
・文字列Sは回文である
・Siはai1,ai2,…,aiN のいずれかと同じ文字である
提出コード
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
vector<map<char,int>> cnts(n);
for (int i = 0; i < n; i++)
{
string s;
cin >> s;
for (int j = 0; j < n; j++) cnts[i][s[j]]++;
}
string front = "";
string back = "";
for (int i = 0; i < (n+1)/2; i++)
{
for(char c='a'; c<='z'; c++){
if(cnts[i][c]>=1 && cnts[n-1-i][c]>=1){
front.push_back(c);
back.push_back(c);
break;
}
if(c=='z'){
cout << -1 << endl;
return 0;
}
}
}
if(n%2==1){
front.pop_back();
}
reverse(back.begin(),back.end());
cout << front + back << endl;
}文字列 S は、行列 a の i 行目と n-i-1 行目から同じ文字を選ぶことで構成できます。(0 <= i <= (n+1)/2-1)
そのような文字が存在しない場合は -1 を出力します。
2つの行に同じ文字が存在するかどうかは、行ごとにその行に存在する 'a'~'z' の個数を数えておき、2つの行に個数が1以上となるような文字が存在するかどうかを見れば良いです。このとき for(char c='a'; c<='z'; c++){}のようにして英小文字を全探索すると楽に判定できます。
G - グリッド金移動
問題概要
無限に広がる二次元グリッド上をマス(0,0)からスタートして、マス(X,Y)に到達するまでの最小の移動回数を出力せよ。到達することが不可能であれば−1を出力せよ。
一回の移動で到達できるマスは、現在位置をマス(x,y)としたとき、
以下の 6箇所のうちのいずれかである。
(x+1,y+1), (x,y+1), (x−1,y+1), (x+1,y), (x−1,y), (x,y−1)
また、障害物のあるマスが N個あり、障害物のあるマスには移動できない。
提出コード
#include <bits/stdc++.h>
using namespace std;
int main(){
int N,X,Y;
cin >> N >> X >> Y;
map<int,map<int,int>> grid;
for (int i = 0; i < N; i++)
{
int xi,yi;
cin >> xi >> yi;
grid[xi][yi] = -1;
}
queue<pair<int,int>> q;
q.emplace(0,0);
int dx[6] = {0,1,1,0,-1,-1};
int dy[6] = {1,1,0,-1,0,1};
while(!q.empty()){
int nowx = q.front().first;
int nowy = q.front().second;
int nowcost = grid[nowx][nowy];
q.pop();
if(nowx==X && nowy==Y){
cout << nowcost << endl;
return 0;
}
for (int i = 0; i < 6; i++)
{
int nextx = nowx+dx[i];
int nexty = nowy+dy[i];
int nextcost = nowcost+1;
if(grid[nextx][nexty]!=0 || nextx<-201 || nextx>201 || nexty<-201 || nexty>201) continue;
q.emplace(nextx,nexty);
grid[nextx][nexty] = nextcost;
}
}
cout << -1 << endl;
}(0,0)から(X,Y)まで幅優先探索すればよいです。
障害物およびゴールは(-200,-200)~(200,200)の正方形の範囲にしか現れませんが、移動しうるマスの範囲は(-201,-201)~(201,201)の正方形の範囲である点に注意が必要です。
実装上は、グリッドを表す2次元mapを全て0で初期化しておき、障害物のマスを-1 、到達済みのマスをそのマスまでの移動回数で更新しました。
問題名からもわかるように、グリッド上のマスを将棋の金と同じ動きで探索する問題なのですが、問題文をよく読まずに玉と同じ動きで探索してしまい、結果、この問題に一番時間を割いてしまいました。
H - ハードル走
問題概要
数直線上を0からLまでハードル走したときに、Lを通るまでにかかる秒数の最小値を求めよ。
ハードル走では、「以下の3つの行動のうち１つを選んで行動する」を繰り返し行う。
1. 距離1を走って進む
2. 距離0.5を走って進み,ジャンプして距離1を進み,また距離0.5を走って進む
3. 距離0.5を走って進み,ジャンプして距離3を進み,また距離0.5を走って進む
走っているときは距離1あたりT1秒、
ジャンプ中は距離1あたりT2秒の速さで進む。
ただし、ジャンプ中でないときに座標 x にいて、座標 x にハードルがある場合、その地点を通り過ぎるのに追加で T3 秒の時間がかかる。
T1,T2,T3は全て偶数
提出コード
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,l;
cin >> n >> l;
map<int,int> h;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
h[x]++;
}
int t1,t2,t3;
cin >> t1 >> t2 >> t3;
vector<int> dp(l+1, 1000000007);
dp[0]=0;
for (int i = 1; i <= l; i++)
{
dp[i] = dp[i-1] + t1;
if(h[i-1]>0) dp[i]+=t3;
int time;
if(i>=2){
time = dp[i-2] + t1 + t2;
if(h[i-2]>0) time+=t3;
dp[i] = min(dp[i],time);
}
if(i>=4){
time = dp[i-4] + t1 + t2*3;
if(h[i-4]>0) time+=t3;
dp[i] = min(dp[i],time);
}
if(i==l){
if(i>=1){
time = dp[i-1] + t1/2 + t2/2;
if(h[i-1]>0) time+=t3;
dp[i] = min(dp[i],time);
}
if(i>=2){
time = dp[i-2] + t1/2 + t2*3/2;
if(h[i-2]>0) time+=t3;
dp[i] = min(dp[i],time);
}
if(i>=3){
time = dp[i-3] + t1/2 + t2*5/2;
if(h[i-3]>0) time+=t3;
dp[i] = min(dp[i],time);
}
}
}
cout << dp[l] << endl;
}dp[x] = 座標 x に到達するまでの最短時間として、DPで解きました。
座標 x に到達するパターンは、
・座標 x-1 から行動1を行う
・座標 x-2 から行動2を行う
・座標 x-4 から行動3を行う
の3パターンがあるので、これらの最小値がdp[x]となります。
ただし、座標Lをジャンプ中に通過する場合もあるので、dp[L]については、以下の3パターンも加えて最小化する必要があります。
・座標 L-1 から行動2を行う
・座標 L-2 から行動3を行う
・座標 L-3 から行動3を行う
J - 回転寿司
問題概要
1,2,3,…,Nの番号がついたN人の子供たちの前に、M個の寿司が順番に流れてくる。寿司は 1,2,3,…,N番の子供の前をこの順に通る。寿司にはそれぞれ美味しさがあり、i番目に流れてくる寿司の美味しさは aiである。
それぞれの子供は自分の前に寿司が流れてきたとき、以下のいずれかの条件を満たすときに限りその寿司を取って食べる。
・まだ寿司を一つも食べていない
・今までに食べたどの寿司よりも美味しさが大きい
それぞれの寿司について、何番の子供が食べるかを求めよ。
提出コード
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin >> n >> m;
vector<int> max_sushis(n);
for (int i = 0; i < m; i++)
{
int a;
cin >> a;
int eater = lower_bound(max_sushis.begin(), max_sushis.end(), a) - max_sushis.begin()-1;
if(eater==-1) {
cout << -1 << endl;
continue;
}
max_sushis[eater] = a;
cout << n-eater << endl;
}
}M個の寿司それぞれについて、N人のうち誰が食べるかを順に確認すると、O(MN)となり今回の制約では間に合いません。
そこで各N人の子供に対し、今まで食べた寿司のうち最も美味しかったものの美味しさに着目します。i番目の子供が今まで食べた寿司のうち最も美味しかったものの美味しさをmax_sushis[i]とすると、
max_sushis[i] >= max_sushis[j] (i<j)
が成り立ちます。もし成り立たなかったとしたら、「今までに食べたどの寿司よりも美味しさが大きい寿司を食べる」という条件に反するからです。
よって、max_sushisは広義単調減少な数列になることがわかります。
以上から、max_sushisを二分探索することでどの子供が寿司を食べるかがわかります。計算量もO(Mlog N)となり十分間に合います。
実装上は、
max_sushis[i]:=N-i番目の子供が食べた中で最も美味しかった寿司の美味しさ
と定義することで、max_sushisを広義単調増加な数列にして、lower_boundでどの子供が食べるかを探索しています。
例えば今流れてきた寿司の美味しさが3で、max_sushis = [1,2,6,8,9]であったとします。
lower_boundは美味しさが3以上の最初の要素のポインタを返すので、この場合6のポインタが返ってきます。このとき、6の一つ前の要素は必ず3未満なので、N-i = 4番目の子供が寿司を食べることがわかります。
よって4を出力し、max_sushis = [1,3,6,8,9]に更新します。
余談ですが、この問題を通したのが終了1分前だったのでかなりエキサイティングでした。(通らなかったら初級でした)
感想
初めてPASTを受験したのですが、長時間で多くの問題を解くのは疲れました。でも楽しかったです(小学生)。
また、今回だとグラフ, 幅優先探索, DP, 二分探索の基礎的な問題が出題されており、かなり教育的な問題ばかりで良いと思いました。AtCoder始めたての人もこのあたりの問題を解くのはかなり勉強になるのではないでしょうか。
私も解けなかった問題やPASTの過去問を解いて精進します。