OUPC β参加記
OUPC2020（@rainbou_oupc）の予行練習としてOUPC βをべるさん（@BELL_kyopro）と解きました！！！！！！！！！！！
コンテスト前
OUPC2020のチーム参加条件が1200未満は人数無制限・コーディング台数制限なしだったので，べるさん，ふねらるさん（@FUN_era1）と緑コーダー3人でチームを組むことにしました
初めてのチーム戦なのでどこかで練習したいな～と思っていたところ，OUPCのβ版が以前開催されていたことがわかったので，時間の都合があったべるさんと参加することにしました
- A問題：べる，B問題：クミン，C以降は相談しつつ
- 連絡はdiscordで通話しながら
くらいだけを決めてゆるゆる始めました
コンテスト中
A問題 Grundy Number （200）
べるさんが典型ぽいとのことでお任せしました！
Grundy数に馴染みがあればすぐ思いつけそうです
#include <bits/stdc++.h> #define ll long long #define rep(i, n) for(ll i = 0; i < n; ++i) using namespace std; signed main(){ int n; cin >> n; vector<int> a(110); rep(i,n){ int x; cin >> x; a[x]++; } rep(i,110){ if(a[i] == 0){ cout << i << endl; return 0; } } return 0; }
B問題 Doubling Step （300）
タイトルからダブリング，問題文からdpしろという匂いがプンプンします
少し考えるとダブリングがいらないことに気づきます（は？）
しっかりACして1完という事態が避けられて安堵
#include <bits/stdc++.h> #define ll long long #define rep(i, n) for(ll i = 0; i < n; ++i) #define rep2(i, a, b) for(ll i = a; i <= b; ++i) using namespace std; signed main(){ int n; cin >> n; vector<int> dp(n+1); dp[1] = 1; rep2(i,1,n){ ll cur = i; ll two = 1; while(cur+two<=n){ dp[cur+two] += dp[cur]; dp[cur+two] %= MOD; two *= 2; } } cout << dp[n] << endl; return 0; }
C問題 Power Number （500）
先にCを見てくれていたべるさんから難しそうとの情報を得ます
Bを通してから問題文を読むと，なるほどムズそ～というお気持ちに
（原石の種類）≦500，（原石の長さ）≦10と制約が小さいので，bit全探索でつくれる文字列が全列挙できそうです（偉いポイント①）
しばらくしてから，文字列Sのi文字目までつくったときのスピリチュアル度の最大値をdp[i]としてできそ～ということにも気づきます（偉いポイント②）
つくった文字列とスピリチュアル度の最大値をmapでもって，文字列の最初の文字でグループ分けしてからごちゃごちゃするとサンプルが合います
ここで勝ちを確信しました
提出
対戦ありがとうございました
int型をlong longに直すと，なんとWAが消えます（オーバーフローでした）
残ったTLEの処理を頭を悩ませていると，最初の文字で場合分けしなくても，10文字分先読みしてdpを更新すればよいと気づきます（べるさんも気づいてたらしい）
一致している文字列だけ見ればいいことになかなか気づきませんでした......
無事提出してACです！！！
#include <bits/stdc++.h> #define ll long long #define rep(i, n) for(ll i = 0; i < n; ++i) #define rep2(i, a, b) for(ll i = a; i <= b; ++i) using namespace std; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } const int MOD=998244353; const ll INF=1e18; signed main(){ ll n, m, b; cin >> n >> m >> b; string s; cin >> s; vector<string> a(m); vector<ll> v(m); rep(i,m) cin >> a[i] >> v[i]; map<string,ll>mp; rep(i,m){ string t = a[i]; ll val = v[i]; ll ts = t.size(); rep(bit, 1<<ts){ string str = ""; rep(j,ts){ if(bit>>j &1ll){ str += t[j]; } } ll res = __builtin_popcount(bit); ll spir = val-(ts-res)*b; if(res == 0)continue; if(mp[str])chmax(mp[str],spir); else mp[str] = spir; } } vector<ll> dp(n+1,-INF); dp[0] = 0; rep(i,n){ rep2(j,1,10){ if(i+j-1>n-1)continue; string u = s.substr(i,j); ll us = u.size(); if(mp[u] && i+us<=n){ chmax(dp[i+us], dp[i]+mp[u]); } } } cout << dp[n] << endl; return 0; }
コンテスト後
というわけで120分でABCの3完でした！！！！
緑2人にしては健闘したのではないでしょうか？？？？
べるさんにはAをノーペナできっちり通してもらったり，Cの考察の相談にのってもらったりと様々助けてもらいました，大感謝
個人としてはdpをちゃんと通せるようになったことに成長を感じますが，ペナが多くて反省です
OUPC2020本番の目標
「「「「「「「「「「「打倒緑無限人チーム」」」」」」」」」」」
本番もがんばります
