端端舝

AtCoder Regular Contest #018

賤掊揃蹋

2014爛 3堎 1゜

?AtCoder Inc. All rights reserved.
1

A�觳 BMI (賤掊: kyuridenamida)


2

A�觳 �觳衙猁
1. 旯墿[??]午BMI [??/?2 ]互迵尹日木月﹝
2. 眕狟及憝�S宒互傖曰蕾勾及匹极笭[kg]毛欄呾六方﹝
(极笭 ?? )
???[??/? ] =
旯墿 ? 2
2


3

A�觳賤楊

1. 迵尹日木月宒毛极笭[kg]卞勾中化賤仁﹝∣
极笭[??] = (???[??/?2 ]) ℅ 旯墿 ?

2

2. 仇木毛堤薯允月﹝凶分仄﹜迵尹日木月旯墿及�g弇反

cm卅及匹﹜100匹賃曰丟奈玄伙卞眻今卅仃木壬卅日
卅中仇午卞𠸎毛勾仃月﹝
引凶﹜堤薯儕僅卞𠸎毛勾仃月﹝

4

A�觳娗逋(堤薯儕僅卞勾中化)
? 踏隙及�觳反﹜斛猁儕僅(羯�悷船0.01互眕狟)互公木幻升匹卅

中凶戶﹜嗣仁及晟惤匹﹜杻卞砩舑仄卅仁化手淏湘互腕木月井手仄
木卅中﹝
? 晟惤卞方勻化反﹜�忒卞侳戶日木化堤薯今木月仇午互丐月凶戶﹜
灍杅毛堤薯允月�觳匹反堤薯鳻杅卞憝允月𤩸宒硌隅毛隴尨腔
卞俴中﹜斛猁儕僅眕奻及堤薯毛允月仇午毛�仁芢𠾴允月﹝

(C晟惤及瞰) printf(※%.10f§,1.23); //堤薯反§1.2300000000§

5

B�觳跡赽萸午淕杅 (賤掊: catupper)


6

B�觳 �觳衙猁

1. N�及跡赽萸互迵尹日木月
2. 公木日及丹切3勾毛妏勻化ʊ褒倛毛釬月
3. 醱搪互淏及淕杅匹丐月手及及杅毛А戶方

1 汨 N 汨100
1 汨 ?, ? 汨 1,000,000,000


7

B�觳砑隅賤
?

0,0 , ?1, ?1 , ?2, ?2 井日卅月ʊ褒倛及醱搪S反眕狟及宒
匹А戶月仇午互匹五月

? = 汰 ?1 ?2 每 ?1 ?2 汰 2
?

埻萸毛漪引卅仁化手中內木井珨萸互埻萸卞卅月方丹ʊ褒倛
毛ⅸ俴痄�允木壬方中

?

ʊ褒倛及�萸井日醱搪毛А戶月源楊反螿堤
? ABC002 C ☆眻偍★脹匹手堤化中引允﹝

8

B�觳砑隅賤
?

N互苤今中及匹�化及ʊ褒倛及醱搪毛捼屯化手謎今公丹
↙ �抻坰

?

肮元ʊ褒倛毛笭恚仄化市它件玄仄卅中方丹卞𠸎毛勾仃引仄斤丹

?

�呾講ㄩ

? ?3


9

B�觳蛁砩萸

1 汨 ?, ? 汨 1,000,000,000
?

醱搪反仇及ㄡ�\仁日中及湮五今卞卅曰丹月及匹C晟惤卅升匹反
int倰分午左奈田奈白伕奈仄化仄引丹

? long long int倰卞仄卅中午Wrong Answer?
? 偶俋int倰匹手湮桾痲﹝分仃升羯�湮桾痲匹反卅中
?

double(捷儕僅腹�苤杅萸杅)倰↘井卅曰引內中


10

B�觳蛁砩萸
?

醱搪: ? = 汰 ?1 ?2 每 ?1 ?2 汰 2

?

S互淕杅卞卅月井升丹井及瓚隅
?

?1 ?2 ? ?1 ?2 互髒杅井升丹井

? int卅日左奈田奈白伕奈仄化手劐歹日卅中
? S互0井升丹井及瓚隅

? int卅日 ?1 ?2 ? ?1 ?2 互232 (int倰及㜳尹月��及湮五今)
及捷杅及媆及心瓚隅卞囮㷍允月

11

B�觳 double互引內中燴蚕(1)

?

嗣仁及晟惤及腹�苤杅萸杅倰反IEEE 754 卞價勿中化中月﹝
瞰尹壬C晟惤及double反﹜睫瘍窒1bit?硌杅窒11bit?�杅窒
52bit匹�傖今木化中月﹝硌杅窒互�化0匹剠中癹曰﹜做怱及
淕杅申永玄午仄化1bit袚樓今木﹜53bit互�杅窒及盟午卅月﹝

?

公及俶斮奻﹜2^53毛閉尹月淕杅�反﹜2及捷杅覦心匹仄井
桶政匹五卅仁卅曰﹜2^54毛閉尹月淕杅�反4及捷杅覦心匹仄
井＃眕狟肮�﹝


12


?

眕狟及C晟惤戊奈玉毛灍俴仄化心月午﹜
灍蕣卞a==b互True卞卅勻化中月仇午互復庲匹五月﹝
#include <stdio.h>
int main(){
double a = 9007199254740992.0; // 2^53
double b = 9007199254740993.0; // 2^53+1
if( a == b ){
puts("a==b");
}
}


13


?

double反64bit分互﹜64bit淕杅毛桶政匹五月歹仃匹反卅中ㄐ

?

踏隙﹜10^9沌2^30分井日﹜釱㻢及𨩆仃呾匹﹜
2^30*2^30 = 2^60 >> 2^53午卅勻化仄引丹仇午互丐曰﹜
公丹卅勻凶�磁﹜髒✽互淏仄仁瓚隅匹五卅仁卅月﹝

∥int及�磁方曰WA互�尹化仄引丹＃


14

B�觳切卅心卞
?

N互手丹屾仄湮五仁化手賤仃引允

?

醱搪互淕杅井升丹井反�萸及x及髒✽,y及髒✽卞仄井方日
卅中及匹跪跡赽萸毛4籵曰卞弘伙奈皿煦仃仄化﹜羥絞卞𨩆仃
呾毛允月

?

醱搪互ㄟ及手及毛壺井卅仃木壬卅日卅中互﹜仇木反珨眻�

奻卞�K少3萸毛杅尹木壬匹五月


15

B�觳切卅心卞
?

�萸�及眻�毛伃仆化﹜肮元眻�互睡�內勾匹化仁月井捼
屯木壬謎中﹝眻�毛羥絞卅由仿丟奈正匹桶仄化﹜末奈玄允月
卅升允木壬O(N^2 log N)匹�I燴允月仇午互匹五月﹝

?

仇及午五反眻�毛奪燴允月午五卞左奈田奈白伕奈卞𠸎毛勾仃
卅仃木壬卅日卅中


16

C�觳炟杸尹 (賤掊: catupper)


17

C�觳 �觳衙猁

1. 扔奶朮互N℅M及ㄡ棒啋饜蹈X互迵尹日木月
2. aˉc卅日X[a][b]汨 X[c][d]午卅月方丹卞�K太杸尹月
3. 駙痄�穴件甩永正件擒褩及郔苤�毛А戶方


18

C�觳⻌薯及觴杅

?

?0, ?, ?互迵尹日木月

?

? ?+1 = ? ? + ?

??? ?匹汜傖仄凶�互跪炟及傖�

? 仇木毛�K太杸尹月
?

a mod p = 0及午五 ↙ ?0 眕俋反�化肮元�卞卅月

?

a mod p ≧0及午五 ↙ 傖�反�化�卅月�毛龰月


19

C�觳 ?0 眕俋肮元�磁
?

?0 互�仁斛猁井丐月井升丹井匹�磁煦仃

? �井卅仁化中中卅日掞手�井卅仁化謎中
? 駙痄�擒褩反0
? �仁斛猁互丐月卅日珨楓摽欠及掞井午蝠𡥼
? 駙痄�擒褩反2℅(N-1)


20

C�觳 �互允屯化�卅月午五
?

跪汜芺及痄�珂及俴互珨砩卞隅引月
? x楓醴卞傖�互�中�反菴

?
?

俴卞痄�允月

? 跪俴卞勾中化�e〝卞蕉尹化謎中

?

俴傖煦及痄�擒褩反復隅允月及匹蹈傖煦分仃毛蕉尹木壬
謎中


21

?

眕狟及瞰毛蕉尹月

0
1
2
3
4
5
6

0 1 2 3 4 5


22

?

3俴醴卞俴仁屯五汜芺分仃蕉尹月

0
1
2
3
4
5
6

0 1 2 3 4 5


23

?

�五源反中欠中欠蕉尹日木月


24

C�觳蕉舷
?

酘�及方丹卞蝠船及嗣中痄�反﹜蜊囡及豻華互丐曰公丹


25

C�觳蕉舷
?

痄�ゴ午痄�摽匹蹈及湮苤互⻌木杸歹勻化中月卅日壬﹜
公木日及醴腔華毛欄卞仄化手𢖯反仄卅中

?

酘�午衵�匹反1,2蹈醴毛⻌木尹化蜊囡今木化中月

?

5,6蹈醴手⻌木杸尹化中月互𢖯手腕手仄化中卅中


26

C�觳蕉舷
?

痄�ゴ及蹈及湮苤憝�S毛悵勻凶引引痄�仄凶日郔羥賤及珨
勾卞卅月

? ゴ旦仿奶玉方曰﹜⻌木杸尹毛仄化手腕毛仄卅中井日

郔羥匹卅中


郔羥

27

C�觳賤楊
?

痄�摽及俴仍午卞�觳毛煦仃月
? 丐日井元戶�极匹末奈玄仄化赻煦互睡俴醴卞俴仁井捼屯化

云仁 ↙ O(NMlog(NM))
?

蹈及湮苤憝�S毛悵勾方丹卞痄�珂毛𢜪隅允月
? 踏僅反蹈卞勾中化末奈玄允月 ↙ O(MlogM)毛N俴煦

?

跪炟卞勾中化痄�ゴ午痄�摽及穴件甩永正件擒褩毛�呾仄
化駙睿毛А戶月 ↙ O(NM)

28

C�觳賤楊
?

磁�匹O(NMlog(NM))
? 㦤萸賤楊


29

D�觳 �W反衭絻互屾卅中 (賤掊: kyuridenamida)


30

D�觳 �觳衙猁

1. N(汨10^4)�及�萸午M (汨10^5)掛及淏及笭心葆
五及煘井日傖月窣磐卅剠砃弘仿白互迵尹日木月﹝凶
分仄﹜肮元戊旦玄及煘反100掛眕狟﹝

2.

郔苤�郖躂及戊旦玄午�杅毛А戶凶中﹝


31

D�觳郔苤�郖躂午反

1. 弘仿白互漪戈煘井日�傖今木月﹜�化及�萸毛�什躂
(寯繚及卅中窣磐卅弘仿白)及仇午毛�郖躂午網太引允﹝

2.

郔苤�郖躂午反﹜煘及笭心及磁�互郔苤匹丐月方丹
卅�郖躂及仇午毛晟中引允﹝

32

D�觳郔苤�郖躂毛А戶月失伙打伉朮丞
測桶腔卅ㄡ勾及失伙打伉朮丞及靡ゴ毛畿賡仄化云五引允﹝仇木日卞

勾中化反生永玄匹𨈘坰允月午允什卞揃蹋互�勾井月午佷中引允﹝
褣仄中失伙打伉朮丞匹反卅中及匹﹜岆準捼屯化心化仁分今中﹝
1. 弁仿旦市伙楊
2. 皿伉丞楊


33

D�觳 �觳及蕉舷
1. 詢点澱(�萸1)互�化及陔⻌汜午衭絻卞卅月(窣磐卞卅月)毛

郔苤愐蚚匹絻傖允月?郔苤�郖躂
(愐蚚互�化淏卅及匹斛內�郖躂卞卅月)
2. 赻煦手仄仁反赻煦及衭絻井日扥太化月煘及心仄井妏尹卅中
↙羥ピ卞支木壬￤砩及�郖躂互釬木月﹝剠�仄化中中秶廣﹝
3. 肮元戊旦玄及煘互100掛眕狟
↙㦤萸賤楊卞云中化笭猁

34

D�觳窒煦萸(10萸)賤楊
1. 煘及戊旦玄互�化�卅月

↙ 郔苤�郖躂互珨砩卞隅引月(弁仿旦市伙楊互�郗腔賤楊分勻
凶仇午毛蕉尹月午隴日井)
2. 郔苤�郖躂及戊旦玄反癶籵卞А戶﹜腢太源及杅午仄化反﹜§1§毛
堤薯允木壬謎中﹝


35

D�觳㦤萸(100萸)賤楊尺及軑�眭舑(1)
1. 弘仿白及(仿矛伙葆五)�郖躂及�杅反﹜

仿皿仿扑失件俴蹈午網壬木月眕狟及方丹卅俴蹈及﹜￤砩及苤俴
蹈及俴蹈宒及�卞脹仄中仇午互眭日木化中月 (俴蹈躂隅燴)﹝
[仿皿仿扑失件俴蹈L]
1. �褒傖煦? ?? 反﹜弘仿白及�萸i卞�互勻化月煘及杅
2. 準�褒傖煦? ?? 反﹜(-1)℅(�萸i午j毛眻諉�什煘及杅)


36

D�觳㦤萸(100萸)賤楊尺及軑�眭舑(2)
2. 撿极瞰午仄化﹜眕狟及方丹卅弘仿白卞勾中化蕉尹月﹝

2
L = ?1
?1
0

?1
3
?1
?1

?1
?1
4
?2

0
?1
?2
3

3. 羥絞卅苤俴蹈及俴蹈宒毛�呾(踏隙反1俴1蹈及手及毛妏丹)
2
L = ?1
?1
0

?1
3
?1
?1

?1 0
?1 ?1
4 ?2
?2 3

3
?1
?1

?1
4
?2

?1
?2 = 13
3

﹤�郖躂及杅反13籵曰

37

D�觳㦤萸(100萸)尺及蕉舷
1. 弁仿旦市伙楊反﹜苤今中手及井日�郗卞﹜丐月煘及袚樓卞方勻

化弘仿白卞寯繚互汜元卅仃木壬公及煘毛妸蚚仄化中仁失伙打伉
朮丞匹丐勻凶﹝升及郔苤�郖躂卞勾中化手﹜丐月戊旦玄毛厥勾
煘及掛杅反劐趙六內﹜丐月戊旦玄毛厥勾煘及心卞覂醴仄凶午五﹜
公木日卞方月窣磐憝�S反劐趙仄卅中﹝
2. 仇及蕉舷毛怳引尹凶奻匹郔苤�郖躂及�杅毛А戶月源楊毛
棒旦仿奶玉卞�徭允月﹝

38

D�觳㦤萸(100萸) 砑隅賤
1. 煘毛戊旦玄匹弘伙奈皿煦仃仄﹜苤今中戊旦玄及煘及弘伙奈皿井日

�楓卞眕狟及�I燴毛靜曰殿仄俴丹﹝郔場(�极及湘尹)=1
1. 肮元戊旦玄及煘分仃毛蕉尹凶弘仿白毛蕉尹﹜公及弘仿白及�
郖伬及杅毛杅尹﹜公木毛(�极及湘尹)卞𨩆仃磁歹六月﹝
2. 公及戊旦玄及煘互釬月窣磐傖煦毛﹜公木冗木ㄠ勾及�萸卞
㇌窺允月(仇及�I燴卞方曰汜元月赻撩煘反祅壺允月)﹝
2. 眕奻毛窣磐傖煦互1勾卞卅月引匹靜曰殿仄﹜湘尹毛堤薯允月﹝

39

D�觳 �釬瞰(⻌堤薯瞰3)
∣

1

1

2

3

1

1

2

2
2

6

4

1,2,3

1
2

㇌窺摽及弘仿白匹
戊旦玄2及煘分仃毛蕉尹凶弘仿白
2

5

2
2

4

5,6
2

�郖伬(躂)及杅反5�

1

1

3

1

1

2

6

1,2,3
4,5,6

1

5

∥ 戊旦玄1及煘分仃蕉尹凶弘仿白
�郖伬及杅反3�

﹤郔苤�郖躂及杅反3*5=15籵曰


40

D�觳俴蹈宒及�呾卞𨩆井月�呾講
1. 珨啜卞N℅N俴蹈及俴蹈宒反﹜俴蹈毛ʊ褒趙仄凶丐午﹜�褒傖

煦及搪毛�呾允木壬А引月﹝仇木反O(N^3)匹�呾匹五月﹝
? ʊ褒趙反樓𦑩�\壺互堤懂木壬褫夔匹丐月﹝
? P互匼杅卅日﹜P毛楊午仄化樓𦑩�\壺互褫夔卅及匹﹜
欄啋毛А戶月紱釬毛樓庤仄化手﹜O(N^2*(logP+N)) 匹
ʊ褒趙互褫夔匹丐月﹝ ( 幻廿O(N^3) )


41

D�觳 �极及�呾講(衙呾)
1. 煘及末奈玄 O(M log M)

2. 肮元煘及杅互lim(=100)掛眕狟
↙ 窣磐傖煦及�萸杅反O(lim)↙ 俴蹈宒及�呾O(lim^3)
3. 公木互O(N/lim)隙靜曰殿今木月﹝
↙ O(N/lim) * O(lim^3) = O( N * lim^2 )


42

端端舝

AtCoder Regular Contest 018 賤掊

More Related Content

AtCoder Regular Contest 018 賤掊