Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

AtCoder diverta 2019 Programming Contest 2

AtCoder c++ competitive programming

A, Cの2完。終了5分前でぎりぎり通したので、それまでは生きた心地がしなかったです・・・。

各問題

A - Ball Distribution

K - 1人に1個配って、最後の一人に残り全部を配るのが最適です。なのでN - Kが答え、ですが、K == 1のときは一人に全部配る以外の選択肢がないので、そもそも差が存在しないので場合分けしなければなりません。

サンプルにその例がなかったら1WA出してたと思います。怖い・・・。

B - Picking Up

N <= 50 なので、全探索でいけることはわかりましたが、肝心の探索方法がわからずじまい・・・。

editorial にあるような「(xi −xj , yi −yj )で最も多いものが何個あるか」という解法はうっすら浮かんだのですが、実装できずじまいでした。とほほ。

そんなわけで、Bを諦めた時点でCまたはDを通さないと凍死確定ということに。さあ、Toyさんの運命やいかに。

C - Successive Subtraction

自分が最終的にたどり着いた解法がこちら。（ちなみに、ここに至るまでにものすごく試行錯誤しています・・・。）

  • N == 2 のとき
    • 大きい方から小さい方を引く
  • N > 3 のとき
    • 非負の数と負の数がどちらもある場合
      • 非負が多い場合
        • 非負と負を相殺して非負にする（非負から負を引いて非負を新しく作っていく）、このとき負を一つだけ残す
          • 一つだけ残った負から、余った非負および先の作業で作った非負を一つを残して引いていく（一つだけ残った負の絶対値が増えていく）
            • 一つ残した非負から、一つ前の作業のでできた負の数を引く
      • 負が多い場合
        • 非負と負を相殺して非負にする（負から非負を引いて負を新しく作っていく）、このとき非負を一つだけ残す
          • 一つだけ残った非負から、余った負および先の作業で作った負をすべて引いていく
    • 非負の数しかない場合
      • 最小値から最大値を引いて負数を一つ作る
        • あとは非負の数と負の数がどちらもある場合に帰結する
    • 負の数しかない場合
      • 最大値から最小値を引いて非負数を一つ作る
        • あとは非負の数と負の数がどちらもある場合に帰結する

と、まあ、場合分けを頑張って実装でねじ伏せてやりましたよ、ええ。（あかん） とはいえ、前述の通りこれを嘘でも何でも通さないといけない状況に陥ってしまったので、やりきったといえばいえるかも。

editorialや公式YouTubeのような考察は、残念ながら私の頭からは出てきませんでした。

D - Squirrel Merchant

Bが解けなかった時点でCとの二択だなと思ってちらっと見たのですが、その瞬間DPであることを察し、600点のDPはまだ無理だろうということで華麗にスルーしました。

EとF

このような状況だったので、当然問題を開いてもいません。

まとめ

善悪は別として、これぞまさに火事場のクソ力。

レートが下がることも覚悟していたのですが、ギリギリ水パフォで踏みとどまれました。

f:id:mdstoy:20190616002306p:plain

DevLove関西「データベースの複雑性と立ち向かう現場の話」に行ってきました

DevLOVE関西 Database

devlove-kansai.doorkeeper.jp

に行ってきました。

speakerdeck.com

資料はこちら（と同じ）だそうです。

感想

色々濃ゆい話をたくさんたくさん聞かせていただきました。詳しい話は上記の資料を見ていただいたほうがわかりやすいと思いますが、その中でも特にこれは、という話は適宜ツイートしていたのでまず抜粋すると

あと、モニタリングやテストなどをしっかりやるとか、マイグレーションツールは楽になるから何をおいてもまず入れるとか、完全な無停止メンテナンスは現実的に不可能だから、相応の覚悟と政治力も必要だとか、闇の深いリファクタリング（非正規化や外部キーの削除など）には手を出さないとか、チューニングの内容はデータの性質によって変わるし、データの性質は時間によっても変わる（例えばユーザーのデータで20代が最も多かったとして、10年後には30代が一番多くなっているかも）とか、いろいろためになるお話を聞かせていただきました。

これらは結局、当たり前のことを当たり前に、長い時間を（サービスがある限り）かけて、継続的に行うということなんですよね。と自分で言っていて耳がもげそうなくらいに痛いわけですが。

もちろん、言うは易しで、地道な努力と労力を消費するので、上記の一番上のツイートにあるように事前にそれを工数をかけてやるだけの価値があるのかはきっちり見極める必要があるということなんですね。これはデータベースに限らずそうですね。

まとめ

勉強になったのはもちろんのこと、とにかく楽しいお話でした。自分もあんな軽妙な話術を身に着けたいです。（自分は明らかにそういうキャラじゃないけど・・・）

AtCoder Beginner Contest 129

AtCoder c++ competitive programming ABC

4完。まだ緑コーダーなのだから満足してもいい成績だとは思うのですが、Eはなんとかしたかったと思う自分がいる。

罪深いぜ令和ABC・・・。

各問題

A - Airplane

かかった時間に移動の順序は関係ないので、要するにP+Q, P+R, Q+Rの3パターンのうち最小のものを取ればいいです。

B - Balance

累積和を取ると、i番目までとi+1番目からで分けたときS1とS2はそれぞれsum[i]とsum[N] - sum[i]になるので、それらの差の絶対値を端から順に取っていって最小となるものが答えです。

Bで累積和！？と思ったけど、愚直に計算しても間に合うのね。

C - Typical Stairs

i段目に上がる方法は「i-1段目に上がる方法」＋「i-2段目に上がる方法」で求められるので、それをDPで回していくだけです。 壊れている段については上がる方法がないので無条件に0になることに注意です。

CでDP！？と思いましたが、漸化式が単純（ていうかフィボナッチみたいなもの）だからあり、なのか？それにしてもMODもありますしねぇ・・・。

で、単純な漸化式とか言いながら、私はすぐに思いつけず、先にDをやりました。on_

D - Lamp

まず、縦と横で累積和チック？に見渡せる範囲を保存していきます。 例えば#...#.#..という並びに対しては{0, 3, 3, 3, 0, 1, 0, 2, 2}みたいな感じで。

それから、あるマスに対して縦と横の見渡せる範囲を足して、重なり合う範囲がひとマスあるので1を引けば見渡せる範囲がわかるので、すべてのマスに対してそれを求めていって最も大きいものが答えです。

editorialでは縦横の二通りではなく四方向で見える範囲の保存をするような解説がされてましたけど、そっちのほうがまっすぐ捜査するだけで済むので実装がシンプルでバグらせにくいかもしれません。

E - Sum Equals Xor

考察の結果、editorialで言われているところの、「どちらの数についても 1 であるような桁」が存在しない、まではわかりました。

で？

どうすんの？

というところでタイムアップでした。Lを超えないようにという条件がつくので今の私には無理ゲー。

F - Takahashi's Basics in Education and Learning

ちらっと見て、そっ閉じ。

まとめ

やっぱり数学力とDPが今の最大のボトルネックなんですよねー。後者はDPの問題を解きまくれば慣れていくでしょうけど、前者はさすがにつらい・・・。

水パフォは維持できているけど、もうひと伸びがないと水色コーダーにはなかなかたどり着けないですね。

f:id:mdstoy:20190609234427p:plain

AtCoder Grand Contest 034

AtCoder c++ competitive programming AGC

Aしか通せませんでした。BはTLEどまり。悔しい。

各問題

A - Kenken Race

まず、二人の移動する範囲に岩が2つ以上連続して置かれている場合は飛び越えられないので当然"No"です。 以下、そのようなことがないとして考えます。

すぬけ君がふぬけ君を追い抜く必要がない、つまりC<Dのときは、ふぬけ君を先に動かせばなんの障害もないので必ず"Yes"です。 すぬけ君がふぬけ君を追い抜く必要がある場合は、追い抜くために3マス分の空き地が必要ですので、ふぬけ君の移動範囲内にそれがあるかどうかを探します。

AGCの400だからこんなんでいいのかってびびりまくってたんですけど、これだけでよかった・・・。 境界値でミスらないかどうかがちょっと心配だったんですが、それもなくてよかったです。

B - ABC

まずは愚直に再帰で実装してTLE。まあそりゃそうですね。

で、先読みしてAABC、ABCBC、ABCABCに場合分けでしてどれだけ積み重なるか、ってやろうとしたのですが実装間に合わず。この方針があっているかどうかもわからず・・・。

ちなみに後ろから読んでましたけど、editorialを見ると前から読んでよかった？

（追記） 解説ACしました。

https://atcoder.jp/contests/agc034/submissions/5769876

うわー、難しく考えすぎてましたねこれは・・・。

C以降

見てません。

まとめ

スッキリしない結果ではありますが、AGCのB:600が通せなかったことを悔しがるくらいのレベルになったと思うことにしましょう。

なんだかんだでレート1000超えましたし。

f:id:mdstoy:20190602233322p:plain

AtCoder M-SOLUTIONS プロコンオープン

AtCoder c++ competitive programming

ABDの3完でした。ついにRatedで500点を通しました！！いや、3回目のはずなのですが←しつこい。

というわけで、自分の中での最低限のノルマは達成したのでまずはよかったです。

各問題

A - Sum of Interior Angles

恥を忍んで言います。内角の和の公式をぐぐりました。いきなりとんでもないタイムロスで、ABの2完だととんでもなく寒いことになるので、これを埋め合わせるためにCかDのACというプレッシャーがさらに強くなることに・・・。

B - Sumo

これは単に'x'が8個以上あれば"NO"、7個以下なら"YES"ですね。

B問題としては簡単すぎるような気がしますが、forを使うのが想定されるからBの200点ということなのか？ まあ相撲を知っているか知らないかで考察にかかる時間が若干違ってくるかもしれませんね。

C - Best-of-(2n-1)

期待値計算も分数のmodも今の知識ではどうしようもないというやつでした。

D - Maximum Sum of Minimum

紙に木を書いていろいろ考察したところ、どうも根から順番に大きい数を振っていけばいいっぽいように見えたので、とりあえずそのまんまBFSで実装してみたところ（配列の添字のミスで1WA出した後）通っちゃいました。証明？知らない子ですね。

E - Product of Arithmetic Progression

これは多分なんか式変形で計算量が落とせるんですかね？と思ってちょっと考えてみましたが、手も足も出ずでした・・・。数学力のなさよ・・・。

F - Random Tournament

うーん、ふんわりとしたイメージは最後の最後に湧いたんですが（自分の両側から、勝てる可能性のある人が上がってくるかどうかがわかればよい）実装する時間はなく。もっとも正しく実装できたかどうかもわかりませんが。

まとめ

数学力なぁ・・・。

しかし、500点を通したし、パフォーマンスはHighestを更新したので大満足です。明日は鬼門のAGCですが、500点もコンテスト中に通せる率が上がってきているので、0完ってことはないでしょう。ないはずだ。多分ないんじゃないかな。

f:id:mdstoy:20190601234414p:plain

AtCoder Beginner Contest 128

AtCoder c++ competitive programming ABC

3完。寒い。

でも、先週と先々週は500点通したんですよ！？（しつこい）

各問題

A - Apple Pie

問題文通りに、林檎を砕いて破片にして、元からある破片と足して、破片の総数を2で割れば答えです。

B - Guidebook

市名をソート、各市ごとに点数の降順でソート、でいいんですが、実装が面倒くさかったです・・・。

https://img.atcoder.jp/abc128/editorial.pdfでは、pair<pair<string,int>>での解説が載っていましたが、私はmap<string, priority_queue<pair<int, int>>>でやって、勝手にソートしてもらいました。ただ、そのせいでむしろ面倒くさくなったかも。うーむ。

C - Switches

bit全探索でいけるということはすぐわかったのですが、純粋に実装に時間がかかりすぎました。

D - equeue

制約から全探索できることはわかったのですが、マイナスの価値の宝石をうまく捨てる方法がわからずじまいでした。今回BとCの実装にめちゃくちゃ時間を食われたのも痛かったですね。

EとF

問題をチラ見する余裕もなかったです・・・。

まとめ

わしの実装力、どこ行った？！

でもパフォーマンス1103でレートも下がらなかったので、今回はそもそも難易度が高かったようですね。

f:id:mdstoy:20190526231736p:plain

AtCoder Beginner Contest 127

AtCoder c++ competitive programming ABC

4完。平成ABCならやったー、だったのですが。そして、先週と先々週は500点問題がコンテスト中に解けていたのですが。

各問題

A - Ferris Wheel

年齢で場合分けすればよろし。

B - Algae

forとifの、いつものB問題。x2000+i+1を出すためにx2000+iを保存しておく必要があるのがミソです。

C - Prison

一番大きいLと一番小さいRの間にあるゲートが、どのカードでも通れるゲートです。

LとRの大小関係が逆転するときに注意。通れるゲートは0になります。（マイナスにはならない）

D - Integer Cards

Aをソート、BとCの組をC（の降順）でソートして、先頭から貪欲にCで上書きしていけばOKでした。

考察より実装に手こずりました。もっと簡単な解法があるのだろうと思いながら実装でねじ伏せた気になっていたのですが、editorialを見る限り、想定解に近そうで、ちょっと意外でした。

一応、汚いですけど私の解答→https://atcoder.jp/contests/abc127/submissions/5607337

（追記） YouTubeの公式解説を見てみると、やっぱりちょっと実装が力ずくだったっぽいです。priority_queueかー。

E - Cell Distance

問題の意味がぱっと見よくわからなかった（マンハッタン距離だなーということだけはわかった）ので、Fに逃げました。

F - Absolute Minima

こちらは、問題の意味はわかるし、TLEする嘘解答ならすぐ書けたのですが、計算量を減らす方法はわからずタイムアップ。

editorial を見ると、これは知識が足りてないですわ・・・。

まとめ

EFまで安定して攻略するには数学を含めた知識の底上げが必要！？

まあABCでは水パフォ維持で、微々たるものながらHighest更新したのでよし！

f:id:mdstoy:20190525231631p:plain