Toy と帽子と ADP BE

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

AtCoder Grand Contest 033

AtCoder c++ competitive programming AGC

0完。AGCはやっぱりまだ怖い。

各問題

A - Darker and Darker

いやもうこれが全てです。

最初は実は愚直に実装して（当然TLE）、次に思いついたのが幅優先探索だったにもかかわらず、なぜ白いマスから黒いマスへの距離を測ろうとしたのでしょうか！？

いやはや本当にちょっと頭が沸いていたとしか・・・。

B - LRUD Game

一次元に落とせることは気づいて、後ろから見ればいいということにも気づいたのですが、押すか引くかの駆け引きをどう表現すればいいのかがわからずじまいでした。

解説を聞いて、自分は問題を点でしか見れていないなーと痛感しましたね。

しかし、単に四方向への貪欲が通るのかー。 先にそれやっとけばよかった気もしますし、それで通したところでなぁという気もします。 YouTube解説ではむやみに貪欲に飛びつくと後々伸びないよー的なことを言われていたので、やらないでよかったと思うことにしましょう。

まとめ

茶色まで落ちなかったので、今回はまあよしとしましょうか・・・。

f:id:mdstoy:20190505015541p:plain

AtCoder Beginner Contest 125

AtCoder c++ competitive programming ABC

全完（ただし4WA）。

今の自分にいえることはただ一つ。

落 ち 着 け

各問題

A - Biscuit Generator

切り捨て除算で T / A をすると生産された回数がでるので、それに一回あたりの生産枚数 B をかければよいです。

（2019-06-03 追記） +0.5というのは、閉区間であることを擬似的に表しているんですね。最近知りました。罠じゃなかった。

T も A も整数なので 0.5 を足そうが足すまいが結果には影響しません。なので式にに含めなくてよいです。むしろ含めると、小数を扱わなければならなくなるため処理が面倒なことになります。

つまり、罠ですｗ

B - Resale

それぞれの宝石に対して、X - Y を計算して、結果が正のものだけを合算すればそれが答えです。

forとifの、いつものB問題ですけど、ほんのちょっと問題文読み解くのが難しかった気がします。（私だけ？）

C - GCD on Blackboard

最適解かどうかはわかりませんが、私の解法は以下の通り。

配列を2つ用意して、片方は1からN-1までの累積GCDを、もう片方にはNから2までの累積GCDを入れていきます。 つまり、9 6 3 4 6という列があったとして、A[0]には9と6のGCDである3を、A[1]にはA[0]と3のGCDである3を、というふうに累積和っぽく格納していきます。 で、2つの配列をうまく組み合わせると、1からNのうちひとつだけが除かれた状態のGCDが取れるので、それらのうちの最大のものがそのまま答えになります。

ただし、注意が必要なのはN=2のときはGCDを取るのではなくて、単にmax(A1, A2)が答えになるという点ですね。

https://atcoder.jp/contests/abc125/submissions/5156890

なお、私の4WAのほとんどは、単なるソースコードの編集ミスです・・・。on_ これで順位を160くらい落として泣きそうです・・・。

D - Flipping Signs

基本的に操作によって負数の偶奇は変化しないですが、うまく位置を取ると増やしたり減らしたりは自在にできます。 なので、最初の列に負数が奇数個なら、最終的に負数を1つにでき、絶対値が最小のものだけを負数としてほかは正数として合算します。 最初の列に負数が偶数個なら、すべてを正数として合算します。

ただし、0があると話が別で、0に-1を掛けても0なのでこれはマイナスを吸収してしまいます。ので・・・

と思っていたのですが、合計を出す時に「負数が奇数個なら絶対値が最小のものだけを負数として」扱うことにしました。しかし、0が含まれている列の場合、それは0です。なので足そうが引こうが結果が変わりません。 つまり、結局のところ0の有無は結果には影響しないのでした。無駄なロジックを書いてしまった・・・。

まとめ

今回DよりCのほうが難しかったですよね？（editorialによると、DはDPが想定解だったっぽい？）

つまらないミスで4WAも出してしまいましたが、結果は初の水色パフォ！！ このまま水色になってしまいたい。

f:id:mdstoy:20190427230452p:plain

f:id:mdstoy:20190427230800p:plain

AtCoder Tenka1 Programmer Beginner Contest 2019

AtCoder c++ competitive programming ABC

f:id:mdstoy:20190420234051p:plain

緑にはなった。なったけど、今回はAB2完・・・。納得いかん。

各問題

A - On the Way

AとBの間にCが入っていれば"Yes"なのですが、A<Bという条件はない、というのが若干面倒なポイントですね。（複数条件が必要） 恥ずかしながらこれに惑わされてちょっと時間がかかってしまいました。

B - e e *ee *e

どうでもいいですが、この問題のタイトル、マークダウン殺しですね。面倒なので修正しません。

で、問題そのものは、ifとforを組み合わせるいつものB問題でした。

C - Stones

はい。

最初WAを出した後に考察し直して、上記のツイートのケースがあることに気づきました。 で、累積和で行けそうってところまでは気づいたのですが、テンパりまくって和のとり方ミスるし、境界線をどう取ればいいのかには気づけなかったし、結局タイムアップでした。とほほ。

わかってしまえばさくっと実装できるんですがねー。

→https://atcoder.jp/contests/tenka1-2019-beginner/submissions/5066701

まとめ

緑にはなった。なったけど。（二回目）　場合によっては「緑になるまでやったこと」も書こうかと思いましたが、今回はあまりに不出来だったのでちょっとモチベが・・・。

まあとにかく慌てないことですかね。危ういと思ったら、一度書きかけのソースコード全部消したほうがいいかもしれない、とか。

AtCoder Beginner Contest 124

AtCoder c++ competitive programming ABC

ようやく、全完。

REとかWAとかあるけど（とりあえず）気にしない。

f:id:mdstoy:20190413223154p:plain

各問題

A - Buttons

これは考えている暇があったら全通り並べたほうが速いと思って（3通りですしね）、前回の公式解説YouTubeで覚えたmax({a, b, c})を早速使いました。

つまりmax({A+A-1, A+B, B+B-1})を出力ですね。

B - Great Ocean View

これはforとifを組み合わせて使えれば解ける、いかにもABCのB問題、って感じのやつですね。

常に全部比較する必要はなくて、手前にある山で最も高い山との比較さえすればよいというところが肝要。

C - Coloring Colorfully

これは塗り替えた後の状態は偶数番号白/奇数番号黒か偶数番号黒/奇数番号白の二通りなので、両方にかかる手数をそれぞれ計算して、少ないほうが答えです。

こういう解法が浮かんでくるあたり、だいぶ競プロに慣れてきてるのかなぁと思ったり思わかなったり。

私の回答 : https://atcoder.jp/contests/abc124/submissions/4944713

実装中にも、もうちょっと効率よくできると思ってはいましたが、うっかりREとか出さないように紛れのない実装にした、つもりです。

D - Handstand

最終的に通しましたが、1REと2WAはだめですね。

実装の方針は

010011100

こういうのを、状態ごとにカウントした配列に落として

1, 1, 2, 3, 2

k の数に応じて和を取って、最も大きいものを答えとする、というもの。 たとえば上記の例でK=1なら

2, 6, 5

なので答えは6、 K=2なら

7, 8

なので答えは8、という具合。

カウントした配列の偶奇、最初が0なのか1なのか、あとKの数と0の区間の大小関係で細かい場合分けが必要な実装になってしまったのですが（そのへんのコーナーケースの不備がRAやWAの理由）、もっと効率のいい実装があるんでしょうね、きっと。（←まだ公式解説配信前）

追記

公式解説によると、0 or 1の切り替わる位置を記憶すればよいとのこと、たしかにそれだと無駄に和を取る必要がないですね。

あとは二分探索やしゃくとり法でも解けるとのこと。しゃくとり法は、確かに言われてみればそりゃそうだなー。

まとめ

しゃくとり法は、まだトレーニングしていないのでやらねば・・・。

なにはともあれ初の全完は嬉しいですね。方針がわりとすぐ浮かぶようになってきているのは大きいと感じます。

f:id:mdstoy:20190413230219p:plain

次回予告、「緑になるまでにしたこと」乞うご期待。（うそ）

AtCoder Beginner Contest 123

AtCoder competitive programming c++ ABC

目標は達成した。フラグはへし折った。

でも、結局3完なんですよねぇ・・・。

あと、

結局全部C++でやりました。考え方が重要で、実装は簡素で済む問題ばかりでしたので。

各問題

A - Five Antennas

直接 通信ができないアンテナの組が存在するかどうか判定してください。

  • できないものが一つでもあれば通信できないということ
    • 最大の座標と最小の座標の距離だけ見ればいい
      • それが通信できれば、他の組み合わせももちろん通信できる
        • 全てそれ以下の距離しかないから
      • 通信できなければ、一つ存在するので判定終了

A問題にしては頭を使わされたような気が・・・。

B - Five Dishes

正直に言いまして、最初順番関係ないんじゃないの？って思ってました。注文が完了したら終わりだと勘違いしていたので。 しかし、出力例2を見て勘違いしていたことと、正しい答え（一の位が小さいものを最後に選ぶ）がわかりました。そこはまったく自分で考えていません・・・。

まあコンテストではそういう解き方もときにはあるということで。

C - Five Transportations

これも、しばらく考えていたら突然答えが降ってきました。最大のボトルネックにのみ輸送量は影響されるんですね。 それさえわかれば簡単、なのですが、人数が輸送量で割り切れるときの処理を誤るという極めて初歩的なミスで1WAだしてしまいました。（TLEは出さなかったというのに・・・。）

D - Cake 123

うーん、正しく枝狩りする方法が思いつかなかったです。これから解説みて勉強します。

まとめ

とりあえず愚直に実装してみるのも重要と悟りました。そこから気づくこともあるはず・・・。

f:id:mdstoy:20190406230844p:plain

AtCoder エクサウィザーズ 2019

AtCoder Java competitive programming

C問題、解けそうで実はそうでもなかった。

各問題

A - Regular Triangle

最初、問題文を流し読みして、三平方の定理使うのか面倒くさいなぁ、とか思ったんですけど全然そんなことはなかった。 正三角形だから、三辺が全て等しいかどうか判定するだけでしたね。

B - Red or Blue

元の文字列から"B"か"R"かどちらか一方を消去して（私の場合JavaなのでString#replaceを使う）元の文字列長と消去後の文字列長を比較すればOK、という方針でやったのですが、テストが通らない。

よく見たら、ちょっとブログに書くのをはばかられるような信じられないバグを埋め込んでました。

この問題が簡単すぎてみんな当たり前に早解きしているので、これだけで順位800位分くらいロス。どうやら最初からバグ無しで最速提出できていたら青パフォで今回緑到達だったようです。つらい・・・。

C - Snuke the Wizard

条件を見たら、さすがに愚直に実装したら時間がいくらあっても足らないのはわかります。500点問題ですしね。 で、クエリ系は後ろからというセオリー？に則って考えて、端から狭めていけばいいんじゃないの？という方針で実装。 入力例は通るので提出するも、半分ほどWAが出る・・・。

しばらく考えて、潰す前に逃げられてたらだめじゃん！ということに気づきましたが、どこまで逃げられているかを管理する方法がわからず、ここでタイムアップとなりました。

D - Modulo Operations

B問題まで終わった時点でCDE問題を一通り見ましたが、D問題は今の自分にはできないやつと悟ったのでスルー。

E - Black or White

これもD問題と同じくスルー。

まとめ

初級者にとっては完全に早解き大会でしたね。つまらないバグで時間をロスしたのが本当に悔やまれますが、それもまた実力ですね。

f:id:mdstoy:20190330235534p:plain

とりあえず緑にはなっておきたい。

AtCoder Beginner Contest 122

AtCoder Java competitive programming ABC

f:id:mdstoy:20190324230708p:plain

安定のTLEよ・・・。

各問題

A - Double Helix

単純にif, else ifを並べました。

1分台(1:43)でAC出たのでよし、と思っていたのですが、これでもちょうど300番目だった模様。厳しい。

B - ATCoder

N <= 10 なので、全部見ればいいわ楽勝楽勝と思っていたら、まさかのWA。最後の一個だけがWAだったので、境界値バグかなと思ってよく見たらそのとおり、入力が一文字のみときが見事にすっぽ抜けてました。on_

C - GeT AC

まず、各クエリごとに文字列を全部捜査するというゴミみたいなロジックを書いて無事TLEをもらいました。 次に、文字列捜査部分を、"AC"をreplaceAllでぶっこ抜いてもとの文字列との長さの比較で答えを出すというロジックに変えて、引き続きTLEをもらいました。

そういうことじゃないから俺！

で、これは"AC"を探すのは最初に一回だけやっておけということだなということにようやく気づき、"AC"が出現した位置を最初に覚えるようにして、各クエリごとに、"AC"が出現した位置が範囲内に含まれるかどうかを「全部」確認するように書き換えたところ、三度TLEをもらいました。

ちょっと考えて、全部チェックしなくても範囲外の部分だけわかればいいよね、ということに気づき、ようやくACがとれました。

https://atcoder.jp/contests/abc122/submissions/4695870

解説によると、これは累積和を使うとよかったんですね・・・。

追記 (2019-03-25)

せっかくなので累積和を求める解法で解き直してみました。

https://atcoder.jp/contests/abc122/submissions/4707780

私が最初に通したコードとくらべて、笑えるくらいシンプルかつ速く動作するコードになりました。

D - We Like AGC

解説にあるような、末尾がこれこれだとそれ以上は続かない、みたいなのがおぼろげにはわかったのですが、そもそもちゃんとわかってないし、わかったとしてDPを実装もできなさそうなので今の所だめです。

まとめ

  • 提出してWAだすくらいならローカルでちゃんとテストしよう
    • 境界値とか
    • 大量データとか
  • 文字列を大量にゴリゴリ捜査・操作するのダメ！絶対！
  • DPもっとやりこんでいこう

f:id:mdstoy:20190324235616p:plain

ぐいっと伸びているように見えるけど、これは二日連続開催だからですねｗ