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は遠いなぁ。
第３回ドワンゴからの挑戦状予選
頑張って帰宅して参加。
以下感想。
A問題 動画検索
max(0,a+b-n) 終わり。
B問題 ニコニコレベル
なんかバグらせる自信があったので後回しにしてしまったが、結局アレだった。
奇数番目からスタートするのと偶数番目からスタートするので場合分けすれば変なこと考えなくてすむしバグらせるわけないじゃん！という気持ちになりました。（書き間違いで2回WA出しました くぅ〜〜〜）
C問題 スキーリフト
まず、グループの来る順番は意味がないことを考える。
4人の場合は必ずそのグループだけ。
3人の場合は1人のグループがあったら一緒に乗せる。
あとの2人グループと1人に関しては(合計の人数)/4 +0 or 1 (ぴったし乗せられるかそうでないか）
AC。
一か八かでB問題を後回しにしてD問題とE問題の部分点にアタックしようとするも１時間以上考えても何もわからず。頭が足りないか経験不足なのかどっちに由来するのかもわかりませんでしたヽ(^。^)ノ
182位でフィニッシュ。もっとがんばりましょう。
AtCoder Regular Contest 065
お酒を飲んだあとに参加したけど、あんまり影響はなかった。
以下感想。
C問題 白昼夢
4種類の文字列を追加していくことで文字列Sを作ることはできますかという問題。
dreamとdreamer、eraseとeraserは先頭の方の文字が一致しているので先頭から見ていくと泥沼なので、末尾から見ていく。
（stringの仕様がわからずstringのアレコレを調べながら書く。）
AC
D問題 連結
道路と鉄道の線路が街にいっぱいあるので、道路でも鉄道でも連結であるような街の数を街ごとに答える問題。
とりあえずunion-findかぁということでこの前書いたunion-findを持ってくる。
とりあえず道路のunion-findして、道路が同じ成分だったら鉄道についてもunionを取ればいいか〜。とりあえず手元のは通ったしいっけぇーサイクロンマグナム！
➔WA
道路が1⇔3、鉄道が1⇔2、2⇔3とかで普通に落ちる。酷い思い違い。
しょうがないから道路と鉄道で連結成分を全部計算。
<<道路の成分、鉄道の成分>、街の番号>というvectorをつかってソートして端から順にunion-find。
連結成分の数をそれぞれの街について出力。
➔AC
多分絶対もっと賢い方法があるんだろうなぁ。
EもFもわからず。(F考察しようとしたけど破滅的な方向へ進んで無事終了）
136位。パフォーマンス2058 新レート1852(+30)
AtCoder Regular Contest 064
AtCoder Regular Contest 064やりました。以下感想。
C問題 Boxes and Candles
n個の箱に端の箱から順にキャンディーがa_i個入っている時、隣り合う箱に入っている個数がすべてx以下になるようにするには何個のキャンディーを取ればいいかという問題。
ぱっと見貪欲っぽさがあったので、どういう貪欲か考えた。
とりあえず、箱の中のキャンディをa[i]、隣り合う個数の和を配列b[i]として持ってみる。隣り合う個数について貪欲してみた。
端から順番に、b[i]>xならb[i]とb[i+1]を-=(b[i]-x)。
サンプルがなんとなく通ったので提出➔WA。後ろ4つが落ちる。
ダメなのは例えば以下のケース。
3 2
6 1 6
この時は嘘解法では真ん中の箱が負の値になってしまうので、それを修正して貪欲。AC。
D問題 An Ordinary Game
二人が文字列sに対して、端以外の文字を取り除く操作を行う。ただし同じ文字が隣り合うようにはしてはいけない。最善手を取るとどっちが最後に操作を行えるかという問題。
適当に考察してみて、abababのパターンかaxaxaのパターンになることは分かった。文字は英小文字だから26種類あるし、なんか知識いるのかなぁと思ってE問題に移ってしまった。
戻ってみてよく考えてみる。終状態は何パターンも考えられるし、その中で最善手とか無理だよなぁ〜。abababaにもacacacacaみたいなのにも成りうるし・・・。と悩んでいたのですが、よく考えればどちらも奇数個。同様にabababababのパターンは必ず偶数個。
ガックリきながら、最初の文字と最後の文字と文字列のサイズの偶奇で場合分けしてAC。
E問題 Cosmic Rays
なんか円状のバリアーがいっぱいあって宇宙線がビャービャー降ってて、スタートからゴールまで行く時の当たる宇宙線を浴びる時間の最小値を求める問題。
始点、終点、バリアーの中心を頂点として、各頂点間を直線で進んだ時に宇宙線を浴びる時間を辺の重みとするダイクストラ法で終わり。
とここまでは特に難なくという感じでしたが、ダイクストラをC++で書いたことなし。テンプレもなし。困った困った。
とりあえず「ダイクストラ C++ 競技プログラミング」でググってそれを参考に書く。バグる。いっぱいエラーが出る。困る。よく見たらcin >>x[i] >> y[i] >> r[i] >> endl;って書いてありましたとさ。
適当に書いたらAC。
F問題 Rotated Palindromes
そもそも問題名の英語がわからない。
m種類n文字の数列回文をぐるぐる回した時にできる数列の総数？を求める問題。（あんまりよく読んでない）
周期とか関係ありそーとは思いましたが、なんかよくわかんねえってなって終わりました。終わり。
108位 パフォーマンス2119 新レート1822 (+46)
D問題に気づくのがもうちょっと早ければ、もしくはE問題書くのがもうちょっと早ければと行った感じ。
