TCO2017 Round 1B
参加してました。
Easy.
H2OとO2の量と1日当たりのコストが与えられるから何日生きられるか求める問題。H2OからO2を作ることが可能。
H2Oのみ、O2のみについて計算した後、O2が切れた時点でH2Oがまだ残ってたらOの量をH2Oコスト+2*O2コストで割ったら終わり。
問題の中で、H2OがH20になってたり想定解がオーバーフローしてたりでかなりカオスだった。
Med
1~1000000000の値のついたコインを重複ありで20個以内取ってきて、払える金額がN通りになるような組み合わせを一つ挙げる問題。
2進数で考えた。
2^m < N <2^(m+1) なら、1,2,4,...,2^(m-1),N-2^m+1を使えば、1~Nまでのすべての金額を払えます。おしまい。
Hardはグラフだったのでもうなんか考えることもしなかった。チャレンジもよくわかんないのでやりませんでした。
Topcoderはよくわかんない。おわり。
AtCoder Regular Contest 071
参加しました。
C問題 怪文書 / Dubious Document
n個の文字列が与えられるので、各々の文字列に対していくつか文字を取り出して別の文字列を作った時にどの文字列からでも作れる文字列のうち最長のものを求める問題。
出てくる文字をカウントしていって、各々の文字に対して出てくる回数の最小を計算する。あとはaから順に並べて終わり。（1回バグらせた）
D問題 井井井 / ###
xy座標にx軸に平行な直線がm本、y軸に平行な直線がn本あるときに、作られるすべての長方形の面積の和の10^9+7で割ったあまりを求める問題。
x_i-x_j (i>j)の和とy_j-y_k (j>k)の和を取って掛け算すれば多分いいんだろというノリで考える。
そのままだとTLEなので、足される回数と引かれる回数を考えて、O(n+m)で計算しました。おわり。
E問題 TrBBnsformBBtion
今気づいたけどTransformationってことか。
A,Bからなる文字列に対して、A→BB、B→AAもしくはAAAかBBBであるような一部を消去（場所は選べる）という操作を考える。
文字列S,Tに対してSのa_i~b_i文字目をTのc_i~d_i文字目に変化させられるかを判定する問題。
なんかいっぱいクエリがあるしどうすんだ〜〜〜と思いましたが、逆にいっぱいクエリがあるってことは前処理で位置に対して値が対応付けられるのでは？という気持ちになる。
とりあえず全部のBをAAに変えることを考える。→なんかAの数で分類分けできるっぽいぞ？？？
サンプル見てもそうっぽいにおいしかしないので、S,Tに対してi文字目までの部分列についてBをすべてAAに変えた時のAの個数をx[i],y[i]として予め計算。
kつめのクエリに対して、x[b_k]-x[a_k-1]とy[d_k]-y[c_k-1]のmod.3が一致しているかどうかで判定した。
なんかうまくいった。やったね！
F問題 Infinite Sequence
問題分がまずややこしい。
{1,...,n}からなる無限長の列っていう文字で若干ウッとくるものがあるよね。
第n項以降は同じ数。第i項の直後のa_i個の項はすべて同じ数。
となるような{1,...,n}からなる{a_n}の総数を10^9+7で割ったあまりを求める問題。
とりあえずn=2の時とかを考える。→なんかいまいちよくわかんない。
そのままnで考えてみる。なんか色々分かる。
①1でない数pのあとに1でない数qが来ると、その後は再帰的に全部qになる。
②p 1 1 1 .... 1 1(1がn個) って感じだとその後はまた新たに考えればよい。
なので、n文字目まで残りk文字残っているような時の数列の総数をx_kとすると以下のような漸化式が成り立つ。
x_k = (n-1)^2 + x_(k-1)+x_(k-3)+...+x_0+n+1-k
これをkとk-1の時で連立させると、
x_k - x_(k-1) = x_(k-1) - x_(k-2) + x_(k-3) -1
3項間漸化式の出来上がり。
あとは適当に計算して終わり。一応確かめたらきっちりあってそうだったので、提出したらACでした。
算数ゲーすぎて全完できてしまった・・・ なんか後にも先にもこの順位も全完ももうなさそうですね。
35位 パフォーマンス2742 レート 1981(+141)
黄色まであと19。ギリギリいかない奴だ。
Atcoder Grand Contest 12
今回も数分遅刻。学ばない男。
A問題 AtCoder Group Contest
各人に強さA_iのついている3n人に対し3人組をn個作って、各グループの強さの中央値の総和を最大化する問題。
ソートしてi,3n-2*i-2,3n-2*i-1番目の人でグループを作っていくと最適。
B問題 Splatter painting
グラフはつらい。なんか後ろからやっていくんかなといった感想。知らない。
C問題 Tautonym puzzle
なんか算数要素強そうなのでとりかかる。
同じ種類のものがn個あればそいつらで2^(n-1)-1個の良い部分文字列は作れることは示せた。10^12だと2進数で40bitとかだし、文字列の長さの制約に引っかかるなぁ、なんかいい構成法ないかなーとやっていたけど、何も降ってこなかった。おしまい。
残り3分の時点で535位。うげぇ。。
結局いつも算数しか解いてないので、競プロちゃんとやりましょうっていう話。
Atcoder Grand Contest 11
参加しました。完全に忘れていて数分遅刻しました。
A問題 Airport Bus
sortして前から貪欲した。終わり。
B問題 Colorful Creatures
sortして前から足していってA[i-1]までの和S[i-1]の2倍がA[i]より大きければスルー。もしS[i-1]*2<A[i]ならばmin=iとして記録。
N-minが答え。
C問題 Squared Graph
グラフ問題は無理。
D問題 Half Reflector
算数ゲーの匂いがしたので、いろいろ検証しだす。
左端の状態がAだと最初で終わり。Bだと必ず右端から抜ける。
i番目とi+1番目が異なるとi番目は変化。同じならば変化しない。右端は必ずA。
たくさんやるとBABA...BABA or ABAB...BABA or BBABA...BA。
左端がBのi番目の状態列は1文字目を消去して反転して末尾にAをつけるとi+1番目の状態列になる。
などがわかる。あとは書くだけ（書けなかった）。
コードをちゃんと書きましょう。
274位 パフォーマンス1840 レート1888(-7)。
以上。
住建はクソ。
みんなのプロコン
参加しました。
A問題 Yahoo
yahooを並び替えてできる文字列ならYES、そうでないならNOを出力させる問題。
y,a,h,oの出現回数を調べて終わり。
B問題 オークション
N個出品されていてそれぞれ最初の値段がA_iで1日1品しか買えない。1日経つごとにすべて1円ずつ上がっていくとすると、K個の商品を買うのに最低でいくら？という問題。
安い方からK個買って、順番には依らずコストk(k-1)/2がかかると考えればok。
C問題 検索
この問題の最中に予定がかぶっていることが発覚。同時並行で問題を解いていた。
N個の文字列があって、そのうちA_1,A_2,A_3...番目のものだけに共通する先頭の文字列のうち長さが最小のものを求める問題。ただし、そういうものがないときは-1を出力、また空文字が答えでもokという問題。
自分の書いたコードが理解不能になってグダグダに。方針としては、とりあえず共通する先頭の文字列のうち最長のものをまず求めて、その後ひっかかっちゃいけない他の文字列を区別できるようになるのはどこかを片っ端から調べる感じ。先に調べた最長のものを先頭に持つような他の文字列があったら-1って感じ。
ひたすら愚直にコードを書いた結果、何がなんだかわからなくなりましたとさ。4回くらい直したらなんか通った。やったぜ。
D問題 工場
一通り読んで「何言ってんだこれ？」となった。ニホンゴムズカシイヨ。
問題分の意図を把握したら残り10分もなかったので、時間があれば答えは出るタイプのクソコードを自棄で投げたらTLE TLE TLE TLE TLE TLE TLE。
はい。以上
200位！ キリ番取りました！踏み逃げします！
ちゃんと自分の予定は把握しとこうね。っていうお話でした。（あと、プログラミングちゃんとやろうねって話）
AtCoder Regular Contest 068
参加しました。
C問題 X: Yet Another Die Game
サイコロゴロゴロして上の面の和がS以上になる最小回数を求める問題。
XI[sai]を思い出しました。小人くんが6の目と5の目をカタカタ回すのを想像。
6と5の面をひたすらゴロゴロすれば最大。あとは回数を計算。
D問題 Card Eater
N枚のカードに数字がふってあって、「任意の3枚を取ってきて数字最大と最小のカードを食べる」という操作を何回かやってすべての数字が2枚以上にならないようにする時最大何枚残せるかという問題。
同じ数字が3枚以上あると、そいつらを3枚取ってくれば2枚は減らせる。貪欲的にやれば各数字1枚か2枚。まあ適当に食べて行けば1枚ずつになるっしょｗという感じ。
要するに正解は貪欲で偶数枚分余分なカードを食べた時なので、最大もそんな感じ。
E問題も頑張っていもす法とかを考えましたが、次々に反例が湧いてきて終了。区間がd以上なら必ずとかはわかったけれど、区間の長さで場合分けっていうのは全然頭になかった。
124位 パフォーマンス2092 レート1895(+28)
春休みは少しずつプログラミングしよう。
Atcoder Grand Contest 08
参加した。
A問題 Simple Calculator
xに対して+1or符号反転を最小で何回やればyになるかという問題。
とりあえず愚直に場合分けすりゃ余裕っしょ！→x,yの符号と大小がややこしくてどっか間違えてWA。
人間にとってわかりやすい解き方を考える。
y-x,y+x+1,-y-x+1,-y+x+2のうち非負で最小のものを取ればいい。AC
B問題 Contiguous Repainting
与えられた数列に対して自由にk個連続する箇所を黒か白で上塗りして、最終的に黒く塗られているところの和の最大値を求める問題。
ある程度自由に色塗ることはできそうということはわかった。dpっぽさがあったのでdpを考えてみる。
mマス目までの時の最大値がわかっている時にm+1マス目を黒か白で塗る過程があるかでdpやろうとした。サンプルは通ったけど残念ながらWA。つらみ。
C問題 Tetromino Tiling
与えられたテトリミノで2*2nの長方形を作った時のnの最大値を求める問題。
最初任意の長方形かと思ってこんなん無理でしょと思っていたがよく読むと2*2nだった。テトリスをやったことある人ならなんとなく分かると思いますが、2*nの長方形になる時は、Oミノ、Iミノ、Lミノ、Jミノの4種類の組み合わせしかない。
Oミノはそのまま置けばいい。他のものはとりあえず2つ組み合わせれば2*4の長方形ができる。IミノLミノJミノ1枚ずつで2*6の長方形ができるので、それにだけ注意する。
AC
D問題以降は知りません。D問題はワンチャンあったのかもしれないけど、まあ結果論。
169位 パフォーマンス 1989 新レート1868(+16)
2000は遠いなぁ。
