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位。うげぇ。。
結局いつも算数しか解いてないので、競プロちゃんとやりましょうっていう話。
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位！ キリ番取りました！踏み逃げします！
ちゃんと自分の予定は把握しとこうね。っていうお話でした。（あと、プログラミングちゃんとやろうねって話）
