ゆるふわ競技プログラミングオンサイト at FORCIA #2 ゴリラの挑戦状 参加記
ゆるふわオンサイトに参加してきました。オンサイトイベント参加はほぼ初めてです(ICPC予選はほぼコード打ってない&懇親会とかなかったので)。
会場到着〜コンテスト開始
会場に到着すると競プロTシャツとか着てる人いたのでみんなガチプロに見えた。実際その場にいた人みんなガチプロ。
コンテスト結果
問題ページ
A問題
本田のじゃんけん。
B問題
コンパイルエラーになっ他のでHackerRankわからんなぁ、と思ってたらfor構文のi++を抜かしてました。人のせいにするのは良くないね。気を取り直して提出したらWA。テストケース試すのに手こずって時間ロスしましたがやり方に気づいたので入れてみると答えがマイナスに。入力が大文字なのに-'a'してた。緑Coderだからしゃーない。
C問題
N!って思ったのでN!したら通りました。
D問題
実はサンドイッチを食べたことがあるのでパンとパンの間に指を挟めば一つのサンドイッチを取り出せることを知ってた。
E問題
クエリがソート済みだったことに気づかずに二分探索した。lower_boundだと思ったらupper_boundだった。二部探索大好きとコメントアウトしたらHackerRankはコメントアウトでも日本語含めちゃいけないらしいのでそこで若干タイムロスした。
F問題
これは本当に二分探索する問題だった。前問と似てたのでupper_boundしたらlower_boundだった。
G問題
重なる範囲は裏返さない→2回裏返す、と読み替えて二次元累積和。はじめての二次元累積和だったけどひとりでできた。えらい。
H問題
対戦系は苦手だし問題ヤバそうだったのでそっと閉じた。実はここが今日一番の良い選択。
I問題
K人全員に全てのピノを最低1個ずつ報酬として渡す必要があるので箱は(K-1)/7+1個必要。まず全員にピノ3個ずつ配ったことにして、問題をシンプルにする。次にそれぞれの味について報酬が安い順に人をソートする。(安い順に人を消していくので速くなるように降順でソートして後ろを見る)。配ったピノの個数を変数3つで管理しておく。
最後に、K人雇えるまで以下を繰り返す。箱を増やさずにバニラ好きで報酬一番安い人を雇えるなら雇う。チョコ、アーモンドも同様。誰も雇えなかったら箱を増やす。本当は箱数X個でK人雇えるか、という問題のXを二分探索で探すのが想定解らしいけど全員がピノ100個欲しがっても一人当たり箱を追加するのを15回繰り返せば良いので十分間に合った。
この問題は正直説明が難しかったのでコード貼った。
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int N,K;
cin >> N >> K;
vector<int> v,a,c;
int nv=K;
int na=K;
int nc=K;
int bx=(K-1)/7+1;
for(int i=0;i<N;i++){
int x,y,z;
cin >> x >> y >> z;
if(x==1 && y==1 && z==1)K--;
if(x!=1)v.push_back(x-1);
if(y!=1)a.push_back(y-1);
if(z!=1)c.push_back(z-1);
}
sort(v.begin(),v.end());
reverse(v.begin(),v.end());
sort(a.begin(),a.end());
reverse(a.begin(),a.end());
sort(c.begin(),c.end());
reverse(c.begin(),c.end());
while(K>0){
if(v.size() && v.back()+nv<=bx*10){
nv+=v.back();
v.pop_back();
K--;
}
else if(a.size() && a.back()+na<=bx*7){
na+=a.back();
a.pop_back();
K--;
}
else if(c.size() && c.back()+nc<=bx*7){
nc+=c.back();
c.pop_back();
K--;
}
else bx++;
}
cout << bx << endl;
return 0;
}
問題J,K,L
見たけど残り15分じゃ解けなさそうだったのでパス。結果8完。
表彰
総合優勝(全完)と各色1位が表彰された。緑は僕以外数人しかいなかったので僕も表彰されることができた。うれしい。僕が解かなかったH問題を解いてI問題はACまでいかなかった人も結構いたので全体順位も割とよかった。
懇親会
ピザ美味しかった。ABCのGolfはヤバいとか競プロ関連で盛り上がって面白かった。あと割と社会人もいるんだなぁという印象。あとはホワイトボードを使ったアンケートとかがあった。