昨日の17時からのCodeforcesに参加してきました。
日記書くの遅い？小さいことは気にするな！
結果は・・・
2126点 30位/796
A～Cの３問しか解けず、しかも他の参加者に比べて遅い上にAを再提出したのですが、8本のHackが効いたようです。
ではコードを晒していきましょう。
A. Robot Bicorn Attack
文字列の長さは最大30文字！区切りは2箇所！これは全探索！！→書く→提出
…Σ(ﾟДﾟ|||)しまった！このままではオーバーフローする！→再提出
► スポイラーを表示
CODE:
#include
#include
int main(void) {
char input[50];
int length;
int i,j,k,l;
long long n1,n2,n3,now,max;
scanf("%s",input);
length=strlen(input);
max=-1;
for(i=0;i1000000 || n2>1000000 || n3>1000000)continue;
now=n1+n2+n3;
if(now>max)max=now;
}
}
}
printf("%I64d\n",max);
return 0;
}
結果：318点 Aを再提出とか痛いです。
B. Plane of Tanks: Pro
仕様が与えられているので実装するだけ。でもどうやって実装するか…
→普通に整数で計算したら通りました
► スポイラーを表示
CODE:
#include
#include
#include
#include
using namespace std;
struct player_t {
string name;
int score;
int got_more;
int got_less;
string category;
};
//syo-zyun
int qsort_comp(const void* x,const void* y) {
const player_t* a=(const player_t*)x;
const player_t* b=(const player_t*)y;
if((a->score)>(b->score))return 1;
if((a->score)score))return -1;
return 0;
}
int player_num;
player_t players[1000];
int main(void) {
map scores;
char name[12];
string name2;
int score;
int n,i;
int count;
scanf("%d",&n);
for(i=0;iscores[name2])scores[name2]=score;
}
}
map::iterator itr=scores.begin();
player_num=0;
for(;itr!=scores.end();itr++) {
players[player_num].name=itr->first;
players[player_num].score=itr->second;
player_num++;
}
qsort(players,player_num,sizeof(player_t),qsort_comp);
count=0;//Number of people who got less points
for(i=0;i0 && players[i-1].score=0;i--) {
if(iplayer_num*50/100) {
category="noob";
} else if(players[i].got_more>player_num*20/100) {
category="random";
} else if(players[i].got_more>player_num*10/100) {
category="average";
} else if(players[i].got_more>player_num*1/100) {
category="hardcore";
} else {
category="pro";
}
printf("%s %s\n",players[i].name.c_str(),category.c_str());
}
return 0;
}
結果：426点 そこそこ。
C. Geometry Horse
これは…貪欲でおk？→Pretest Failed→問題の解釈を誤った！→修正して提出
► スポイラーを表示
CODE:
#include
#include
typedef long long ll;
struct figure_t {
ll num;
ll cost;
};
int figure_num;
figure_t figures[100];
int kizyun_num;
ll kizyun[100];
//syo-zyun
int qsort_comp(const void* x,const void* y) {
const figure_t* a=(const figure_t*)x;
const figure_t* b=(const figure_t*)y;
if((a->cost)>(b->cost))return 1;
if((a->cost)cost))return -1;
return 0;
}
int main(void) {
int i;
scanf("%d",&figure_num);
for(i=0;i0;i--) {
kizyun[i]-=kizyun[i-1];
}
int now_figure=0;
int now_kizyun=0;
ll score=0;
while(now_figure=kizyun_num) {
score+=figures[now_figure].cost*
figures[now_figure].num*
(now_kizyun+1);
now_figure++;
} else {
if(figures[now_figure].num>kizyun[now_kizyun]) {
score+=figures[now_figure].cost*
kizyun[now_kizyun]*
(now_kizyun+1);
figures[now_figure].num-=kizyun[now_kizyun];
now_kizyun++;
} else {
score+=figures[now_figure].cost*
figures[now_figure].num*
(now_kizyun+1);
kizyun[now_kizyun]-=figures[now_figure].num;
now_figure++;
}
}
}
printf("%I64d\n",score);
return 0;
}
結果：582点 終了時には500点満点になっていたのですが、
誰かがシステムテストで落ちた影響で1000点満点になったようです。
D. Plane of Tanks: Duel
所謂普通の確率DP？…でも両方100%の確率で外したら全然決着がつかないし、
そうでなくてもいつ終わるかわからないし、わからない！
ソースコードはありません。
E. Power Defence
攻撃のタワーとフリーズタワーを向かい合わせに配置して…でもフリーズタワーの影響範囲が…
めんどくさそう！パース！（おい）
ソースコードはありません。
F. Gnomes of Might and Magic
え？え？問題文何言ってるの？わけがわからないよ。
ソースコードはありません。
Hack
コーディングと撃墜が分かれていないということは、
コーディングを早めに諦めればそれだけ長い時間を撃墜に当てられるということ。
思う存分撃墜してやりました。
主な撃墜対象としては
A：最初の0の処理忘れor処理ミス、桁数制限が無いor甘いことによるオーバーフロー
B：隣にあるプレイヤーのデータとスコアが同じ間(インデックスを確認せずに)ループ
C：不完全な多倍長計算
がありました。
私がいたRoom 74
撃墜に使ったデータはこちらです。
► スポイラーを表示
A（1行が1個のデータです、実際に投げていないものもあります）
CODE:
214748364821474836482147483648
1844674407370955161600
010
429496729600
4294967296429496729642949672960
42949672961000010000
4294967296111111111
100001000010000
458129844910000100
500000000010000100
0010000000
B
C
CODE:
10
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1000 1000
1
1000000
[hr]
おまけ
Japan Alumni Group Spring Contest 2012
AOJで（比較的出やすい時間に）コンテストがあると聞いた（見た）ので、参加してみました。
案内のページ
Everyone is eligible to participate the contest but please be very sure that this contest is intended for World Finals; The problem set will be far harder than other JAG's practice contests.
意訳：誰でも参加できるよ、でも世界大会を想定しているから超難しいよ。しっかり理解しといてね。
よし、受けて立つ！
→開始
A：うわぁ、実装ゲーだ！パース！
B：え？グラフの切断？今の僕には理解できない。
C：45^4通りなら全探索！…よく考えたら4^45通りだ。無理。
D：僕には、わからないよ。
E：グラフから閉路を消す？…わけがわからないよ。
F：凸包？…いや、コーナーケースが…
G：工ｴｴｪｪ(´д｀)ｪｪｴｴ工
H：？？？？？？？？？？
I：これはDP…いや、10^18だと！？どうみてもMLE…以前の問題。
J：上から順番？コーナーケース？…？？？
…やばい、マジで難しい。
→しばらく経過
やばい、全然解けない！みんなはBを通してる人が多いみたい。わけがわからないよ。
基地が繋がっていない場所を切ったらいけないから…
最大値が10000だからshortで行ける。
→Runtime Errorを量産。＼(^o^)／
→さらに経過
Iも通してる人が多いみたい。よく考えろ。
障害物が30個しかない。ということは障害物と障害物の間を効率良く計算できればいいはずだ。
でもどうやって？数列？書き出してみる。だめだ、全然一般項が求まらない。
何か、武器はないのか！？
…この形は…
そうか！蟻本にあった行列の繰り返し２乗法だ！
→書く→提出→Σ(ﾟДﾟ|||)
#include
#include
#define MOD_BY 1000000009ULL
typedef unsigned long long ull;
typedef struct {
int x;
ull y;
} xy_t;
ull matrix[64][75][75];
void matrix_mul(ull in1[75][75],ull in2[75][75],ull out[75][75],int n) {
ull result[75][75];
int i,j,k;
for(i=0;i0)matrix[0]
[i-1]=1;
matrix[0]=1;
if(iy)>(b->y))return 1;
if((a->y)y))return -1;
if((a->x)>(b->x))return 1;
if((a->x)x))return -1;
return 0;
}
int main(void) {
int case_num;
int w,n;
ull h;
int i;
ull now[75];
ull now_pos;
xy_t noentry[30];
ull now_matrix[75][75];
for(case_num=1;;case_num++) {
scanf("%d%llu%d",&w,&h,&n);
if(w==0 && h==0 && n==0)break;
for(i=0;inow_pos) {
memset(now_matrix,0,sizeof(now_matrix));
matrix_kaizyo(now_matrix,w,noentry.y-now_pos);
matvec_mul(now_matrix,now,now,w);
now_pos=noentry.y;
}
now[noentry.x-1]=0;
}
if(now_pos<h) {
memset(now_matrix,0,sizeof(now_matrix));
matrix_kaizyo(now_matrix,w,h-now_pos);
matvec_mul(now_matrix,now,now,w);
}
printf("Case %d: %llu\n",case_num,now[w-1]);
}
return 0;
}
[/code][/spoil]
メニュー
カレンダー
Clock
最新メンバー
投稿数
統計データ
Link to us
カウンター