いつも頭に問題を

競技プログラミング中心で思ったことを書いてく

AtCoder Grand Contest 019(AGC019)

AtCoder Grand Contest 019 - AtCoder Grand Contest 019 | AtCoder
touristtouristtouristtouristtouristtouristtouristtouristtouristtouristtouristtouristtouristtouristtouristtouristtourist!!!
出てました、いまさら感ありますがせっかくのtourist回なので
前回のABC/ARC解説配信で次回は歴史的な回になるとか言われたのでまあ予想通り(?)でした

結果は2完、CとDがまるで分らず、辛かったのは考察を練れば解けるのか、アルゴリズムを知らないと解けないのかわからないこと
それなのに考え続けるしかないこと

A.Ice Tea Store
Nリットルのアイスティーを買う
0.25L,0.5L,1L,2Lずつでしか売られてなくてそれぞれ値段が違う
”ちょうど”Nリットル買いたいとき必要な最低金額を出力

最初はDPかと思って焦ってしまった
買い方パターンは実際は少なくて
0.25をNになるまで買う
0.5をNになるまで買う
1をNになるまで買う
2をNになるまで買う or N-1まで買って残り1L分だけ上の3つのどれかで埋める
なので7通り
全て求める式を書いてminとってオラァって投げたら通りました


B.Reverse and Compare
英小文字からなる文字列がある
区間を選んで1回だけその区間を反転させる事ができる
何通りの文字列が出来上がるか答える

どうしていいかわからなかったのでとりあえずサンプルをノートで実際にやってみた
反転する箇所を選ぶ通りはn*(n-1)*0.5通りあることが分かったため文字が被らなければそれが答えであると分かった
また回文を反転させると同じものが取り出せるので、全通りから回文の個数を引いて出力すればいいのでは?と思ってコードを書いた
コードを書く前に試せばよかったがサンプル3が当然合わない、親切流石tourist
サンプル3をノートで試していると「abca」のような文字列があったときに
1-4で反転したものと2-3で反転したものが同じであることが分かった
つまり同じ文字で囲まれた区間は反転すると同じものが取れる、これは回文でも同じように出来るっぽい、証明は自信がない

例えば「abcadeafga」のような文字列だった場合
f:id:ratetion:20170901040554p:plain
こんな感じで同じ文字の間が出現する
のでこの場合は全通りから6を引けば答えになる
これを全探索したらTLEした、馬鹿である

各文字の出現回数を全て求めて、n個だとすると(n-1)+(n-2)+...+2+1をそれぞれ足し合わせて全通りから引いたらAC
500点問題だったのでそこそこ嬉しかった
Submission #1541862 - AtCoder Grand Contest 019 | AtCoder
ノート
f:id:ratetion:20170901040908j:plain
こんな感じでほとんど回文についてとサンプルについて考えてた、気づけば早かったらしい

この問題は是が非でもサンプルに「tourist」を入れるべきだった、許さない

f:id:ratetion:20170901041819p:plain

C.Fountain Walk
900点問題だしここまでかなぁって思ったけどとりあえず開いた
グリッドの街があって各通りに多くて1個噴水がある
スタート地点からゴールまで歩くんだけど噴水があったらその周りを通る
最短距離を出力

噴水は1/4歩く場合は近道になって、1/2歩く場合は遠回りしていることがわかる
また1/2は、条件から各通りに噴水が1個と分かっていることを考えるとせいぜい1回通るか通らないかだと思った
ただ1/2を2度通っても1/4いっぱい通ったほうが得とか、そんな状況はあり得るかわからなかった
方針としては通れるだけ1/4を通ってなるべく1/2を避けるルートを選び、通った個数だけ直線での距離から変更を加えてやればいいと思った
通りの本数がでかいので単純に経路探索は無いだろうという感じ
うん、わからない
終わってから解説読んでもさっぱりじゃった、そうじゃった、、、
いつかチャレンジしなおします



水色になりました
8月中に水色を目標にしてたので嬉しいです、運がよかった
f:id:ratetion:20170901041549p:plain
AtCoder