Toy と帽子と ADP BE

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

AtCoder Grand Contest 035

1AC5WA。ひどいけど、まあ実力ですか。

各問題

A - XOR Circle

最終的には「全部0」または「nが3の倍数かつ3つの数字(これらは重複していてもよい)が循環している形で、その3つの数字で題意を満たせる場合」が"Yes"、という解答にたどり着きましたが、そこにたどり着くまでが長かった・・・。

全部0というのにも最初気づけなかったし、3つずつ循環していてもよいということにもなかなか気づけなかったのです。 5つもWAを投げているのは、明らかに極端な誤答(例えばn != 3なら無条件で"No"にするとか)を投げて、WAの傾向がどう変化するかを見て対策を立てるという緊急手段をとったためです。 今回に関しては、n == 3でなくても"Yes"になるケースがあると気づけたので、全く無駄にはならなかった模様。ペナルティーは痛いですがやむなし。

B - Even Degrees

一応考えていたのですが、その考察は的はずれだった模様。明らかに構築できるケースでも、それを復元する方法を思いつけなかったので論外ですが。

C以降

見てません。

まとめ

緑コーダーにAGCはきついという、当たり前の結果でした。

まあなんとかAだけでも通してレート微減で済んだのでいいかな、と。水色一発圏内からは遠のいてしまいましたが。

f:id:mdstoy:20190715002501p:plain

AtCoder Beginner Contest 133

4完3WA。あーなんか通常運行に戻ってしまった感が・・・。

各問題

A - T or T

最初、タクシーと電車に分乗するケースがあるのかと思って、A問題にしては難しくない?B問題と間違ってる?と思ったんですが、よく見るとタクシーにはN人全員が乗れることから、A * NBの比較だけでよかったんですね。それにしてもでかいタクシーだな

B - Good Distance

二重ループ(計算部分を入れれば三重ループ)を回して全通りを実際に計算してみればいいです。私はtypo連発してめちゃくちゃ時間がかかってしまいました。

C - Remainder Minimization 2019

結論からいうと、mod 2019なのでiとjそれぞれたかだか2019個について検査すればよくて、最大でも2019 * 2019個を調べれば答えが求まります。

私はなにを血迷ったかmod 2019が最小になるiとjを「別々に」探してから掛け算していて、しかも2019が素数だと思いこんでいて(どう見ても3の倍数です本当にry)、2WAを出してしまいました。

D - Rain Flows into Dams

山1に降った雨をM1、山2に降った雨をM2とします。A1 = M1 / 2 + M2 / 2です。同様に、A2 = M2 / 2 + M3 / 2A3 = M3 / 2 + M4 / 2と循環していきます。このN元1次の連立方程式を、ぐるーーーんと順番に解決していくと、最終的にM1が求まります。M1が求まれば、順次M2以降も求まりますね。

私はintで足りると判断してたら1WA喰らいました。どこでオーバーフローしたのだろう?

E - Virus Tree 2

必死に数え上げの方法を考えていましたが、シンプルなケースでしかわからずタイムアップでした。

今、editorialを見て膝から崩れ落ちているところです。問題の言い換えをする技術がなさすぎるよ自分・・・。

F - Colorful Tree

そっとじ。

まとめ

問題を言い換える技術なぁ・・・。わかっていてもなかなかできません。知識の問題もあるし頭の固さの問題もあるし時間に追われて焦ってしまうという問題もあります。そこをなんとか克服しないといけませんね。

結局、知識をつけていくしかないかなぁまずは。

で、今回レート増減なしでした。水色を前にして収束し始めてる?まずくない?

f:id:mdstoy:20190707231232p:plain

AtCoder Beginner Contest 132

ABCの3完で、気分的には大惨敗ですね。今回は水色入りを狙っていただけに。

各問題

A - Fifty-Fifty

問題の意味はわかるんですけど、最短の実装法がすぐに浮かばず。

そこで悩んでいても時間がもったいないので、最初に浮かんだ方法、アルファベットの数の26要素のint配列を作って、出現した文字の要素をインクリメントして、最後に26個それぞれ要素がすべて0か2ならYes、それ以外の数が入っていればNoという実装をしました。ループが必要になるので、たぶんちょっと回りくどい実装のはずです。

あーでもeditorialの解法も(A問題にしては)思ったほど軽くはないですね。

B - Ordinary Number

愚直に{p1, p2, p3}, {p2, p3, p4}, ... と見ていけばよいです。ちなみに私はmaxでもminでもないとき条件を満たす、という実装をしました。不等式怖い・・・。

C - Divide the Problems

まず入力を取ってきてソートします。

で、真ん中のふたつ、つまりN / 2番目とN / 2 + 1番目の数が同じである場合、きれいに半分に分けることはできません。その数がどっちか片方に入るので偏りが出ます。なのでこの場合は0です。 異なる場合、単にそれを引けば答えになります。

ていうか今気づいたんですけど、真ん中のふたつが同じ数のとき、引いたら0になるから結果的には場合分け要りませんでしたねこれ。まあこういうケースが例外的な値になってWAをもらうこともあるので、あらかじめ考察しておくのは悪いことではない、はず。

D - Blue and Red Balls

ふんわりとはわかったんですけど、きっと使うはずと思ってnCrのライブラリもコピペしたんですけど、組み合わせの作り方が結局最後までわからずじまいでした。なさけない。

EとF

チラ見しただけ。

まとめ

相変わらず数学力のほうがネックになっているような気がします。あと、不得手な領域がまだまだ多いので安定しません。今後は苦手な問題を集中的に潰していったほうがいいのでしょうか・・・。

3完なのにパフォ4桁に乗っていて、レートは微減で済みました。Cまでの早解きはできていたのでなんとか助かった感じです。

f:id:mdstoy:20190629233108p:plain

AtCoder Beginner Contest 131

5完で、初の青パフォ。前回のレート減少をのしつけて返してやりました。

各問題

A - Security

単純に隣り合う文字を比較していって、同じものが一つでもあるなら"Bad"、一つもないなら"Good"です。 ループを回してもいいし、4文字限定なのでif文3つ並べてもOKですね。

B - Bite Eating

ひとつだけ抜くリンゴは絶対値が一番小さいものにすると題意を満たすので、それを探して、すべてのリンゴの味の和から抜くリンゴの味を引けばいいです。

C - Anti-Division

「割り切れないもの」の数は全体の数から「割り切れるもの」の数を引けばいいです。

「割り切れるもの」の数は、Cの倍数の数 + Dの倍数の数 - CとDの公倍数の数、です。Cの倍数の数 + Dの倍数の数だけでは、CとDの公倍数についてダブって数えてしまうことに注意。(包除原理)

求めるのはA以上B以下の整数についてなので、B以下についてとA「未満」についての「割り切れないもの」の数を求めて、前者から後者を引けばいいです。A「未満」にしないとちょうどAのときが抜け落ちてしまうので注意です。(私はサンプルに該当するケースがなかったらやらかすところでした・・・)

D - Megalomania

締切時間でソートしてから、前からひとつずつ確認していけばOKです。

ソース見てもらったほうがわかりやすいかも -> https://atcoder.jp/contests/abc131/submissions/6062745

これ、Cの300でもいいのでは?

ちなみに、editorialの実装のようにAとBを逆に格納するとsortの比較関数を書かなくて済むのですが、私はあとで混乱する可能性があるので避けるようにしています。 変数名をわかりやすく付ければいいだけの話なんですけど、競プロの場合その手間を惜しんじゃうんですよね。

E - Friendships

Kが取りうる最大値はN * (N - 1) / 2 - (N - 1) です。これがどういう状態かというと、例えばN=5のとき

  2
  |
3-1-4
  |
  5

こういう状態です。(いわゆるスター) この場合、2-3, 2-4, 2-5, 3-4, 3-5, 4-5 の6つの距離が2です。 あとは、ここから辺を一つ足すごとに距離が2の2点が一つ減っていくので、与えられたKに合うように辺を適当に足せばよいです。

結構最近に、すべてのN * (N - 1) / 2個の辺がある状態から題意に合わせて間引いていくという問題が出題されていたのを覚えていたので、割とすんなりこの発想に至れました。復習は大事ですね。

F - Must Be Rectangular!

私はx座標ごととy座標ごとのmapを用意して愚直に探す、ということをやろうとしたのですが、おそらく嘘解法な上にTLEも出ていました。とほほ。

あとでeditorial読んで勉強します。

まとめ

当たり前ですけど、復習は大事。超大事。

初の青パフォで超回復達成。次回も同程度のパフォならレート水色になるので、昇格戦ということになります。頑張る。

f:id:mdstoy:20190622230041p:plain

AtCoder Beginner Contest 130

2完。ちょうど20回目の参加になりますが、今までで一番ひどい成績(パフォ)でした。そんなことある?!

各問題

A - Rounding

XとAを比較して0と10を出し分けるだけです。

しかし、cin >> X >> A;cin >> X, A と書いてしまい1WA。 波乱の立ち上がり・・・。

B - Bounding

L を順に足していって、Xを超えないところまでの回数+1(D1=0のときの分)が答え。

しかし、回数を足す処理を記述する位置を間違っていたためコーナーケースに引っかかりまた1WA。 ぐぬぬ・・・。

C - Rectangle Cutting

考え方がそもそも間違っていて問題外。(対角線上にあれば対角線に切る、それ以外は縦か横に切る、だと思ってました・・・。)

本当に幾何は苦手なんです・・・。

D - Enough Array

累積和を取ってしゃくとり法でOK。和がK以上になる位置が見つかったとき、それより後ろが全て条件を満たすので、N - 見つけた位置 + 1を合計に足していくのがみそ。

なのですが、なぜかWAがなくならない。コンテストが終わってから見直したら、一部の変数をintで定義していたという。long longに直したら一発で通りました・・・。

400点損した。これはひどい。ひどすぎる。

E と F

C, Dがご覧の有様だったので、チェックすらできず・・・。

まとめ

とりあえず落ち着きましょう。

あと、実は調子が悪いことは自覚していたので、休む勇気を持つべきだったかもしれないです。コンテストの参加は義務ではないですしね。

AGC以外では初めてのレート減少で1000割ってしまいました。まあ続けていればたまにはそういうこともあるかなくらいに思っておくことにしましょう。 Dはありがちなミスで400点失ってしまいましたが、解法はちゃんとあっていたわけですし。まあそう悲観することもないかな、と。

f:id:mdstoy:20190616233200p:plain

AtCoder diverta 2019 Programming Contest 2

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-kansai.doorkeeper.jp

に行ってきました。

speakerdeck.com

資料はこちら(と同じ)だそうです。

感想

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

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

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

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

まとめ

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