自己紹介
明石高専の4年生のしんちゃんと申します。競プロ歴はあと数ヶ月で3年になります。現在AtCoderのレートは1689です。
以前から、情報オリンピック、数学オリンピック、パソコン甲子園、高専プロコン(課題部門)に参加したりしてました。
ですが高専プロコンを除いてオンサイトには進めたことがありません。
オセロ対戦相手募集中
概要
2020/11/06(金)のICPC国内予選に参加しました。
チームappearedはエカスドクィナ・おーじ・しんちゃんです。
結果はABCDの4完で31位でした!!
わりと余裕をもって予選通過できました。
私にとっては始めてのオンサイトです！
前日まで
atcoder青になってからしばらく競プロはおやすみしていましたが、応用情報が終わって2週ほど前から再開しました。
(実際にはコンテストのみでてたりはしてました。)
エカスドに言われて、AOJ-ICPCを埋める作業に移りました。
国内予選の350ぐらいまではけっこう埋めました。
前々日にバチャとかやった感じから、3完はいけるなと自信になりました。
また、構文解析というのはICPC特有なのかなと思いまして、AOJ-ICPCで度々遭遇して、1つ1つの実装が重く、少しめんどくさかったです。
しかし、AOJ-ICPCをやっていくうちに得意になっていたらしく、自分の書き方の"型"ができ、前々日のバチャや今回の本番のD問題でも活躍できました。
さて、前々日にバチャをやったということなんですが、さすがに3人現地に集まってのチーム練を1回ぐらいやっておいた方がいいと思い、放課後に行いました。
ICPC2019の国内予選を用いました。結果は3完で、Dは通せなかったもののボーダーよりは上でした。夜にものいみさんが立てたバチャに、おーじと2人で参加し、20分3完でこれもわりといい結果でした。
ただ、Dを通せばほぼ確実なので、Dをなんとかして通したいという想いは3人ともあったのではないでしょうか。
前日はいつも通り精進して緊張しながら寝ました。
当日
リハーサルも行い、。
14:40~16:10の4限に課題研究という教科があるのですが、研究室内のクラスメート4人のうち2人がICPCに参加するため日を変えてくれました!!担当教員感謝!!
糖分をしっかり接種して会場入り、メールの内容印刷したりして始まり…
と思いきやデータベースの破損がどうしたこうしたと。
電話をかけるかどうか戸惑いながらも、待っていると問題を見れるようになりました。
本番
予定通りおーじはAから、私はC、エカスドはDを見ました。
おーじがサラッと2完してくれ、私も少ししてCをACしました。
Dは難しそうでした。エカスドに「構文解析と愚直解実装して」と言われて実装。
エカスドも全探索パートの考察と実装ができて、僕のコードとの修正結合とか確認を行ってAC。
正直この時点で「よっしゃぁ横浜!!」って言ってました。
多分3人とも予選通過を確信していたと思います。(私は3完の時点で確信してましたけどね)
まぁ残りの時間は椅子温めたりだべったりって感じでしたね。
3人でE見て無理だと判断し、F見て考察したものの嘘だとわかり、多分そのあたりでみんな集中はきれたと思います。
暇だったので、GとかHにペナコードを提出したりして遊んでました。
楽しかったです。
結果としても31位で予選通過、それに3人ともいい感じに活躍できてよかったです。
僕とおーじは独り言言いながらやるタイプなのもあり、競技中は2人で関係ないこととかもしゃべって笑いながらやってました。
Fのおーじの嘘解法が発覚してからは3人とも笑いモードで終了しました。
チームで楽しめたというのが一番良かった点です。
反省もまったくないですね。
ソースコード
まずはC問題で実際に書いたコードです。
#include <bits/stdc++.h> #define be(v) (v).begin(),(v).end() #define pb(q) push_back(q) typedef long long ll; using namespace std; const ll mod=1000000007, INF=(1LL<<60); #define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl; vector<ll> calc(ll n){ vector<ll> v; for(ll i=1;i*i<=n;i++) if(n % i == 0){ v.pb(i); if(i * i != n) v.pb(n / i); } sort(be(v)); return v; } int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(false); ll n; while(1){ cin >> n; if(n == 0) return 0; ll ans = INF; vector<ll> v; v = calc(n); for(ll i : v){ ll m = n / i; if(i >= ans) continue; for(ll j : v){ if(i > j) continue; if(m % j) continue; ans = min(ans, i + j + m / j); } } cout << ans << endl; } return 0; }
次に、D問題で書いた愚直解です。
#include <bits/stdc++.h> #define be(v) (v).begin(),(v).end() #define pb(q) push_back(q) typedef long long ll; using namespace std; const ll mod=1000000007, INF=(1LL<<60); #define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl; pair<char, int> dfs(string &s, int nowi, vector<int> &v, map<char, int> &mp){ if(s[nowi] == '(') { char ret; nowi++; pair<char, int> a = dfs(s, nowi, v, mp); nowi = a.second + 1; pair<char, int> b = dfs(s, nowi + 1, v, mp); if(s[nowi] == '<'){ if(v[mp[a.first]] < v[mp[b.first]]) ret = a.first; else ret = b.first; }else{ if(v[mp[a.first]] > v[mp[b.first]]) ret = a.first; else ret = b.first; } nowi = b.second + 1; return {ret, nowi}; } return {s[nowi], nowi}; } int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(false); int n; while(1){ cin >> n; if(n == 0) return 0; string s, t, r; vector<int> v; cin >> r >> s >> t; map<char, int> mp; for(int i=0;i<n;i++){ v.pb(i); mp[r[i]] = i; } int ans = 0; do{ if(dfs(s, 0, v, mp).first == dfs(t, 0, v, mp).first) ans++; }while(next_permutation(be(v))); cout << ans << endl; } return 0; }
メンバーについて
私は3人の中では構築やパズルなどが得意なのです。
ICPCでは見せ場が少ないと思ったのですが、構文解析が得意だとわかり、そこで見せ場を作れました。
おーじは早解きやdpは僕と比べものにならないほど得意で、PCKでもチームを組みました。
今回も、A, Bをペナなく早めに通せてよくやってくれたと思います。
ただしコードはマクロ多すぎて読めない。
エカスドは言うまでもないですが、一番強いです。それに頼りになります。
正直ICPCはエカスド次第だと思ってました。僕とおーじがどれだけエカスドの手助けをできるかというのが重要だと思ってました。
しかし、前々日のバチャで、おーじとの2人でも予選通過できる実力があるとわかり、エカスドに大きな負担をかけなくてすむことにもなりました。
エカスドが担当したDも構文解析パートを私が担当したりと、チーム戦の特徴をフルに活用できたと思います。
全探索パートを考察できたのはさすがとしか言いようがない。
ただしコードは言語仕様にのっとり、正しく書けすぎていてかっこよすぎて慣れなくて読めない。
全員AtCoderは現在青(エカスドはhighest黄)で、バランスもわりとよかったです。
チームの2人には感謝しかな…(これは本選に置いておこう)
ところで
最近運使いすぎて応用情報落ちそう
2021/01/18追記
↑落ちた
