きっかけ
たぶん阪大競プロ部RAINBOUに案内が来たのかな？それで参加することに。
参加したい人を募集すると4人だったので他に参加できる人を強い順に声をかけると6人になりました。
レート順に組んで、以下の2チームを作りました。
kotamanegi_ganbaruby
チームの写真はjag夏合宿懇親会のときにkowerkointと僕が持ってた黒澤ルビィを一緒に撮ったものです。そのときにチーム名も勝手に僕が付けました。
kotamanegi_daisuki_club
littlegirl112
shogo314
Daylight
早解きって観点だと、shinchan, hint908以外の4人の方が早解きタイプ。優勝はできないだろうと思ってゆるふわでいこうとしてたが、参加者を見ると案外黄色上位以上がいないかも？と思ったので優勝をとりにいくことに。東大の2チームとかkotamanegi_daisuki_clubにさえ勝てたら？とかこのときは思ってた。
本番
1区前
キーワードがEkiden!らしいのでこれを出力させるコードをkowerkointに用意させる。
1区
予定通りAのFA。しかし、Bで問題文読解に苦しんだとはいえあのkowerkointが1位になれないということは、上の東大はともかく謎のぼっち参加者が只者ではなさそう。
ググるとこれがでてきて、techful coding battleでkotamanegiに勝ってるということは橙以上と考えてよい。この時点で、優勝ではなくFAに狙いを定める。特に、後に優勝するこの人はDから解いてるっぽいので、2,3区も賞金理論値のためにDから解くと考え、僕とhint908はCのFAを狙うことに。
2区
とりあえず4問とも開いてDを読んだが、このタイプだとFAは取れないと思った。A, Bはちょっとめんどくさそう。やっぱりCを狙う。Cは全探索は必須っぽかったので書くしかないなぁと思って全探索を書いた。先に1位の人がFAだったものの、DもFAだったらしく、予定通り僕がFAとなった。
その後Dを考えて嘘を生やすこと2回。いったんA, Bを通してDに戻る。セグ木貼れば脳死でできそうなので貼った。全完。
ペナなし早解きなので全体的に何も考えず脳死で書けたのは良かったと思うがDの嘘に気づけるくらいは考えた方が良かった。
以下、回答したコード
#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(),(v).end()
#define pb(a) push_back(a)
#define rep(i, n) for(int i=0;i<n;i++)
#define foa(e, v) for(auto& e : v)
using ll = long long;
const ll MOD7 = 1000000007, MOD998 = 998244353, INF = (1LL << 60);
#define dout(a) cout<<fixed<<setprecision(10)<<a<<endl;
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
string s;
getline(cin, s);
vector<int> cnt(26, 0);
foa(e, s) {
int num = e - 'A';
if(0 <= num and num < 26) cnt[num] ++;
num = e - 'a';
if(0 <= num and num < 26) cnt[num] ++;
}
cout << (count(all(cnt), 0) ? "No" : "Yes") << endl;
return 0;
}
B
#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(),(v).end()
#define pb(a) push_back(a)
#define rep(i, n) for(int i=0;i<n;i++)
#define foa(e, v) for(auto& e : v)
using ll = long long;
const ll MOD7 = 1000000007, MOD998 = 998244353, INF = (1LL << 60);
#define dout(a) cout<<fixed<<setprecision(10)<<a<<endl;
bool calc(int x) {
int h = x / 60;
int m = x % 60;
if(h == m) return true;
if(m == 0 or h == 0) return false;
string s = to_string(h);
string t = to_string(m);
reverse(all(s));
reverse(all(t));
while(s.back() == '0') s.pop_back();
while(t.back() == '0') t.pop_back();
s += t;
int n = s.length();
for(int i = 0; i < n - 1; i ++) if(s[i] != s[i + 1]) return false;
return true;
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int a, b, c, d;
cin >> a >> b >> c >> d;
int ans = 0;
for(int i = a * 60 + b; i <= c * 60 + d; i ++) {
if(calc(i)) ans ++;
}
cout << ans << endl;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(),(v).end()
#define pb(a) push_back(a)
#define rep(i, n) for(int i=0;i<n;i++)
#define foa(e, v) for(auto& e : v)
using ll = long long;
const ll MOD7 = 1000000007, MOD998 = 998244353, INF = (1LL << 60);
#define dout(a) cout<<fixed<<setprecision(10)<<a<<endl;
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int m;
cin >> m;
vector<vector<int>> v;
auto dfs = [&](auto dfs, vector<int> vec, int now) -> void {
if(now == 1) return;
if(now == 0) {
v.push_back(vec);
return;
}
for(int i = 1; i <= now; i ++) {
vec.pb(i);
dfs(dfs, vec, now - i);
vec.pop_back();
}
};
dfs(dfs, vector<int> (), m);
sort(all(v));
foa(e, v) {
foa(e1, e) cout << e1 << " ";
cout << endl;
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(),(v).end()
#define pb(a) push_back(a)
#define rep(i, n) for(int i=0;i<n;i++)
#define foa(e, v) for(auto& e : v)
using ll = long long;
const ll MOD7 = 1000000007, MOD998 = 998244353, INF = (1LL << 60);
#define dout(a) cout<<fixed<<setprecision(10)<<a<<endl;
struct SegmentTree {
private:
ll n;
vector<ll> node;
ll ID = INF;
inline ll func(ll a, ll b){return min(a, b);}
public:
SegmentTree(vector<ll> v) {
int sz = v.size();
n = 1; while(n < sz) n *= 2;
node.resize(2*n-1, ID);
for(int i=0; i<sz; i++) node[i+n-1] = v[i];
for(int i=n-2; i>=0; i--) node[i] = func(node[2*i+1], node[2*i+2]);
}
void update(ll x, ll val) {
x += (n - 1);
node[x] = val;
while(x > 0) {
x = (x - 1) / 2;
node[x] = func(node[2*x+1], node[2*x+2]);
}
}
ll get(ll a, ll b, ll k=0, ll l=0, ll r=-1) {
if(r < 0) r = n;
if(r <= a || b <= l) return ID;
if(a <= l && r <= b) return node[k];
ll vl = get(a, b, 2*k+1, l, (l+r)/2);
ll vr = get(a, b, 2*k+2, (l+r)/2, r);
return func(vl, vr);
}
};
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int n;
cin >> n;
SegmentTree seg(vector<ll> (300000, INF));
rep(i, n) {
ll a, b;
cin >> a >> b;
seg.update(a, min(seg.get(a, a + 1), a + b));
}
int ans = 0;
ll now = 0;
while(1) {
ll num = seg.get(now, 300000);
if(num == INF) break;
now = num;
ans ++;
}
cout << ans << endl;
return 0;
}
Dの解法はいろいろあって、O(max(T)N), O(N), O(NlogN)などがある。セグ木を使ったO(NlogN)が一番簡単に書けると思ったのでそうした。区間スケジューリングによるO(NlogN)、後ろから累積minを持つO(N)、max(T)が小さいことを利用したO(max(T)N)とか。
閉会式
去年今年ICPCでチームを組んだkowerkoint, daylight, hint908がしゃべったのに僕だけマイク不調でしゃべれてないのもあれなので3位の代表としてしゃべることにした。
↓ミュートになってない人がいて謎の電車音で不機嫌になりながらしゃべったshinchan。
www.youtube.com
とりあえずは、個人で3000円もらえたので嬉しいです。マイクラで走ってる姿とか面白かったので是非来年もやってほしいです。ありがとうございました！！
