読者です 読者をやめる 読者になる 読者になる

AtCoder Grand Contest 014

参加しました。

A問題 Cookie Exchanges

3人がクッキーをA,B,C枚持っている時、各々が半分ずつ他の二人に渡す操作は何回できるか(奇数になったら終わり)という問題。

 

A,B,C → (B+C)/2,(A+C)/2,(A+B)/2になるので、二人の個数の差は1回の操作で1/2になる。よってシュミレーションすればlog(A,B,C)でいけるという感じ。(3人とも同じ枚数なら無限に続く)

 

B問題 Unplanned Queries

N点の木に対してまず各辺に0をふった後、M個のクエリをやる。

「a_i,b_iの2頂点間のパスに現れる辺にふってある数字を+1する」

全部の辺にふってある数字が偶数になるような木は存在するかという問題。

 

なんとなくa_i,b_iに現れる数字の回数の偶奇がそのまま関係してそうだったので、全部偶数回か調べたら通りました()。

 

C問題 Closed Rooms

H行W列の部屋があり、移動は接する部屋のみ。閉じている部屋と開いている部屋が最初存在していて、1,H行目、1,W列目についたらゴール。

K部屋以下分移動し、K個以下の部屋を開けるという魔法を何回使えばゴールできますかという問題。

 

K個部屋開けてK部屋進むという一連の操作で直進し続けられるので、初期状態でK部屋以下分移動した時に、どこまでゴールに近づけるかさえわかれば良い。

queueを使って行ける部屋を管理してみました。

 

バグらせて時間を結構使ったけど通ったのでよし。

 

D問題は端から貪欲に取っていけばいいということはわかりましたがバグらせました。(終わった後普通に通ったので、ダメ)

 

208位 パフォーマンス2118 レート2021(+12)

 

いつ黄色から落ちるかのチキンレース

 

AtCoder Regular Contest 073

参加しました。

 

C問題 Sentou

スイッチを押すとそこからT秒間シャワーが流れる。

N人がt_i秒にスイッチを押した時、お湯の出る時間の総和を求める問題。

 

最初から順番にシミュレートしました。おわり

 

D問題を見て完全に思考が停止し、E問題でmax,minを見ればいいんだろという投げやりな感じでトライしたところ、ドハマりして無事終了。ダメすぎる。

 

393位 レート更新はまだだけど、黄色から落ちそう。そりゃそうだ。

 

 

AtCoder Grand Contest 013

参加しました。

 

問題A Sorted Arrays

長さNの配列Aを何箇所かで区切って、すべての部分列を単調非減少or単調非増加列にするには最低何箇所必要かという問題。

 

前から見ていって貪欲で取っていく。単調非増加か単調非減少かを判定し、そうでなくなるところで区切って同じことを繰り返す。

 

→なんかサンプルが合わない。

よく見ると、最初の方は同じ数が連続するようなものに対して、非増加か非減少かをちゃんと判定できていなかった(2,2,2,1...と2,2,2,3...の区別ができていなかった)。

直してok。

 

問題B Hamiltonish Path

連結かつ単調なグラフに対して、

・2個以上の頂点を通る

・同じ頂点を2度以上通らない

・パスの少なくとも一方の端点と直接辺で結ばれている頂点は必ずパスに含まれる

の3条件をみたすようなパスを一つあげよという問題。

 

適当にflag[n]とかで訪れたかを確認して、頂点1から行けなくなるまでパス取ればいいんじゃね?と思って適当にパスを取る。→WA

 

問題を勘違いしていて、このような場合一番下の条件を満たさない。

→頂点1から限界までパスを取ったあと、flag[n]をそのままでもう一回頂点1からパスを取ってくっつけた。→AC

 

問題C Ants on a Circle

蟻本の蟻が動くやつの円状バージョンってことでいいよね(?)

蟻本読んでないから正しいかは知らないです。

 

長さLの円状にN匹の蟻がいてそれぞれ座標が小さい順に1,2....Nと名前をつける。どの蟻も1秒に1ずつ進み他の蟻とぶつかると反転して動き続ける。最初の位置と蟻の向きが与えられた時、T秒後の蟻の位置を名前順に答えよという問題。

 

反転せずにすり抜け合っても動きは変わらないので、名前順じゃなければ、蟻の位置は簡単に求まりそう。

位置をどうしようかという話。

・反転するだけなので、1,2,3...,nという蟻の順番は変わらなそう。

・最初1がバトンを持っていると考えて、ぶつかるたびにバトンを渡したと考えればバトンは1→2→3→... もしくは 1→n→n-1→...のどっちか。

1が左回りか右回りかで場合分け(しないほうが良かった気がする)。

バトンが何回受け渡されるかは、最初の位置情報からいけそうだったので計算。

バトンを持ってる奴の動きはひたすら一方向にグルグル回っていくだけなので、最終的なバトンの位置は容易に求まる。バトンを誰が持っているかを求めて、そこからどの位置が誰かが決められる。

 

頑張った結果、微妙に対応関係がずれる。最終的に同じ位置にいる奴らの区別が原因。直したら通った。

 

問題DもDPっぽいから頑張っていい感じのところまでいったと思ったら、途中で間違いに気づき終了。

 

順位 70位(!?) パフォーマンス 2651 新レート2075(+94)

 

ついに黄色くなりました、やったぜ!

 

 

Google Code Jam 2017 Qualification Round

参加しました。英語はつらい。

 

Problem A. Oversized Pancake Flipper

+-+---+-+みたいな列に対して連続するK個の±を反転させる操作で全てを+にするには最低何回必要かという問題。但し操作する箇所ははみ出してはいけない。

 

左端から-があったらひっくり返す。右端まではみ出さないところまでやる。全部+になってたら回数出力。そうでないならIMPOSSIBLE

 

Problem B. Tidiy Numbers

N以下で、昇順になっているような数字(1234, 2333467888等)の最大値はいくつ?

 

Nを上の桁から順に調べていって、広義単調増加してる範囲をしらべ、なおかつ、広義単調増加している列のうち、最後に増加した場所を調べておく。

具体的には、22223344413とかだったら一番左の4の場所を覚えておく。

Nが昇順になっていなかったら、記録しておいた場所の情報を使って、その桁までは同じ、その桁は-1、あとは全部9みたいな数字を出力。

22223344413 → 22223339999

こんな感じ。後は微妙な例外を除去。10から始まる数字とかそういうやつ。

 

Problem C. Bathroom Stalls

N+2箇所の枠があって、左端と右端はすでに埋まっている。すでに埋まっているところとの距離の最小値が最も大きくなるようにK個埋めていくと最後埋める時に左と右に空いてる連続したスペースは何個になりますかという問題。

N=11の時はこんな感じ

K=0 o-----------o 

K=1 o-----o-----o

K=2 o--o--o-----o

K=3 o--o--o--o--o

2^m<=K+1<2^(m+1)となるようなKに対して、全体を2^mで分割して余りを意識しながら、、あとはゴニョゴニョやりました(日本語で書くの難しい)。

 

A~Cまでしか解いてないけど全部通ってたので良かったです。

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位。うげぇ。。

 

結局いつも算数しか解いてないので、競プロちゃんとやりましょうっていう話。