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枚ずつになるっしょwという感じ。
要するに正解は貪欲で偶数枚分余分なカードを食べた時なので、最大もそんな感じ。
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は遠いなぁ。
第3回ドワンゴからの挑戦状予選
頑張って帰宅して参加。
以下感想。
A問題 動画検索
max(0,a+b-n) 終わり。
B問題 ニコニコレベル
なんかバグらせる自信があったので後回しにしてしまったが、結局アレだった。
奇数番目からスタートするのと偶数番目からスタートするので場合分けすれば変なこと考えなくてすむしバグらせるわけないじゃん!という気持ちになりました。(書き間違いで2回WA出しました くぅ〜〜〜)
C問題 スキーリフト
まず、グループの来る順番は意味がないことを考える。
4人の場合は必ずそのグループだけ。
3人の場合は1人のグループがあったら一緒に乗せる。
あとの2人グループと1人に関しては(合計の人数)/4 +0 or 1 (ぴったし乗せられるかそうでないか)
AC。
一か八かでB問題を後回しにしてD問題とE問題の部分点にアタックしようとするも1時間以上考えても何もわからず。頭が足りないか経験不足なのかどっちに由来するのかもわかりませんでしたヽ(^。^)ノ
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問題書くのがもうちょっと早ければと行った感じ。
CODE FESTIVAL 2016 参加
タイトルの通り、CODE FESTIVAL 2016参加してきました。
まずは予選の話から。の前にCODE FESTIVALに参加するまでのあらましを。
・CODE FESTIVALに参加するまで
7月くらいに何か新しいこと始めようと思って、競技プログラミングを始める。
C言語を学科に入って少し触った程度からのスタート。
とりあえずAtcoderのコンテストに参加してみるという一環でCODE FESTIVAL予選も参加。
・予選A
最早大分前すぎて何も覚えていません。
今確認したところC問題でドハマリしてたみたいです。文字列の扱いをググりながらやっていた模様。
結果余裕の予選落ち(688位)。
・予選B
これももはや曖昧ですが、C問題で道の対応関係を間違えて時間が吸われていった記憶。
326位でこれも通過できず。
・予選C
実装が重いとかデータ構造を知らないとかそういう問題がなく、かなり嬉しいタイプのセットだった。
C問題のデバッグで結構時間を食い、C問題を解いた時点で200位くらいでワンチャンあるか???と思いD問題へ。
まず2列で実験し、これは隣り合う2列ごとに見れば操作組み込めるじゃん!と気づき、やったか!?という感じに。
とりあえず部分点に飛び込む。5回目のsubmissionで部分点成功。
同じ方向性で行けるっしょwと提出してみるもTLEで終了(累積和という考えが頭になし)。
結果151位。まさかの本戦へ。かなり問題セットとの相性が良かった(sigma君に大感謝)。
・CODE FESTIVAL 1日目
知り合いと思われる人が3,4人くらいしかいなく、顔を知ってる人は5,6人というかなり戦々恐々とした面持ちで会場へ。周りみんな強そう~~~ 周りみんな知り合いっぽい~~~と思いながら席に着く。参加番号って学年順だったみたいですね。
朝兼昼ご飯を食べていったら昼ご飯が置いてあったので、まあとりあえず食べてお腹いっぱいに(昼ご飯あるのはうれしかったけど、昼ご飯あること教えてほしかった)。
住建を見つけて色々聞く。パーカー1600点以上は厳しいねぇ~~という感じに。
始まってみると周りのカタカタ音でかなり焦る。途中から音無しイヤホンをつけていたけど最初からつけていた方が良かったかも。
A問題 Where's Snuke?
cinして判定を繰り返して見つけたら出力(なお、行と列を間違えた模様)
B問題 Exactly N points
m(m+1)/2 >= N となるような最小のmを見つけて、m(m+1)/2-Nを除いて1~mまで出力。
多分これで必ず上手くいくだろと確信したので、とりあえず提出。AC
C問題 Interpretation
400点問題だし解けるかなと思って問題を見てみるも見た瞬間にかなり険しい表情に。グラフ問題をほとんど通したことがなく、CODE FESTIVALまでにどうにかしようと思っていたが結局何も手を付けられずに来てしまったのでかなり絶望感が漂う。
連結性判定だしUnion-Findっぽいよなぁと感じ、とりあえずUnion-FindでググってヒットしたAtcoderのスライドを読むも要領をつかめず。そもそも今回の問題でどうUnion-Findすればいいのかも分からず。3,40分くらいずっと色々試行錯誤してみるも何も得られずD問題へ。(その後何回か戻ってみるも全く分からず考えるだけ無駄だった)
D問題 Pair Cards
700点問題だったので結構身構えて問題を読み始めるも意外とあっさり解法が思いついた(似たような問題をどっかで見たことがあったけど、その問題の方が注意しなきゃいけないことが多かったような)。
カードの枚数を普通に管理する配列とmod Mでグループ分けした時の枚数を管理する配列を用意して、Mの偶奇で場合分け。0,M/2 mod Mは枚数/2のペアを作れる。i,M-i mod M について枚数が多い方に対してどれだけ同じカードがあるかをチェックしてペアの数を計算。これでAC。
E問題 Cookies
問題名見た瞬間にCookie Clickerを想起したのは自分だけではないと思いたい。0枚所持で1秒間にN枚焼ける状態になるまでにかかる最小時間をdp[n]とかにして1次元の動的計画法を行った。それを利用して最小値を求めた。
N(1+1/2+1/3+...)とかの計算量なので途中で止めればO(Nlogm)とかで部分点くらいなら間に合うという算段。何回かバグらせて部分点。H問題へ。
H問題 Tokaido
部分点にアタックしようとした。i,i+1の状況は常に保たれるだろうからdpだろうなーというところまでは分かったが、O(N^2)とかになっちゃいそうだし、条件分岐よくわかんねーという感じで思考を打ち切る。終了。(C問題にかけた時間をこっちに費やしたほうが良かったなぁという気持ち)
そんなこんなで1600点。残り30分くらいからは、パーカーって2000点だったよなぁ~みたいな謎の勘違いをしてました。なぜかパーカーゲット!
700点問題と500点部分点が考察でどうにかなる系の問題で助かりました。Union-Findすら碌に知らず行ったのはアレでしたが。
本選終了後はtouristさんのインタビューをボーっと聞いていて、強い人は強いんだなぁという感想を抱きました。
食事はたらふく食べました(食べ過ぎた)。何名か知りあいと話したり、学科の上の人を認識したり。(二日間通じてそうですが、競プロ界隈に疎くてずーっとぶらぶらあてもなく歩いたりしてました)
エキシビションを見てほげーっとして1日目は終了。近くのホテルに泊まる権利を有してはいましたが、家に帰りたかったのでそのまま帰宅。
・CODE FESTIVAL 2日目
寝坊して朝トナメに遅刻する気しかしていませんでしたが、意外と早く起床。余裕をもって会場に。
この日も朝食を食べていったらお弁当が置いてあったパターン。
Tournament round1
まず2問とも見て、これはヤバいと感じる。
graphはダメだし、文字列もアレだし・・・
とりあえずB問題100点を取ってお茶を濁しにいこうとする。なんかバグったりしたけどとりあえず100点。
A問題に取り掛かるも完全な誤読。終了。(Bの部分点をもうちょっとやるべきだった)
まさかの100点で通過。ダメもとでやってみるもんだね。
Tournament round2
同様の作戦で200点部分点を2つ取りに行こうとする。
A問題の200点を取った後B問題の200点へ。バグらせる。2次元配列の引数を間違えました。以上200点、通過ならず。
A問題が考察すればという問題だったようなので全力で取り組むのが正解だったかもしれない。まあB問題バグらせたのが最大のアレ。
短時間トーナメントはコーディングの遅さが如実に現れることを実感しました。もっと量やらないとダメですね。
Tournament round3は適当に眺めていましたがB問題の最初の部分点は取れそうかな?という感じでした。まあ書いてないからどうせバグらせるんだけど。
そんなこんなでその後は適当に過ごし、チームリレーへ。
・Relay
チームKでした。京大の人が多かったです。問題は下から順番に割り振っていったので、僕は最初はE問題担当に。
問題を一読して、ユークリッドの互除法でgcd求めて後はちょちょいで終わりとはすぐに分かる。
D問題の方と隣り合ってやっていたのですが、Dが魔法陣で手元で計算すれば実装なしなのに気づく。
コーディングが遅いし、あの環境で実装にもたつくのが目に見えていたので、D問題の方と交渉。実装できないんでお願いします!と言ったけど、流石にユークリッドの互除法でそんなこと言うのはアレだったかなと反省。まあ、任せた方が早いのは明白だったので許してください。
(魔法陣計算で一度計算ミスしたのは完全な失態。申し訳なさしかない。)
その後はひたすら掃除と応援。結構止めどなくやっていたように感じましたが、トップチームが早すぎてビックリ。
自分たちのチームも後半の問題で一発通しが多く追い上げていたようには思いましたが、ラストの問題を残してタイムアップ。
ほとんど貢献できませんでしたが、チームリレーのあの雰囲気は楽しかったです。
表彰式で宇都鬼が現れた時はちょっと笑ってしまいました。
なんやかんや楽しかったです。来年もあったら出れるといいな。
・翌日
Union-Findを学びました。おしまい。