AtCoder Regular Contest 076

参加しました

C問題 Reconciled?

区別可能なN匹の犬とM匹の猿がいるので犬と猿が隣り合わないように直線に並べる方法は何通り(%1000000007)あるかという問題。

NとMの差の絶対値が2以上のときは不可能。

NとMの差の絶対値が1のときは多い方から交互に並べる場合のみ。

N=Mのときは、犬から始めても猿から始めても良い。

あとはN!とM!を求めましょう。おわり。

D問題 Built?

N個の街があって、街の座標(a,b)と(c,d)の間に道を作るには、

min(|a-c|,|b-d|)円がかかります。街同士を繋げて全ての街を行き来できるようにするには最低何円必要かという問題。

x座標とy座標でソートしたものを各々作り、隣り合う点同士に枝を貼って最小全域木を求めればよいです。

実装下手くそすぎて泣きかけた。

E問題 Connected?

長方形の内部（境界含む）に数字が1~Nが2つずつ含まれているとき、長方形の外部に出ずかつ曲線が交わらないように同じ数字を結ぶことができるかという問題。

数字つなぎとかそんな感じのパズルに近いが、適当に曲線を書いていいので本質的にはかなり違いそう。

境界上になければ、空間を歪める感じで、同じ数字を重ねあわせることができるので、数字がともに境界上にあるときだけを考えれば良い。

辺に沿うように、座標軸をとって、辺上で現れる順番に数字の列を作りました。

後は交わらないようになっているかを考えれば良い。

盲目的に再帰をやったけど、stackを使えばいいというのはそれはそうなので非常に悲しい。

終了1分半前にギリギリ通して一安心。

順位 159位 パフォーマンス 2138 レート1993(+18)

地道に黄色に戻していこう！（溶ける時は一瞬）

AtCoder Grand Contest 016

参加しました

A問題 Shrinking

長さNの文字列tを長さN-1の文字列t'に変える操作を考える。

t'[i]はt[i]かt[i+1]を選ぶ。

このとき、全部が同じ文字に成るようにする最低回数を求めよ。

最初の文字列のi番目の文字のみになるような時の最低回数は貪欲的にできるので、全部の文字についてやりました。

B問題 Colorful Hats

1~N匹の猫が色のついた帽子をかぶっている。

i匹目の猫から見ると他のN-1匹はa_i種類の色の帽子をかぶっているとする。

{a_i}が与えられた時そういうパターンは存在するかという問題。

とりあえず考察。

(1) a_iで出てきていい数字は2種類まで(3種類以上あると無理)

(2) 2匹が同じ帽子をかぶっていると必ずその色はすべての猫から見える

(3)a_iで出てくる数字がk,k+1のときkの方の猫は全て別の色の帽子をかぶっている

以上で無理な場合を弾いていけば解けました。

C問題 +/- Recrangle

H*Wの行列が以下を満たすようなものを構成しろ（無理ならNo)

・行列の全要素の和は正

・h*wの部分長方形を取り出しても要素の総和は負

貪欲にh行w列ごとに-hwを配置していけばいいんじゃね？というノリでやったら無事死にました。

H=1,W=3,h=1,w=2で落ちるようです。( 2, -3 ,2 とすれば良い）

全然気づかなかったのでもうダメ。

D問題 XOR Replace

問題文は結構面倒なので省略。

a1,a2,....,x　の値のセットは常に一定なので、末尾とのスワップのみでb1,b2....bnを作ることを考えました。

多分方針はあってるような気がするけど、時間も足りず終了（後半が本質らしいのでやっぱ無理）。

順位　275位 パフォーマンス　1996 レート1975(+2)

精進あるのみ。

AtCoder Regular Contest 075

参加しました

C問題 Bugged

N問の点数がs_iで定められているとき、10の倍数でないような最大の点数を求めよ。

無駄にDPをして1ケースだけ落としました。

D問題 Widespread

N体の魔物のHPがh_iとする。爆発魔法が使えて、1体にAのダメージ他の全員にBのダメージを与えられるとき、何回使えば全員倒せますかという問題。

回数について2分探索してしまえばよい。

とりあえず全員にBのダメージを与えて、後何回A-Bダメージを個別に与えるかを計算しました。

F問題　Mirrored

正の整数nに対して左右に反転させて得られる整数をrev(n)としたとき、

rev(N) = N+DとなるようなNはいくつ存在するかを求める問題。

rev(N)-N= (10^m-1)x_1+(10^(m-1)-10)x_2...

的なことを考えて上から順番に決めていく方針をとりました。

サンプルが通ったので投げたら半分くらいWA。どこがバグってるのか分からず。

C,D書くの遅かったけどF問題解けたっぽいし投げるか！というクソプレイングをした結果、爆死しましたとさ。良い子のみんなは真似しちゃだめだぞ！

427位　パフォーマンス 1452  新レート 1973(-48)

青くなりました　ﾁｬﾝﾁｬﾝ。

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までしか解いてないけど全部通ってたので良かったです。