「ライブプログラミング」：ITMO大学でのICPC地域準決勝

12月上旬、ICPC学生プログラミング世界選手権の準決勝。 スポーツプログラマーのメインワールドトーナメントで、参加者が合格した「テスト」と、春に北ユーラシア地域を代表する人を紹介します。





^{icpcnews / Flickr / CC BY /最終ICPC-2017}

15人の勝者

300以上のチームが参加したコンペティションは、サンクトペテルブルク、バルナウル、トビリシ、アルマアタの4つの会場で同時に開催されました。 ITMO大学は、ロシアとバルト諸国から100以上のチームを受け入れています。 参加者はNEERC北ユーラシアカップとICPCファイナルに行く権利のために戦った。





モスクワ州立大学のチームは、 11の問題を解決し、絶対的なチャンピオンになりました 。 誰ももうこれをすることができませんでした。 2位と3位はMIPTからの参加者でした。 「バトル」の進行状況をライブで見ることができます。 ICPC YouTubeチャンネルにエントリがあります：





ICPC-2019のファイナルでは、ITMO大学のメンバーを含む合計15チームが選出されました（リスト全体はこちらで確認できます ）。 3月下旬に、彼らはポルト（ポルトガル）の都市に行き、世界チャンピオンの称号を得るために戦います。

準決勝はどうでしたか？

学生はJava、C ++、Python、またはKotlinプログラミング言語を使用しました。 すべてのタスクには、注意力、集中力、さまざまなアルゴリズムの知識が必要でした。



たとえば、次のタスクは、ITMO大学チームGennady Korotkevichの一部として、ICPCの2回の受賞者によって提案されました。

無向無加重グラフがあります。 2つの頂点uとvの間の距離は、最短パスのエッジの数によって決まります。 頂点のすべての無秩序なペアの合計d（u、v）を見つけます。



最初に、2つの数値nおよびm （2≤n≤10 ⁵ ; n-1≤m≤n + 42）-頂点とエッジの数がそれぞれプログラム入力に供給されます。 頂点には1からnまでの番号が付けられています。 次に、2つの整数値x _iおよびy _i （1≤x _i 、y i≤n; x _i ≠y _i ）でm行が入力されます-これらはi番目のエッジの終点です。 頂点のペアの間に少なくとも1つのエッジがあります。



ソリューションを含むプログラム例（審査員により提案）：

C ++コード

#undef _GLIBCXX_DEBUG #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector<set<int>> gs(n); for (int i = 0; i < m; i++) { int x, y; cin >> x >> y; x--; y--; gs[x].insert(y); gs[y].insert(x); } long long ans = 0; vector<int> weight(n, 1); set<pair<int,int>> s; for (int i = 0; i < n; i++) { s.emplace(gs[i].size(), i); } while (s.size() > 1) { int i = s.begin()->second; assert(!gs[i].empty()); if (gs[i].size() > 1) { break; } s.erase(s.begin()); int j = *gs[i].begin(); gs[i].clear(); ans += (long long) 2 * weight[i] * (n - weight[i]); weight[j] += weight[i]; auto it = gs[j].find(i); assert(it != gs[j].end()); s.erase({gs[j].size(), j}); gs[j].erase(it); s.emplace(gs[j].size(), j); } if (s.size() == 1) { cout << ans / 2 << '\n'; return 0; } vector<vector<int>> g(n); for (int i = 0; i < n; i++) { g[i] = vector<int>(gs[i].begin(), gs[i].end()); } vector<int> id(n, -1); int cnt = 0; for (int i = 0; i < n; i++) { if ((int) g[i].size() > 2) { id[i] = cnt++; } } if (cnt == 0) { for (int i = 0; i < n; i++) { if ((int) g[i].size() == 2) { id[i] = cnt++; break; } } assert(cnt > 0); } vector<int> rev_id(n, -1); for (int i = 0; i < n; i++) { if (id[i] != -1) { rev_id[id[i]] = i; } } vector<vector<vector<vector<int>>>> edges(cnt, vector<vector<vector<int>>>(cnt)); for (int i = 0; i < n; i++) { if (id[i] >= 0) { for (int j : g[i]) { if (id[j] >= 0) { edges[id[i]][id[j]].emplace_back(); } } } } for (int i = 0; i < n; i++) { if ((int) g[i].size() == 2 && id[i] == -1) { vector<int> edge; edge.push_back(weight[i]); id[i] = -2; vector<int> fin(2); for (int dir = 0; dir < 2; dir++) { int x = g[i][dir]; int px = i; while (id[x] == -1) { assert((int) g[x].size() == 2); edge.push_back(weight[x]); id[x] = -2; int nx = px ^ g[x][0] ^ g[x][1]; px = x; x = nx; } fin[dir] = x; reverse(edge.begin(), edge.end()); } edges[id[fin[1]]][id[fin[0]]].push_back(edge); } } vector<vector<int>> dist(cnt, vector<int>(cnt, n + 1)); for (int i = 0; i < cnt; i++) { dist[i][i] = 0; } for (int i = 0; i < cnt; i++) { for (int j = 0; j < cnt; j++) { for (auto &p : edges[i][j]) { dist[i][j] = dist[j][i] = min(dist[i][j], (int) p.size() + 1); } } } for (int k = 0; k < cnt; k++) { for (int i = 0; i < cnt; i++) { for (int j = 0; j < cnt; j++) { dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } } } vector<vector<vector<vector<long long>>>> edge_pref_sum(cnt, vector<vector<vector<long long>>>(cnt)); vector<vector<vector<vector<long long>>>> edge_pref_sum_by_pos(cnt, vector<vector<vector<long long>>>(cnt)); for (int i = 0; i < cnt; i++) { for (int j = 0; j < cnt; j++) { edge_pref_sum[i][j].resize(edges[i][j].size()); edge_pref_sum_by_pos[i][j].resize(edges[i][j].size()); for (int k = 0; k < (int) edges[i][j].size(); k++) { edge_pref_sum[i][j][k].resize(edges[i][j][k].size() + 1); edge_pref_sum_by_pos[i][j][k].resize(edges[i][j][k].size() + 1); for (int t = 0; t < (int) edges[i][j][k].size(); t++) { edge_pref_sum[i][j][k][t + 1] = edge_pref_sum[i][j][k][t] + edges[i][j][k][t]; edge_pref_sum_by_pos[i][j][k][t + 1] = edge_pref_sum_by_pos[i][j][k][t] + (long long) edges[i][j][k][t] * t; } } } } auto get = [&](int i, int j, int k, int from, int to, int coeff_from, int coeff_to) -> long long { if (from > to) { return 0; } assert(0 <= from && to <= (int) edges[i][j][k].size() - 1); long long ret = (edge_pref_sum[i][j][k][to + 1] - edge_pref_sum[i][j][k][from]) * coeff_from; if (coeff_from != coeff_to) { assert(abs(coeff_from - coeff_to) == to - from); long long other = edge_pref_sum_by_pos[i][j][k][to + 1] - edge_pref_sum_by_pos[i][j][k][from]; other -= (edge_pref_sum[i][j][k][to + 1] - edge_pref_sum[i][j][k][from]) * from; ret += other * (coeff_from < coeff_to ? 1 : -1); } return ret; }; for (int v = 0; v < cnt; v++) { long long w = weight[rev_id[v]]; for (int j = 0; j < cnt; j++) { ans += dist[v][j] * w * weight[rev_id[j]]; } for (int i = 0; i < cnt; i++) { for (int j = 0; j < cnt; j++) { for (int k = 0; k < (int) edges[i][j].size(); k++) { int x = dist[v][i]; int y = dist[v][j]; int cc = (y - x + (int) edges[i][j][k].size() + 1) / 2; cc = min(max(cc, 0), (int) edges[i][j][k].size()); ans += w * get(i, j, k, 0, cc - 1, x + 1, x + cc); ans += w * get(i, j, k, cc, (int) edges[i][j][k].size() - 1, y + ((int) edges[i][j][k].size() - cc), y + 1); } } } } vector<pair<int,int>> pairs; for (int i = 0; i < cnt; i++) { for (int j = 0; j < cnt; j++) { if (!edges[i][j].empty()) { pairs.emplace_back(i, j); } } } for (int ii = 0; ii < cnt; ii++) { for (int jj = 0; jj < cnt; jj++) { for (int kk = 0; kk < (int) edges[ii][jj].size(); kk++) { for (int tt = 0; tt < (int) edges[ii][jj][kk].size(); tt++) { long long w = edges[ii][jj][kk][tt]; for (int i = 0; i < cnt; i++) { int d1 = dist[ii][i] + tt + 1; int d2 = dist[jj][i] + (int) edges[ii][jj][kk].size() - tt; ans += w * weight[rev_id[i]] * min(d1, d2); } for (auto &p : pairs) { int i = p.first; int j = p.second; for (int k = 0; k < (int) edges[i][j].size(); k++) { if (i == ii && j == jj && k == kk) { int d1 = tt; int d2 = (int) edges[ii][jj][kk].size() - tt + dist[i][j] + 1; if (d1 <= d2) { ans += w * get(i, j, k, 0, tt, tt, 0); } else { int cut = (d1 - d2 + 1) / 2; ans += w * get(i, j, k, 0, cut - 1, d2, d2 + cut - 1); ans += w * get(i, j, k, cut, tt, tt - cut, 0); } int d3 = (int) edges[ii][jj][kk].size() - 1 - tt; int d4 = tt + 1 + dist[i][j] + 1; if (d3 <= d4) { ans += w * get(i, j, k, tt, (int) edges[i][j][k].size() - 1, 0, (int) edges[i][j][k].size() - 1 - tt); } else { int cut = (d3 - d4 + 1) / 2; ans += w * get(i, j, k, (int) edges[i][j][k].size() - cut, (int) edges[i][j][k].size() - 1, d4 + cut - 1, d4); ans += w * get(i, j, k, tt, (int) edges[i][j][k].size() - 1 - cut, 0, (int) edges[i][j][k].size() - 1 - cut - tt); } } else { int d1 = dist[ii][i] + tt + 1; int d2 = dist[jj][i] + (int) edges[ii][jj][kk].size() - tt; int d3 = dist[ii][j] + tt + 1; int d4 = dist[jj][j] + (int) edges[ii][jj][kk].size() - tt; int x = min(d1, d2); int y = min(d3, d4); int cc = (y - x + (int) edges[i][j][k].size() + 1) / 2; cc = min(max(cc, 0), (int) edges[i][j][k].size()); ans += w * get(i, j, k, 0, cc - 1, x + 1, x + cc); ans += w * get(i, j, k, cc, (int) edges[i][j][k].size() - 1, y + ((int) edges[i][j][k].size() - cc), y + 1); } } } } } } } assert(ans % 2 == 0); cout << ans / 2 << '\n'; return 0; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そして、参加チームの1つがソリューションとして提案したコードは次のとおりです。

C ++コード

 #include <bits/stdc++.h> #define ll long long #define ld long double using namespace std; int main() { int n,m; cin>>n>>m; int b[n+1][n+1]={}; int c[n+1][n+1]={}; int a1,b1; vector < vector <int> > v(n+1); vector <int> met(n+1); queue <int> q; for(int i=0;i<m;i++){ cin>>a1>>b1; v[a1].push_back(b1); v[b1].push_back(a1); c[a1][b1]=1; c[b1][a1]=1; } long long ans=0; for(int i=1;i<=n;i++){ q.push(i); met.clear(); met.resize(n+1); while(!q.empty()){ int frontt = q.front(); met[frontt]=1; for(int j=0;j<v[frontt].size();j++){ if(!met[v[frontt][j]]){ if(b[i][frontt]+1<b[i][v[frontt][j]] || b[i][v[frontt][j]]==0){ ans-=b[i][v[frontt][j]]; b[i][v[frontt][j]]=b[i][frontt]+1; ans+=b[i][v[frontt][j]]; } q.push(v[frontt][j]); met[v[frontt][j]]=1; } } q.pop(); } } cout<<ans/2; return 0; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ソリューションの分析は、当社のWebサイトの公式文書（ 3ページ ）に記載されています。

もう1つのタスクは「チェス」です。

エルマはチェスをすることを学び、ルークが水平または垂直に動くことをすでに知っています。 エルマの祖母は彼女に8x8のチェス盤を渡し、ルークをセルA1からH8にn回移動する方法を見つけるように頼みました。 この場合、図が停止するすべてのセルが異なる必要があります。 入力には、値n （2≤n≤63）が提供されます。 参加者は、エルマがルークを置いたすべての正方形をリストする必要があります。



以下は、審査員によって提案されたこの問題の解決策の例です。

Javaコード

 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.ArrayList; import java.util.StringTokenizer; public class easy_chess_va_wa { BufferedReader br; StringTokenizer st; PrintWriter out; public String nextToken() throws IOException { while (st == null || !st.hasMoreTokens()) { st = new StringTokenizer(br.readLine()); } return st.nextToken(); } public int nextInt() throws IOException { return Integer.parseInt(nextToken()); } public class Cell { int x, y; public Cell(int x, int y) { this.x = x; this.y = y; } public String toString() { return (char) ('a' + x) + "" + (y + 1); } } public void solve() throws IOException { int n = nextInt() + 1; ArrayList<Cell> cells = new ArrayList<>(); int k = Math.min(8 * 8, n + 4); if (k <= 8 * 7) { for (int i = 0; i < 7 && cells.size() < k; i++) { for (int j = 0; j < 8 && cells.size() < k; j++) { cells.add(new Cell(i % 2 == 0 ? j : 7 - j, i)); } } Cell last = cells.get(cells.size() - 1); if (last.x != 7) { cells.add(new Cell(last.x, 7)); } cells.add(new Cell(7, 7)); } else { for (int i = 0; i < 7; i++) { for (int j = 0; j < 8; j++) { cells.add(new Cell(i % 2 == 0 ? j : 7 - j, i)); } } for (int i = 0; i < 8; i++) { for (int j = 0; j < 2; j++) { cells.add(new Cell(i, i % 2 == 0 ? 7 - j : 6 + j)); } } Cell last = cells.get(cells.size() - 1); if (last.y != 7) { cells.add(new Cell(last.x, 7)); } cells.add(new Cell(7, 7)); } while (cells.size() > n) { cells.remove(1); } for (Cell cell : cells) { out.print(cell + " "); } } public void run() { try { br = new BufferedReader(new InputStreamReader(System.in)); out = new PrintWriter(System.out); solve(); out.close(); } catch (IOException e) { e.printStackTrace(); } } public static void main(String[] args) { new easy_chess_va_wa().run(); } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

タスクの完全なリストは、コンテストの公式ウェブサイトで公開されています。 そこで、ソリューションの詳細な分析で答えを見つけることができます 。 参加者が提案したコードは別のアーカイブにあります。ここでは、自動検証に使用されたすべてのソリューションとテストを見つけることができます。



オリンピアード開催中、参加者はソリューションをテストサーバーに転送し、テストサーバーは事前に準備されたテストセットのコードを「チェック」しました。 すべてのテストが正常に完了した場合、参加者はポイントを獲得しました。 それ以外の場合、チームはエラーフィードバックを受け取り、コードを調整できます。



ICPCの規則に従って、ほとんどのタスクを解決したチームが勝ちます。



複数の参加者が一度に同数のポイントを獲得した場合、順位表での位置はペナルティ時間によって決まります。 ペナルティ時間は、正しく解決された各問題に対して与えられ、競争の開始からコードがすべてのテストに合格するまでに経過した時間に等しい。 さらに、タスクの引き渡しに失敗するたびに、ペナルティに20分が加算されます（結果として問題を解決できる場合のみ）。 チームが問題の正しい解決策を提供しなかった場合、ペナルティは与えられません。





^{icpcnews / Flickr / CC BY /最終ICPC-2017}

ファイナリストは何を競いますか？

すでに述べたように、準決勝チャンピオン-15チーム-は、ポルトガル、ポルトの街に行き、そこでワールドカップと15,000ドルで戦います。 1位から4位までのチームには、金メダルが授与されます。 5位から8位で「終了」した参加者には銀メダルが、9位から12位には銅メダルが贈られます。 賞金も提供されます。



ITMOユニバーシティチームは7回（最後-2017年）ICPCのチャンピオンになりました。 これはまだ誰にも負けていない世界記録です。チャンピオンのタイトルの数で2位にいるのは同胞であり、サンクトペテルブルク州立大学、4カップ、そして最も近い外国のライバル、アメリカのスタンフォードとジャオトンの中国大学-3つの勝利。 7年連続で、世界の決勝戦はロシアのチームによって常に勝ち取られてきました。 ICPC 2019で、彼らがまともな結果を示すことを期待しましょう。



Habréで他に書いていることについて：

• ITMO大学ダイジェスト：新しい研究と国際プロジェクト
• ITMO大学の低レベルプログラミングコースの仕組み