現在の進捗
満点解法まですべて作成済みです。
他の問題はこちらから。
https://qiita.com/clara775/items/57dbe85edcad1f4483c8
問題
日本語問題文はこちら
問題概要
N人がM日にわたり1日1回試合をします。それぞれの試合では1つ新しく勝者にメダルが与えられます。
$i$回目の試合では参加者$x_i$が$y_i$に勝利しました。この時、$x_i$は$y_i$の持っているメダル全てと、新しいメダル1つを獲得することができます。
M回の試合が全て終わった後、各メダルはそのメダルを一番長く保持していた人（保持は連続日数である必要なし）に渡されます。タイがいれば、参加者番号の最も小さい人に渡されます。各参加者のメダル獲得数を計算しなさい。
小課題1 N=2
2人の参加者は、それぞれのメダルについて、そのメダルが渡される日のあとに勝った試合数分だけメダルを保持していることになります。よって、試合を後ろから辿っていき、その日から最終日までに勝った試合数を2人について数えることで、各メダルがどちらに渡されるか判断することができます。
全体計算量は$O(N+M)$です。
小課題2 N,Mが2000以下
愚直なシミュレーションをすれば良いです。各参加者がその時保持しているメダルのリストを管理し、試合のたびにそれを更新します。また、メダルと参加者のペアそれぞれについて、何日そのメダルが参加者に保持されていたかを記録しておきます。最後に、各メダルについて、一番保持日数が多かった人をN人の中から探せば良いです。
全体計算量は、メダルのリストの更新が$O(M^2)$、最後にメダルがどの参加者に渡されるかの計算が$O(NM)$なので、合わせて$O((N+M)M))$になります。
小課題3 前回の試合の勝者が次の試合に必ず参加する
この小課題では、試合$i$の勝者は必ずメダル0からメダル$i$までを持っていることがわかります。なぜなら、前回の勝者がメダル0からメダル$i-1$まで持っており、試合$i$で前回の勝者が勝った場合は新たにメダル$i$を獲得、負けた場合はその相手がメダル0からメダル$i-1$を全て受け取り、新たにメダル$i$を獲得するため帰納的にこれがわかります。
つまり、小課題1と同じように最後の試合からどの参加者がメダルを保持していたかを追っていき、メダル$i$は$i$日目から最終日までに最も多く勝った参加者が受け取ります。これはそれぞれの参加者について勝った回数を記録しつつ、暫定で最も多く勝った参加者を持っておいて、必要に応じて最も多く勝った参加者を更新することで$O(M)$で実現することができます。
全体計算量は$O(N+M)$です。
小課題4 それぞれの試合で、勝者のメダルの数は敗者以上である
すべての試合はより多く（または同じ数の）メダルを保持している方が勝ちます。つまり、あるメダルについてその保持者が変わるとき、新しい保持者の方が元々多くメダルを持っているので、そのメダルの保持者の持っているメダルの総数は必ず2倍以上になります。
よって、それぞれのメダルについて保持者が変わる回数は多くても$\log M$回となります。
この小課題では小課題2のようにすべてのメダルと参加者のペアについて保持日数を記録することはできないので、代わりに各メダルについて歴代の保持者といつ保持し始めたかを記録しておきます。各メダルについて保持者は最大$\log M$人しかいないので、これは可能です。最後に、各メダルについてどの参加者が最も長くメダルを保持していたか数えます。
全体計算量は、$O(M\log M+N)$です。
小課題5 一度負けた参加者は二度と試合に参加しない
まず、各試合を頂点とし、試合$x$の親は次に試合$x$の勝者が現れる試合とした有向の森を考えます。これにもう一つフェイクの頂点を足して根とし、森が木になるようにします。
このグラフ上で、各メダルについてその保持者の変遷は、そのメダルが最初に与えられた時から根までのパスを追うことでわかります。またこのグラフでは、ある参加者が参加した試合はすべて隣り合っています。
よって、このグラフの根からDFSを行い、その際根からその頂点まで誰が一番長くメダルを保持していたかと、各頂点でのメダルの保持者と保持日数を管理すれば良いです。
全体計算量は$O(N+M)$です。
小課題6 満点解法
小課題5と同じように木を構築すると、一度負けた参加者がまた参加する可能性があるため、ある参加者が参加した試合が一つのパスになるとは限りません。よって、最長保持者を記録するだけでなく、すべての参加者についてメダルの保持日数を数える必要が出てきます。
ただし、あるメダルについてその保持者が参加する試合は、今まで通り一つのパス上に存在することがわかります。よってこれはDFSの際にすべての参加者について、そのパス上でのメダルの保持日数を記録しつつ、各メダルについての最長保持者を記録しておくことで実現できます。
選手当時書いたコード（汚い）
#include <bits/stdc++.h>
using ll=long long;
using edge=std::pair<ll,std::pair<ll,ll>>;//行き先、その時のメダル保持者、保持日数
const ll INF=(1LL<<60);
void dfs(const std::vector<std::vector<edge>>&graph, int p, std::vector<ll>&vec,ll maxx, std::vector<ll>&maxp){
//dfs(グラフ、今の頂点、パス上でのそれぞれの参加者のメダル保持日数、最長メダル保持日数、それぞれのメダルの最長保持者)
ll maxx1=maxx;
for(const auto&edge:graph[p]){
maxp[edge.first]=maxp[p];
vec[edge.second.first]+=edge.second.second;
if(vec[edge.second.first]>maxx){
maxx=vec[edge.second.first];
maxp[edge.first]=edge.second.first;
}
else if(vec[edge.second.first]==maxx&&edge.second.first<maxp[p]){
maxp[edge.first]=edge.second.first;
}
dfs(graph, edge.first, vec, maxx, maxp);
vec[edge.second.first]-=edge.second.second;
maxx=maxx1;
}
}
int main(){
ll n,m;
std::cin >> n >> m;
std::vector<ll>latest(m,-1);//メダルの現在の保持者（-1で該当者なし）
std::vector<ll>people(n,-1);//参加者が最後に獲得したメダル（-1で獲得メダルなし）
std::vector<std::vector<edge>>graph(m+1);
for(int i=0;i<m;++i){
ll x,y;
std::cin >> x >> y;
if(people[x]!=-1){
graph[i].push_back({people[x],{x,i-people[x]}});
}
if(people[y]!=-1){
graph[i].push_back({people[y],{y,i-people[y]}});
}
latest[i]=x;
people[x]=i;people[y]=-1;
}
std::vector<int>indegree(m);//入次数
for(int i=0;i<m;++i){
for(const auto&to:graph[i]){
indegree[to.first]++;
}
}
for(int i=0;i<m;++i){
//フェイクの根にまとめて木にする
if(indegree[i]==0)graph.back().push_back({i,{latest[i],m-i}});
}
std::vector<ll>vec(n),maxp(m);
ll maxx=0;
dfs(graph, m, vec, maxx, maxp);
std::vector<ll>res(n);//参加者それぞれの獲得したメダル数
for(int i=0;i<m;++i){
res[maxp[i]]++;
}
for(const auto&r:res)std::cout << r << ' ';
std::cout << '\n';
}