ICPC2024 国内予選参加記 uruzunyaa視点

ウルズニャー

2024年7月6日 20:44

東京通信大学から、チームUMAとしてICPCに参加させて頂きました。

我々の大学、通信制大学から5チームの出場という割と偉業？を成し遂げました。

チームメンバーマッチング周りとか、その事についても書きたい所ですが別記事にして、この記事では当日のコンテストについて、ウルズニャー視点で振り返って行きます。

正直ほとんどの時間、E問題を解いていたので、Eの話ばっかりになりそうですが・・・・ｗ

チーム紹介

全員の通商の頭文字からチーム名はUMAに決まりました。
ウルズ、真鍋、Aさん　が通称の名前になります。

uruzunyaa(U)

3年生、競プロ歴1年ちょい、2度目のICPC。
AtCoder：水
役割：数学、DP、天才考察系

manabeai(M)

4年生、競プロ歴1年ちょい、ICPC初出場
AtCoder：茶
役割：構文解析、文字列、早解き

HackberryA3(A)

3年生、競プロ歴半年、ICPC初出場
AtCoder：緑
役割：コーディング監視、図示

当日開始前

後悔したくなかったので、先生方に色々無理言ったりしながら、自分の中で最高の環境を準備出来ました。

「これでも予選通過出来なかったらもうしょうがない」と思えていたので、開始前は落ち着いていました。

#TOU #ICPC
#ICPC2024
TOUの新宿校舎行って明日の国内予選の準備してきた

普段大学行かないのでプリンタの設定とかに案外手間取った

そして5チームで2教室占有させて貰える最高の環境にマジ感謝

先生方ホントにありがとうございます

私はチームUMAとして出場します！

観戦方法は後でまとめますw pic.twitter.com/clV6AfMhOO
— ウルズニャー＠ICPCありがとうございました。 (@uruzunyaa) July 4, 2024

開始直後

10分位すると先生から全問題を印刷した紙が届く手筈になっていたので、BとCのみを印刷します。

Aは真鍋さん、BはAさん(こう書くと頭おかしくなりそうｗ)、Cは私uruzunyaaが解く手筈になっています。

A問題

問題すら知らぬまま、真鍋さんに丸投げします。
事前の作戦通り、4:23AC。

最高のスタートを切ります。

B問題

こちらも問題すら知らぬまま、Aさんに丸投げします。
少し実装に詰まったそうですが、15:21AC。

早解きよりも問題数をでの突破を狙っている我々にとって、かなり順調です。

C問題

開始2分後頃、印刷が終わり、問題を読み始めます。

座標を四角形に直してみると、「四角形のマス目上で、上下左右及び異符号方向への斜め移動のみを使い、0,0座標から目的地への最小の移動回数を求めよ」という問題へ言い換え出来る事に気付きます。

という事はつまり「同符号なら絶対値の合計、異符号なら絶対値の最大値」という事になります。

10分掛からず考察が終わり、Bの実装が終わるのを待ち、コーディングし始めます。

考察ここまで出来ておいて、コーディングに10分も掛けてしまいごめんなさいという気持ちに。

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#include<atcoder/all>
//#include<boost/multiprecision/cpp_int.hpp>
using namespace std;
#ifdef DEBUG
#include "cpp-dump/dump.hpp"
#define dump(...) cpp_dump(__VA_ARGS__)
#else
#define dump(...)
#endif
#define rep(i,n) for (long long i=0;i<n;i++)
#define loop(i,m,n) for(long long i=m;i<=n;i++)
#define ll long long
//#define bbi boost::multiprecision::cpp_int
#define vl vector<long long>
#define vvl vector<vector<long long>>
#define vdbg(a) rep(ii,a.size()){cout<<a[ii]<<" ";}cout<<endl;
#define vvdbg(a) rep(ii,a.size()){rep(jj,a[ii].size()){cout<<a[ii][jj]<<" ";}cout<<endl;}
#define setdbg(a) for(const auto & ii:a){cout<<ii<<" ";}cout<<endl;
#define inf 4000000000000000000LL
#define mod 998244353LL
//#define mod 1000000007LL

ll solve(){
	ll x,y;
	cin>>x>>y;
	ll ans;
	if((x<0&&y>0)||(x>0&&y<0)){
		ans=max(abs(x),abs(y));
	}else{
		ans=abs(x)+abs(y);
	}
	cout<<ans<<endl;
	return 0;
}

int main(){
	ll n;
	cin>>n;
	rep(i,n){
		solve();
	}
	return 0;
}

何はともあれ、25:53AC。

この時点で順位表を確認すると60位前後に。
かなり良い状態です。

D問題

Aを終えた真鍋さん、Cの考察を終えてPC空き待ち中のuruzunyaaが考察をします。

私が障害物座標の上限が小さい事に気付くと、真鍋さんから「同じ状態になったら永遠に繰り返すので、無限ループの検出をしよう」という提案が。

そして私から、「逆に範囲外に出たら無限に同じ方向に進むのでそうなった場合は残りを全て処理」という提案をすると、「あり得る状態は4方向×100×100なので4万程度」という事が分かり、解法が正しい事を確信します。

ここで私はCの実装へ行き、実装が重い事を考え、バグ地獄対策にAさんに真鍋さんのサポートをお願いします。

しかし色々バグが起こり、2:01:38まで掛かったものの、2人が通し切ってくれました。

E問題

C問を終えた私が、順位表情報からEが解けるかがボーダーになると予想し、問題を読んでみます。

すると天才構築系の匂いがプンプンしてきます。

しかしAtcoderではABCよりもARCを得意とする私にとって、望むべき天才発想系の問題です。「私はかなり良い問題を引いた！」と思います。

1時間位ホワイトボードにあれこれ書いて考察し、解法が降りてきます。この時残り1時間半程度だったと思います。

この時に分かっていたのは以下の3点です。

右端と左端の数字が一緒なら、最外周のみで構築可能。
右端と左端の数字が異なる場合、「1 ? 2 ? 1 ? 2」のような、形でなければ構築不可能である。
条件2に当てはまらない時、この1や2の後ろに隠すように、十字架で構築する事で条件達成可能である事。

PCが空くまでの間に、index処理の式をメモしておき、味方がDを通してくれたので実装を行います。

2時間10分程経過し、Eが書けたので提出しますがWrongAnswer、不正解との事。

正しい構築方法は以下のような形でしたが、2個目の画像のような、綺麗な十字の形の構築の嘘解法を書いてしまいまっていました。

当然、逆順にしても場所が一致する例の方が珍しいわけですが、考察時に左右対称な例(1,6,5,2,1,4,3,2)や(1,6,2,5,4,1,3,2)他にも(2,7,1,7,2,7,1)等、重要な部分が全て左右対称例でテストしてしまい、反例を見つけられませんでした。

「構築時、丸々1列1行ではダメなんじゃ・・・？」と終了5分前にAさんから意見が出ますが、検証する時間なく我々の横浜の夢は潰えました。

まとめ

結果的に最後のAさんの意見は正しかったため「後少しだった！」となりすごく悔しいです。
特に真鍋さんは卒業のため、来年リベンジする事が出来ないのが・・・・・

正直問題セットの相性も悪くなかったと思いますし、事前の作戦も大方上手くは行きました。

それでも、DとEの2問を通し切る、チームの底力が後一歩及ばずという所でしょう。

直前にあった模擬コンテストでは私がC問題を誤読して2完とかやらかしてましたので、本番では実力を出せた所は良かったと思います。

アジア大会の英語問題対策とかは無くなってしまったので、何か競プロ企画はブチ上げたいと思っています。(可能ならオンサイトコンテスト開きたいかも)

来年に向けて

この1年ICPCを見据えて競プロをして来ましたが、競技プログラミングのおかげで素晴らしい出会いをたくさんしています。

筧先生（東京通信大学の名誉教授）が去年ICPC勧誘の声掛けをしてくれた所から全てが始まりました。

本当に感謝すると共に、来年こそはアジア大会進出の報告が出来るように頑張りたいと思います。

お読み頂きありがとうございました！

ここまでお読み頂きありがとうございました！

明日は学内で競プロ布教活動した結果、通信制大学から5チーム出場という偉業を起こすまでの経緯を書いて行こうと思います。

布教の参考にして頂ければ幸いです！

ICPC2024 国内予選 参加記 uruzunyaa視点