Toy と帽子と ADP BE

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

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

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

AtCoder Grand Contest 032

AtCoder Java competitive programming AGC

祝、400点問題初AC!!!

各問題

A - Limited Insertion

最初、よくわからなかったので、とりあえず出力を入力の配列に戻すプログラムを書いてみました。 そのコードと処理の過程をなぞるうち「あ、これ逆算すればいいんじゃね？」と気づきました。

ここまではよかったのですが、私の拙い実装力では最初はTLEしてしまう全探索コードしかかけませんでした。

いろんな枝狩りの方法をうなりながら考えていたのですがさっぱり思いつかず、手元でいろんなテストデータを作って考えているうちにようやく

「あ、これ数字の大きい方がinsertionするための条件が厳しい（操作の後の方にしか入れられない）んだから、大きい数を優先すればいいのでは」

「優先っていうか、操作しうる最大の数だけ相手にすればいいのでは？」

ということに気づき、条件を追加してACできました。

https://atcoder.jp/contests/agc032/submissions/4673376

試行錯誤のなごりでメモ取ってますけど、この方針だと不要ですね。

B - Balanced Neighbors

手元でいろいろ書きなぐってみたがさっぱりわからず・・・。

C - Three Circuits

公式の解説にあるような、次数6や次数4が鍵になることは私でもすぐわかったのですが、時間的にも知識的にも能力的にも今回はそこ止まり。

まとめ

400点問題がコンテストで初めてACできたので今回は満足。

明日のABCは気合い入れていこう。

f:id:mdstoy:20190324001208p:plain

AtCoder Grand Contest 031

AtCoder Java competitive programming AGC

はじめてのAGCは0完5WAでした。on_

各問題

A - Colorful Subsequence

226 で無事死亡しました。

それにしても、これ本当に200点なんですか？！

まとめ

場合の数を一から勉強し直さないとだめですね。

f:id:mdstoy:20190317005519p:plain

AtCoder Beginner Contest 121

AtCoder Java competitive programming ABC

各問題

A - White Cells

算数の問題。しかも問題に

なお、残る白色のマス目の数は行や列の選び方によらないことが証明できます。

って親切に書いてくれています。

B - Can you solve this?

公式解説は二次元配列を作るといいでしょうとされていて、確かにその方が思わぬミスは減るのでより安全だと思います。

ただ、状況にもよりますが、個人的に二次元配列を作る方が混乱することがあるので、こういうのはループ中に入力を取りたい派だったりします。

https://atcoder.jp/contests/abc121/submissions/4517069

C - Energy Drink Collector

ソートはあるけど、B問題っぽい？

お店を金額の安い順にソートする必要があるので、先ほどと同じように二次元配列で混乱しないようにしたくてわざわざクラスを定義しました。

https://atcoder.jp/contests/abc121/submissions/4520837

ぬるいっちゃぬるいですが、まあそこまで時間を気にするようなレベルでもないので、今の所、このへんは読みやすさ重視で書くようにしてます。 あと、long にするのは忘れなかったです。えらいｗ

追記

ていうか、こういうペアを扱うときは(Tree)Map でよかったというお話。 ただし、Mapを使う場合はキーが重複するときどうするかを考慮する必要がありますね。

せっかくなので、TreeMap版も実装して提出しました。

https://atcoder.jp/contests/abc121/submissions/4531121

D - XOR World

結局約半数が WA で完答できず。

https://atcoder.jp/contests/abc121/submissions/4527933

うーん、へんてこな実装ではありますが、これで通るものもあれば通らないものもあるのがなぜなのか・・・。 とりあえず a = 0 のときだめっぽい？なんか法則が崩れる条件がある？それとも単に実装の問題？

ともあれ、XOR のような頻出問題で公式解説にあるような性質をうまく見つけたり使いこなしたりできないとつらいですね。

まとめ

C問題まで順調に解けたし、D問題も提出には至ったのでよし。

なにより、色が付いたので今回はよし！

次の目標は緑で。

f:id:mdstoy:20190309232812p:plain

AtCoder Beginner Contest 120

AtCoder Java competitive programming ABC

各問題

A - Favorite Sound

公式の解説どおり。

B - K-th Common Divisor

概ね公式の解説どおり。なのですが、min(A, B)じゃなくて、何をとちくるったかmax(A, B)としていました・・・。 YouTube解説では単に100とされていて、計算量に対した影響はないからまあいいか、というふうに言われていたので、まあいいか、って感じです。（いいのか？）

C - Unification

最終的に公式の解説どおり。

ですが、初めはまともに解こうとしてTLE連発してしまいました。

そこで我に返って冷静に考えてみて、これ消費されずに0と1が両方残ってしまうことはありえなくないか？ってことに気がついたのでした・・・。

AtCoder、そういうのもあるのか・・・。

D - Decayed Bridges

後ろから順に繋げていく、差分更新していく、という考えにはたどり着きました。 しかし、肝心の連結情報をどう作ってどう保存するのかがまったくわからなくてタイムアップ。

UnionFind木というのを使うんですねー。ほふー。

課題など

  • 考え方一つで、恐ろしくシンプルに実装できるタイプの問題もAtCoderにはある
  • データ構造
    • 今回はUnionFind木

感想

C問題のダメージがあまりにも大きい。on_ 次は、次こそは茶色に到達するということでどうかひとつ。

f:id:mdstoy:20190303232840p:plain