見出し画像

第3回アルゴリズム実技検定（PAST）参戦記

知恵熱ゴリラ

てむてむ星の使者です。反省もかねてPAST第3回の参戦記を書くことにします。

結果

A～GとI～Kを解いて70点（中級）でした。緑ならこんなもんですかね。
ということで反省のために参戦記を書くことにします。（ABCDについてはコード紛失しました（喝））
記載している時間はかなり曖昧なのでご了承ください。（2つに分ければよかった）

A　ケース・センシティブ

3文字の英字列が与えられるので、
大文字小文字完全一致していれば"same"
大文字小文字の違いを除いて一致していれば"case-insensitive"
そうでなければ"different"
を出力してね。（大意）

完全一致しているか⇒両方大文字に直して一致しているか
の順で判定しました。当日はtransform関数を使って大文字に直しましたが、使い方がよくわからず若干の時間ロス。ここまでで10分ぐらい。

 B　ダイナミック・スコアリング

M個の問題が出るコンテストにN人が参加しました。各問題の配点はNマイナス（そのタイミングでその問題を解いた人の数）です。次の2種類のクエリがQ個与えられるので順に処理してください。クエリは、
１：参加者iの"現在"の得点を出力せよ
２：参加者iが問題jを解いた（ただし、同じ人間が2回以上同じ問題を解くことはない）
です。（大意）

回答済みの問題の配点が変化していくのがミソですね。
Mが最大50であったため、
「各参加者が問題jを解いているかどうか」という配列と、
「問題jは今何点の問題か」という配列を作り
毎回得点計算しなおす戦略を立てました。
前者はlist[i][j]:=「iさんがjを解いていればtrue,そうでないならばfalse」
後者はscore[j]:=「jの配点（初期値はN）」
みたいな感じだったと思います。

同じ問題を2度解かないことが保証されているので、2のクエリが来たときは愚直に配点を1減らせばいいだけというのがありがたいですね。

ここまでで20～25分ぐらい。

C　等比数列

初項 A、公比 R の等比数列の第N項が10^9より大きければ large を、10^9以下ならその値を整数で出力してください。
(制約)
1≦A,R,N≦10^9

例えば、R=3とかだったら、Aがどんな値でもN=25ぐらいでもうアウト（多分）なので、素朴に計算していって10^9を超えたかどうかを都度判定すればいいように思えますが、
公比が1の場合に限り一生アウトにならないため(∵Aが10^9以下)
N回掛け算を行ってTLEになると思います。試してませんが。

ここは等比級数の計算よろしく公比が1かそうでないかで場合分けをするのが良いと思いました。
(1)R=1の場合
答えはAです。
(2)R≠1の場合
Nが40ぐらいだとA,Rによらずアウトなので、おおらかにmax(N,40)回掛け算を行い、10^9を超えたタイミングで"large"を出力、ループを抜けたらそのまま出力。

みたいな感じで提出しました。ここまでで多分30～40分ぐらい。

D　電光掲示板

電光掲示板のように数字が表示されるので、それを数字列に直してね（大意）という問題。（説明しづらい……）

自分が考えた方針としては、「数字に該当する3列5行を切りだして、何の数字か判定する」というものです。
何の数字か判定するときに、「1行目が.#.なら1をreturn」「3行目が#.#なら0をreturn」みたいに確定するところからどんどん捕まえていく感じでやったのですが、あんまセンスはなかったかなと思います。ちなみに数字列は最大50桁なので十分間に合います。

ここまでで丁度60分ぐらいですかね。

E　スプリンクラー

N頂点M辺の無向グラフが与えられ、それぞれ色（1~10^5の整数で表す）が着色されている。次のQ個のクエリを順番に処理せよ。クエリは2種類あり
１：頂点xの色を出力し、隣接するすべての頂点を頂点xの色で塗りつぶせ。
２：頂点xの色を出力し、頂点xをy色に塗りつぶせ。
である。

N,Qが最大200、Mがおおらかに見積もって20000ぐらいなので、各クエリを素直に処理していっても間に合いそうです。

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
#define all(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();
int main(){
   int N,M,Q;
   cin>>N>>M>>Q;
   vector<int> u,v;
   rep(i,M){
       int a,b;
       cin>>a>>b;
       u.push_back(a-1);
       v.push_back(b-1);
   }
   vector<int> c;
   rep(i,N){
       int color;
       cin>>color;
       c.push_back(color-1);
   }

   //すべて0index管理
   vector<tuple<int,int,int>> s;
   rep(i,Q){
       int d,e,f=-1;
       cin>>d;
       if(d==1){
           cin>>e;
       }else{
           cin>>e>>f;
       }
       s.push_back(make_tuple(d,e-1,f-1));
   }

   rep(i,Q){
       //愚直に塗りなおす(QN^2だから間に合いそう)
       if(get<0>(s[i])==1){
           //1ならば出力してスプリンクラー起動
           cout << c[get<1>(s[i])]+1 << endl;
           rep(j,M){
               if(u[j]==get<1>(s[i])){
                   c[v[j]]=c[get<1>(s[i])];
               }else if(v[j]==get<1>(s[i])){
                   c[u[j]]=c[get<1>(s[i])];
               }else{
                   continue;
               }
           }
       }else{
           //2ならば出力して上書き
           cout << c[get<1>(s[i])]+1 << endl;
           c[get<1>(s[i])]=get<2>(s[i]);
       }
   }
   return 0;
}

本番では辺を全部なめて両端のどっちかにスプリンクラーがいるかを判定しましたが、解説を見たところ隣接リストを使えばもっと高速に求められるんですね。
隣接リストはまだ身についていないところなので精進します。

ここまでで90分ぐらい。

F　回文行列

各要素が英小文字1字からなる、N次正方行列が与えられます。1行目から各行1文字ずつ要素を選んで連結した際に、回文にできるならばその例を一つ構成し、できないなら-1を出力せよ。ただし1≦N≦500とします。（大意）

言い換えると次のようになります。
「1≦i≦N/2なるすべてのiに対し、i行目とN-i+1行目に同じ文字が存在するか？存在するならばそれを1つ選び、存在しないなら-1を出力せよ」

Nは最大でも500なので、各iに対して、i行目のj文字目がN-i+1行目に存在するかを総当たりしていき、あれば次の行に、なければj+1文字目を見ていく、という方針で解きました。この解き方だと最大で6.25*10^7回ぐらい判定がおこるかと思います。(N^3)/2

これで構成された文字列はあくまで回文の前半部なので、最後にそれをひっくり返したものを連結したものが答えになります。ただし、Nが奇数の場合は、ちょうど真ん中の行は何を選んでもよいので0文字目を挟んで連結しました。

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
#define all(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();
int main(){
   int N;
   cin>>N;
   if(N==1){
       string corner;
       cin>>corner;
       cout << corner << endl;
       return 0;
   }
   vector<string> an;
   rep(i,N){
       string t;
       cin>>t;
       an.push_back(t);
   }
   string ans="";
   bool nextlineflag=false;
   bool gameoverflag=true;
   rep(i,N/2){
       string tmp=an[i];
       nextlineflag=false;
       gameoverflag=true;
       rep(j,N){
           char c=tmp.at(j);
           rep(k,N){
               if(an[N-i-1].at(k)==c){
                   ans+=c;
                   nextlineflag=true;
                   gameoverflag=false;
                   break;
               }
           }
           if(nextlineflag){
               break;
           }else{
               continue;
           }
       }
       if(gameoverflag){
           cout <<-1<<endl;
           return 0;
       }
   }
   string rev="";
   int siz=ans.size();
   if(N%2==0){
       rep(i,siz){
           rev+=ans.at(siz-i-1);
       }
       ans=ans+rev;
   }else{
       rep(i,siz){
           rev+=ans.at(siz-i-1);
       }
       ans=ans+an[N/2].at(0)+rev;
   }
   cout << ans << endl;
   return 0;
}

N=1の時はそれそのものが答えとして例外的に処理しましたがいりませんねこれ。今投げたらそのブロック消しても通りました。
なんか一回範囲外を参照してエラーになったので入れたんですが今思うとそんなことないですね。

ここまでで120分ぐらいかな。もう少しかかってたかもしれません。

G　グリッド金移動

xy座標平面上の原点にすぬけ君が、（X,Y）にゴールがあり、いくつかの障害物が配置されていますが、どの障害物のx座標、y座標の絶対値も200以下です。すぬけ君は一回の移動で右、右上、上、左上、左、下の6方向のいずれかに進むことができます。ゴールまでにかかる最短手数は何回でしょう。到達不能の場合は-1を出力してね。（大意）

ちょっとした考察により、すぬけ君は、x座標およびy座標の絶対値が202以上の場所に行くことがない（行く意味がない）ことがわかります。

したがって、403*403の迷路を解くことに帰着できるので、あとはBFSして終わりです。自分はいったん全座標を201右上にずらして、各座標の最短距離を-1で初期化したのですが、もう少しいいやり方もあった気がします。
あと6個の移動方法を全部書き連ねていますが、ここもちょっとナンセンスな感じがします。

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
#define all(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();


int main(){
   int N,X,Y;
   cin>>N>>X>>Y;
   X+=201;
   Y+=201;
   //すべて201右上にずらす
   set<pair<int,int>> p;
   //移動範囲は0~402までで考えてよい（それより外側はすべて壁とした迷路）
   rep(i,N){
       int x,y;
       cin>>x>>y;
       p.insert(make_pair(x+201,y+201));
   }

   //各グリッドの最短距離を-1で初期化
   vector<vector<int>> dist(403,vector<int>(403,-1));
   //スタート地点は(201,201)
   dist[201][201]=0;//startの距離は0
   queue<pair<int,int>> que;
   que.push(make_pair(201,201));//startは探索済み
   //幅優先探索(queがカラになるまで)

   while(!que.empty()){
       pair<int,int> tmp = que.front();
       que.pop();
       //pから行ける座標をすべて調べる
   
       //１．右斜め上
       if(p.count(make_pair(tmp.first+1,tmp.second+1))||tmp.first+1>=403||tmp.second+1>=403||
       tmp.first+1<0||tmp.second+1<0||dist[tmp.first+1][tmp.second+1]!=-1){
           //そこが障害物または壁または探索済みならばcontinue;
           
       }else{
       //そうでないならば、距離情報を更新してqueに入れる
       dist[tmp.first+1][tmp.second+1]=dist[tmp.first][tmp.second]+1;
       que.push(make_pair(tmp.first+1,tmp.second+1));
       }
       //２．上
       if(p.count(make_pair(tmp.first,tmp.second+1))||tmp.first>=403||tmp.second+1>=403||
       tmp.first<0||tmp.second+1<0||dist[tmp.first][tmp.second+1]!=-1){
           //そこが障害物または壁または探索済みならばcontinue;
           
       }else{
       //そうでないならば、距離情報を更新してqueに入れる
       dist[tmp.first][tmp.second+1]=dist[tmp.first][tmp.second]+1;
       que.push(make_pair(tmp.first,tmp.second+1));
       }
       //３．左斜め上
       if(p.count(make_pair(tmp.first-1,tmp.second+1))||tmp.first-1>=403||tmp.second+1>=403||
       tmp.first-1<0||tmp.second+1<0||dist[tmp.first-1][tmp.second+1]!=-1){
           //そこが障害物または壁または探索済みならばcontinue;
        //   continue;
       }else{
       //そうでないならば、距離情報を更新してqueに入れる
       dist[tmp.first-1][tmp.second+1]=dist[tmp.first][tmp.second]+1;
       que.push(make_pair(tmp.first-1,tmp.second+1));
       }
       //４．右
       if(p.count(make_pair(tmp.first+1,tmp.second))||tmp.first+1>=403||tmp.second>=403||
       tmp.first+1<0||tmp.second<0||dist[tmp.first+1][tmp.second]!=-1){
           //そこが障害物または壁または探索済みならばcontinue;
        //   continue;
       }else{
       //そうでないならば、距離情報を更新してqueに入れる
       dist[tmp.first+1][tmp.second]=dist[tmp.first][tmp.second]+1;
       que.push(make_pair(tmp.first+1,tmp.second));
       }
       //５．左
       if(p.count(make_pair(tmp.first-1,tmp.second))||tmp.first-1>=403||tmp.second>=403||
       tmp.first-1<0||tmp.second<0||dist[tmp.first-1][tmp.second]!=-1){
           //そこが障害物または壁または探索済みならばcontinue;
        //   continue;
       }else{
       //そうでないならば、距離情報を更新してqueに入れる
       dist[tmp.first-1][tmp.second]=dist[tmp.first][tmp.second]+1;
       que.push(make_pair(tmp.first-1,tmp.second));
       }
       //６．下
       if(p.count(make_pair(tmp.first,tmp.second-1))||tmp.first>=403||tmp.second-1>=403||
       tmp.first<0||tmp.second-1<0||dist[tmp.first][tmp.second-1]!=-1){
           //そこが障害物または壁または探索済みならばcontinue;
        //   continue;
       }else{
       //そうでないならば、距離情報を更新してqueに入れる
       dist[tmp.first][tmp.second-1]=dist[tmp.first][tmp.second]+1;
       que.push(make_pair(tmp.first,tmp.second-1));
       }
   }

   //出力
   cout << dist[X][Y] << endl;
   return 0;
}

ここまでで150分ぐらいかな。

H　ハードル走

解けませんでした。設定を見て間違いなくDPだと思い遷移を考えた結果、頭が真っ白になったので一旦飛ばしたものの、帰ってくることなく試験が終わりました。DPは正直身についていないので精進します。

すぬけ君が数直線上の座標0からLに向かってハードル走を行います。いくつかの座標に（スタートとゴールを除く）ハードルが配置されています。
すぬけ君は、
１：距離１走って進む。
２：距離0.5走り、距離１ジャンプし、距離0.5走る。
３：距離0.5走り、距離３ジャンプし、距離0.5走る。
のいずれかの行動をゴールするまで繰り返します。
走っているときは距離１あたりT1秒、ジャンプ中は距離１当たりT2秒、ハードルにぶつかった（ジャンプ中でないときにハードルのある座標にいる）時は追加でT3秒かかります。ゴールするまでにかかる時間の最短はいくつですか。（大意）

結局のところ、整数座標の通過の仕方は次のように分類されると考えました。
0：走って通過
1：距離１ジャンプで通過
2：距離３ジャンプの序盤で通過
3：距離３ジャンプの中盤で通過
4：距離３ジャンプの終盤で通過

なのでdp[i][j]:=「座標iを状態jで通過した際のかかる時間の最小値、ただしj=0,1,2,3,4のいずれか」
と置けばいいかなと考えて漸化式を立てようと思ったのですが、遷移が多くて筆が進まず断念。10分ぐらい考えてひとまず次の問題へ。

I　行列操作

整数を要素に持つN次正方行列があります。初期時点での各要素は
1行目：0,1,2,...,N-2,N-1
2行目：N,N+1,...,2N-2,2N-1
...
N行目：N^2-N,N^2-N+1,...,N^2-2,N^2-1
です。

例えばN＝3の時は
0,1,2
3,4,5
6,7,8
といった感じです。

次の4種類のクエリがQ個与えられるので、順番に処理せよ。
１：A行目とB行目を列の位置はそのまま交換せよ。
２：A列目とB列目を行の位置はそのまま交換せよ。
３：行列を転置せよ。
４：現時点のA行B列の要素を出力せよ。
ここで、1≦N,Q≦10^5とする。（大意）

まず、行列のすべての要素を記憶しておくのは時間的に無理だということがわかります。

これは机上でN=3のケースをいろいろといじっていて気づいたのですが、
初期時点で同一行にいる要素たちを塊としてみた時に、転置や列交換、行交換を何度行っても、その塊は必ず同一行ないし同一列に並びます。

どういうことかというと、例えば（0,1,2）という3個1組を塊としてみた際に、転置、行交換、列交換だけではその塊を分裂させることは出来ないということです。
あわせて、転置を奇数回行った場合はその塊は縦並びに、偶数回行った場合は横並びに並ぶこともわかります。

例
初期配置
012
345
678

1列目と3列目を入れ替え
210
543
876

転置
258
147
036

2列目と3列目を入れ替え
285
174
063

転置
210
876
543

※{012}{345}{678}の塊そのものは一列に並ぶ。
更に、並び方は各塊で同じであることにも気づけます。
※各塊を前からx,y,zと置くと、塊はすべてz,y,xの順に並んでいる。
証明は割愛します。


ここまでわかれば後は、
・転置が何回起こったのか
・それぞれの塊がどの位置なのか（奇数回転置なら左から何番目か、偶数回転置なら上から何番目かを表すことになる）
・塊内部の順番はどうなっているか（同上）

をそれぞれ管理することで、O(Q)で解けることがわかります。
実際のコードでは塊の先頭を代表としてそれぞれの塊の場所を、塊内部の順番を内部配列として管理しました。（命名がイッちゃってるのは許してください）

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
#define all(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();
int main(){
   long long N,Q;
   cin>>N>>Q;
   vector<tuple<int,int,int>> Qu;
   rep(i,Q){
       int d,A=0,B=0;
       cin>>d;
       if(d!=3){
           cin>>A>>B;
       }
       Qu.push_back(make_tuple(d,A,B));
   }
   //0~N-1,N~2N-1...N^2-N~N^2-1というN個の塊で考える
   //転置⇒縦並びと横並びが入れ替わるだけ（最初は塊は横並び）
   //1の操作：
   //横並びなら塊の場所が交換されるだけ
   //縦並びならすべての塊内部の並び順が交換されるだけ
   //2の操作：
   //1の縦と横のときが逆になっただけ
   
   //縦並びか横並びかを管理して、塊の代表元（0,N,2N,..,N^2-N）の場所と
   //代表塊(0,1,2,3,,...N-1)の内部の位置だけを意識すればよい
   bool yoko = true;//最初は横並び
   vector<long long> gen;//塊の代表元の集合最初は横列が縦に並ぶ
   rep(i,N){
       gen.push_back(i*N);
   }
   vector<long long> naibu(N);//内部の並び方
   rep(i,N){
       naibu[i]=i;
   }

   //例えば、今横並びの状態で、a[i][j]を出せと言われたら、iが塊の場所、jが内部の場所となる
   rep(i,Q){
       if(get<0>(Qu[i])==4){
           if(yoko){
           cout << gen[get<1>(Qu[i])-1]+naibu[get<2>(Qu[i])-1] << endl;
           continue;
           }else{
           cout << naibu[get<1>(Qu[i])-1]+gen[get<2>(Qu[i])-1] << endl;
           continue;    
           }
       }
       if(get<0>(Qu[i])==3){
           yoko=!yoko;
           continue;
       }
       if(get<0>(Qu[i])==1){
           if(yoko){
               //横並び時の行交換は代表元の交換
               swap(gen[get<1>(Qu[i])-1],gen[get<2>(Qu[i])-1]);
           }else{
               //縦並び時の行交換は内部配列の交換
               swap(naibu[get<1>(Qu[i])-1],naibu[get<2>(Qu[i])-1]);
           }
       }
       if(get<0>(Qu[i])==2){
           if(yoko){
               //横並び時の列交換は内部配列の交換
               swap(naibu[get<1>(Qu[i])-1],naibu[get<2>(Qu[i])-1]);
           }else{
               //縦並び時の列交換は代表元の交換
               swap(gen[get<1>(Qu[i])-1],gen[get<2>(Qu[i])-1]);
           }
       }
   }
   return 0;
}

こういうのを一目で気づけるようになりたいですね。
ここまでで180分ぐらいでしょうか。

J　回転寿司

N人の子供が回転寿司にやってきました。子供にはそれぞれ１からNまでの番号がふられています。
M個の寿司が順番に流れてきます。i番目の寿司のおいしさはa[i]です。
寿司は子供の前を若い番号順に流れていきます。
各子どもは、
・寿司をまだ一つも食べていない（ルール１）
または
・今までに食べたどの寿司よりもおいしさ度が大きい（ルール２）
のいずれかを満たすとき、その寿司を食べます。
各寿司を何番の子供が食べるか出力せよ。誰にも食べられない場合は-1を出力せよ。ただし、Nは最大10^5、Mは最大3*10^5（大意）

i番目の人が食べた寿司のおいしさの最大値をsushimax[i]と表すことにしました。（せめておいしさmaxとかにすれば良かった）
ルール２は、流れてきた寿司のおいしさがsushimax[i]より大きいか？
で判定することができます。
さらにここでsushimaxの初期値を0とすることで、ルール1をルール2に包含させることができます。（おいしさは正の値なので、何も食べていなければ必ず食べることになる）

ここで次の事実がわかります。
・任意のi<jについて、sushimax[i]≧sushimax[j]

理由は簡単で、もしsushimax[i]＜sushimax[j]であれば、sushimax[j]を与えた寿司は子供の配置上、必ずi番目の子供を通り過ぎているはずなので、その時点でi番目の子供が食べているはずだからです。

よって、各寿司について、そのおいしさがsushimax[i]を超える最小のiを探すことを二分探索で求めることができます。

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
#define all(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();
int main(){
   int N,M;
   cin>>N>>M;
   vector<int> a;
   rep(i,M){
       int v;
       cin>>v;
       a.push_back(v);
   }
   vector<int> sushimax(N,0);//i番目の人が今までに食った寿司のおいしさの最大値（初期値0）

   //各寿司jについて、sushimaxの単調性よりjのおいしさが始めてsushimax[i]を超えるようなiが食す人になる
   //⇒にぶたん
   rep(i,M){
       int tmpmax=N-1;
       int tmpmin=0;
       int tmp=(tmpmax+tmpmin)/2;
       if(sushimax[N-1]>=a[i]){
           cout << "-1" << endl;
           continue;
       }
       while(tmpmax!=tmpmin){
           if(sushimax[tmp]>=a[i]){
               tmpmin=tmp;
               tmp=(tmpmax+tmpmin)/2;
           }else{
               tmpmax=tmp;
               tmp=(tmpmax+tmpmin)/2;
           }
           if(tmpmax-tmpmin==1){
               if(sushimax[tmpmin]>=a[i]&&sushimax[tmpmax]<a[i]){
                   tmpmin=tmpmax;
               }
           }
       }
       sushimax[tmpmax]=a[i];
       cout << tmpmax+1 << endl;


   }
   return 0;
}

多分ここまでで240分ぐらいだと思います。

K　コンテナの移動

残り7~8分ぐらいで何とかACした問題です。

N個の机とN個のコンテナがあり、最初机iにはコンテナiが乗っています。
次のQ個のクエリを順に処理し、最終的にどのコンテナがどの机の上に乗っているかを出力しなさい。

クエリ：机fにあるコンテナxを、（その上に乗っかっているコンテナたちがあればそのままxの上に乗せた状態で）机tの上に（すでに机tにコンテナがいくつか乗っていればその上に）乗せなさい。

ここで、N,Qは最大2*10^5である。（大意）

自分の方針は、机をボス、真下のコンテナを直属の上司と考えた木ととらえて、コンテナの移動は上司の付け替えだと考えて解きました。
「fからtにコンテナxを移動する」
⇔
「xの新しい上司をtの元末端の人に更新」
かつ「fの末端の人をxの元上司だった人に更新」
かつ「tの新しい末端の人をfの元末端だった人に更新」

これでコンテナの移動自体はO(Q)で完了できます。
あとは各要素を上までたどって誰がボスかを判定するだけですが、
単純にボスに行きつくまでたどるを繰り返した場合、最終形※によっては
O(N^2)かかってしまい間に合いません。（一敗）
※例えば全部同じ机の上にある場合

たどる途中で遭遇した要素はすべて同じボスであることが確定しているため、メモ化して無駄をなくすことで対処しました。これでも1200msecなのでもうすこしいいやり方があるのだと思いますがどうなんでしょうか。

※机の番号と人の番号が被っていて気持ち悪いので、全部1-indexで管理して
ボスは負数として実装しています。が、逆にわかりづらくなってしまったような気がします。

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
#define all(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();
int main(){
   int N,Q;
   cin>>N>>Q;
   vector<tuple<int,int,int>> op;
   rep(i,Q){
       int f,t,x;
       cin>>f>>t>>x;
       op.push_back(make_tuple(f,t,x));
   }
   //机をボス、真下のコンテナを直属の上司だと考えた木と考えれば、コンテナの移動は
   //上司の付け替えだと考えられる
   vector<int> leaf(N+1);
   //葉さえ分かっていればいい
   for(int i=1;i<=N;i++){
       leaf[i]=i;
       //机iの葉は最初i
   }
   map<int,int> oyako;//<自分、親>で管理
   //親子関係だけ入れておく
   for(int i=1;i<=N;i++){
       oyako.emplace(i,-i);//親がボスの場合-iとする
   }
   rep(i,Q){
       int f =get<0>(op[i]);
       int t =get<1>(op[i]);
       int x =get<2>(op[i]);
       //机fのコンテナxを机tに移動
       //⇒fの葉を対比させといて、fの葉をxの上司にすげ替え＆xの上司をtの葉にすげ替え＆tの葉をfの葉から持ってくる
       int tmp=leaf[f];
       
       leaf[f]=oyako[x];
       oyako[x]=leaf[t];
       leaf[t]=tmp;
   }
   //後は上司をたどって行けばよい
   //無駄のないようにメモかしておく
   map<int,int> ans;
   for(int i=1;i<=N;i++){
       ans.emplace(i,-1);
   }
   set<int> sameroot;//同じ根のもの
   for(int i=1;i<=N;i++){
       int now=i;
       sameroot.clear();
       while(1==1){
          if(now<0){
              ans[i]=now*(-1);
              for(int l:sameroot){
                  ans[l]=now*(-1);
              }
              cout << now*(-1) << endl;
              break;
          }else{
              now=oyako[now];
              if(now>0){
                  sameroot.insert(now);
              }
              if(now>0&&ans[now]!=-1){
                  cout << ans[now] << endl;
                  ans[i]=ans[now];
               for(int l:sameroot){
                  ans[l]=ans[now];
              }
                  break;
              }
          }  
       }
   }

   //cout << ans[1] << ans[2] << ans[3] << endl;


   return 0;
}

試験時間ギリギリでしたがなんとかACすることができました。


感想

5時間ぶっ続けでやって最後ギリギリACなので、もう少しスピーディに実装したいですね。
とはいえ緑なりたてとしてはまあ相応な結果ではないでしょうか。

ちなみにL以降の問題は見てすらいないので後で確認します。
あとDPは精進します。
（Hの解説見ても、接地した状態だけを考えていい理屈がわかっていないのでまだまだですね）


この記事が気に入ったらサポートをしてみませんか？