Toy と帽子と ADP BE

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

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 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

AtCoder Beginner Contest 119

competitive programming AtCoder Java ABC

2回目の参加の結果は2完。

あああああ、ってなってましたが、パフォーマンスも順位も初参加の前回より上がっていたので、今回はC問題の難易度が高かったということでいいんですよね？ね？

各問題

A - Still TBD

単に、月の部分を引っこ抜いて4以下かどうかで判定しました。 解説PDFでは"2019/04/30"との文字列比較が解説されていて、たしかにそのほうが速いですね。（業務ではやりませんけどね・・・。） ともあれ、A問題でも学びがある。

https://atcoder.jp/contests/abc119/submissions/4367304

B - Digital Gifts

これは問題をそのままコードに落とすだけ。さすがに。

https://atcoder.jp/contests/abc119/submissions/4368946

C - Synthetic Kadomatsu

どうやって「うまいこと」探索するんだろう？うーんわからん、と思ってすぐにD問題に移ってしまいました。 PDFとYouTubeの解説によれば、最大8本の竹に対して「Aに使う or Bに使う or Cに使う or 使わない」を単に全探索すればよかったとのこと・・・。 それぞれの竹がどれに使われるかって発想ができなかったので、そもそもだめです。

D - Lazy Faith

スタート地点から二分探索して、寺→神社の順と神社→寺の順で近いものを探せばいいんじゃないの？東西と目的地の組み合わせで最大8通り計算するだけじゃないの？ と思って実装していたのですが、間に合わず。

PDFとYouTubeの解説によれば、考え方は合っていた模様。要するに実装力が酷すぎるということ。あああああ。on_ この問題は落ち着けばさすがにできた気がします・・・。もったいなかった。

課題

  • 全探索
  • 慌てずにコードを書く

感想

得るものはいろいろあったので、まあよしということで。 次回の目標は茶色に到達、で。

f:id:mdstoy:20190225001544p:plain

AtCoder Beginner Contest 118 (AtCoder 始めました)

AtCoder competitive programming Java ABC

主に、なんか面白そー、っていう理由でAtCoderを始めることにしました。あと、トレーニングっていうかリハビリっていうか、とにかくコードを考えて書くための動機がなんか欲しかったということもあります。

で、自分が何を考えて回答のコードを書くに至ったのか参照できるようにしておくと後で役立つかもと思って、ブログに思考を落としておくことにします。いわば積極的に恥を晒していくスタイル。

あと、Javaでやります。（当面の間は） Javaで競プロは正直面倒ですし、時間をいくらでもかけていいならよりエレガントにかける言語は他にもありますが、現状ではトータルで考えてJavaが圧倒的に早く書けるので仕方がない・・・。

各問題

A - B +/- A

https://atcoder.jp/contests/abc118/submissions/4279713

条件をただコードに書き下しただけ。

B - Foods Loved by Everyone

https://atcoder.jp/contests/abc118/submissions/4282069

食べ物ごとに好きと答えた人の数をカウントし、そのカウントが回答人数と一致したものを数えたら、それが答え。

C - Monsters Battle Royale

https://atcoder.jp/contests/abc118/submissions/4290804

最終的にACに至った回答は

  • 一番小さい数で他の数すべてをオーバーキルにならないように攻撃する
    • このときの最終結果は、他の数に対して一番小さい数で剰余を計算すると求まる
  • これを生存者が一人になるまで繰り返す

というロジック。

なんでこんなロジックになっちゃったかというと、最初に思いついたロジックが

  • 一番小さい数で二番目に小さい数を「一回」攻撃する
  • ひたすらそれを繰り返す

というもので、それを TLE にならないように修正した（だけ）だからです。

最初の回答 : https://atcoder.jp/contests/abc118/submissions/4283717

あと、確実にループでなめられるようにするためにソートかけてるんですけど、多分ちょっと考えたらソートいらなくなりそう。 ていうかソートに頼っている時点でだめやん？

D - Match Matching

未提出

C問題のTLEがなかなか振りほどけず、考える時間がほとんどありませんでした。

ちなみに問題を見て思いついたロジックは。

  • 1があるとき
    • 本数が偶数のとき
      • 1を並べる（完）
    • 本数が奇数のとき
      • 7があるとき
        • 7のあと1を並べる（完）
      • (7がなくて)5があるとき
        • （次は4本の4だが、これは偶数だから考えなくていい）
        • 5のあと1を並べる（完）

（以下省略）

のように、使用本数が少ないものから考慮していくというものでしたが、これだと必要本数の多い数だけが用意されているケースで分岐が大変なことになりそうなので、いずれにせよ色んな意味でだめでした。

感想

競プロで必要な考え方に慣れていかないと、話になりませんね。 とりあえずDPをちゃんと勉強せねば。

まずは色がつくところを目標にがんばります。

f:id:mdstoy:20190217010618p:plain

2018 年を振り返る

misc.

あんまりこういうことしないですけどね。まあ今年は大きなイベントが二つあったので。

2018 年の大イベント

その一　退職

会社をやめました。

mdstoy.hatenablog.com

退職はしましたが、色々あって次に所属する会社は未だに決まっておらず、派遣社員で食いつないでおります。

可及的速やかに次の仕事を見つけねばなりません。見つけねばなりません。

その二　JJUG CCC で登壇

東京で登壇してきました。

mdstoy.hatenablog.com

単発では終わらぬよう、今後も努力していきたい所存です。

幸いなことに、今自分が本当にやりたいことはおぼろげながら見えてきました。

というわけで

2019 年はまず転職活動を全力で、そして、本当にやりたいことをはっきりと見据えることをまず目標にぼちぼちやっていきたいと思います。