予選に落ちた後悔を引きずりながら先輩と参加。
4AC+0WAでした。
予選は6AC+4WA。僕の緊張が極限に達して自滅しました。
1→5→2→3の順でAC。3のAC時刻が17:20:09とかなっていたので更新されないじゃんとなって萎えました。
ちょっと本番と変えてるけど、ソース。
テンプレート
用意してなかったので先輩のテンプレートをコピペしました。若干省略。
#include<iostream>
#include<string>
#include<bitset>
#include<cctype>
#include<cstdlib>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<sstream>
#include<iterator>
#include<algorithm>
#include<complex>
using namespace std;
// structure
typedef long long ll;
typedef pair < int , int > Pi;
typedef pair < int , Pi > Pii;
#define INF (1 << 28)
#define SQR(x) ((x)*(x))
//repetition
#define reps(i,j,n) for(int i = j ; i < n ; ++i)
#define rep(i, n) reps(i,0,n)
#define EACH(i,c) for(__typeof((c).begin()) ;i=(c).begin(); i!=(c).end(); ++i)
// containar
#define ALL(v) (v).begin(), (v).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define sz(z) (int)((z).size())
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define UNQ(s) {sort(ALL(s));(s).erase(unique(ALL(s)),(s).end());}
#define fr first
#define sc second
// PROG START
int main(){
}
問題1.テニス(6点)
パッと見た感じ再帰しか浮かばなかったので再帰で解きました。
答えはvector
で持たせました。
int A,B;
vector<string> ans;
void solve(int a,int b,string t){
if(a == A && b == B){
ans.pb(t);
return;
}
if(a > 6 || b > 6) return;
if(a == 5 && b == 5) return;
if((a == 5 && b < 4) || (a < 4 && b == 5)) return;
if((a == 6 && b == 4) || (a == 4 && b== 6)) return;
solve(a+1,b,t+"A");
solve(a,b+1,t+"B");
}
int main(){
cin >> A >> B;
solve(0,0,"");
sort(ALL(ans));
rep(i,ans.size()) cout << ans[i] << endl;
}
問題2.親方の給料計算(6点)
超難問。O(N*M*L) = O(10^10) で逝くじゃんと思って怖くて触れにくかった問題です。
TLE覚悟でソースを出してみたらACして,ファ??ってなりました。
正答率10%切ってて,下のソースを早くしようとしたけど,ちょっと察せなかった。
int main(){
int N, M, a, b, c, L;
cin >> N >> M;
vector<Pi> vc[N];
int cost[M];
while(cin >> a >> b >> c , a + b + c){
vc[a-1].push_back(Pi(b-1,c));
}
cin >> L;
while(L--){
rep(i,M) cin >> cost[i];
rep(i,N){
int sum = 0;
rep(j,vc[i].size())
sum += cost[vc[i][j].fr] * vc[i][j].sc;
cout << (i ? " " : "") << sum;
}
cout << endl;
}
}
問題3.塵劫記(6点)
みんなACしてて「コレ簡単？(困惑)」になっていた。多倍長乗算。
変換する部分は事前に先輩が実装してくれた。凄い。
あとは多倍長,書きたくなくて書かなかったが、仕方なくやったらすぐ実装できて良かった。
string lis[] = {
"","Man","Oku","Cho","Kei","Gai","Jo","Jou","Ko","Kan",
"Sei","Sai","Gok","Ggs","Asg","Nyt","Fks","Mts",
};
string KAKEZAN(string a,string b){
int ans[100] = {};
string rec;
reverse(ALL(a));
reverse(ALL(b));
rep(i,a.size()) rep(j,b.size()){
ans[i+j] += (a[i] - '0') * (b[j] - '0');
}
rep(i,99){
ans[i+1] += ans[i] / 10;
rec += (ans[i] % 10) + '0';
}
reverse(ALL(rec));
int cnt = 0;
while(rec[cnt] == '0') cnt++;
return rec.substr(cnt);
}
void ZIN(string s){
vector<string> v;
string ret;
reverse(ALL(s));
for(int i = 0 ; i < (int)s.size() ; i += 4){
string cut = s.substr(i,min(4,sz(s)-i));
string Class = lis[i/4];
reverse(ALL(cut));
int pos = -1;
rep(j,cut.size()){
if(cut[j] != '0'){ pos = j; break; };
}
if(pos == -1) continue;
string in;
reps(j,pos,cut.size()) in += cut[j];
v.pb(in+Class);
}
reverse(ALL(v));
rep(i,v.size()) cout << v[i];
cout << endl;
}
int main(){
string a;
int b;
while(cin >> a >> b , a != "0" || b != 0){
string ret = "1";
rep(i,b) ret = KAKEZAN(ret,a);
ZIN(ret);
}
}
問題5.無限急行(8点)
先輩が他の問題を解読しているうちに僕が実装。
一発ACするとは思っていなかった。
たくさん関数分けて,たくさんビットシフトすればいいんじゃね的な考え方で
バグってもいいので適当に書いた。十分このソースも汚いけど、本番はそれ以上に汚かった。
int s, d;
bool check(int train,int n){
if(!train) return true;
int shift = pow(2,train);
if(n + shift > d) return false;
rep(i,32){
if(abs(n) & (1<<i)){
if(i && (1<<i) % shift == 0) return true;
else return false;
}
}
return true;
}
int cnt(int no){
int i = 0;
while(check(i,no)) i++;
return i - 1;
}
int solve(int now, int cost){
if(now == d) return cost;
int train = cnt(now);
if(now + pow(2,train) <= d){
return solve(now+pow(2,train),cost+1);
}else{
return solve(now,cost+1);
}
}
int main(){
int N;
cin >> N;
while(N--){
cin >> s >> d;
cout << solve(s,0) << endl;
}
}
5問目と3問目解けた高揚感で4問目サボってしまったのが反省点。
ソートして再帰すればHappyそうなので今度やって挙げます。
11/12追記
、と思ったけど先輩が解いてくれてたのでやめました。
http://hayashiya.hatenablog.com/entry/2013/11/12/205702
