ABC 初参加 (2019/04/13) レポート with Nim-lang

AtCoder の ABC に初参加したレポートです。
日記程度のもので、誰かの参考になる気は全くしていない。
使用言語は当然 (?) Nim。

参加のきっかけ

大体以下の通り。

  • 就活していて、プログラミングの能力を示す値と、プログラミングに対するモチベーションが欲しくなった
    • なお、前者に関しては手遅れな気がする
    • この目的の場合は Nim で書くのは愚策な気もする
  • 最近の ABC の問題の writer が友人なので、色々聞けそう

要約

問題

ABC124

結果と感想

とりあえず 4 問正解。
多分ここで得られるモノは本質的なものよりも競技プログラミングの経験かなと思った。
素人なので知らない事はそのうち出てくるでしょうけれども。
ABC には一応、後数回お世話になって、解けるようなら先に進もうという感じ。

ただ、ABC 以外でも通用するような実力を持ち合わせていないのは分かっている事なので、知識だけでもためておきたい。
ということで、蟻本を読み始めた。
この本は上記の友人との間に微妙に面白い曰くがあるので、そのうち話したい。

ABC に関しては正直記事を書くほどの事は無いだろうという感想だが、自省のために書く。

解答

自分の最終的なコード置いてあると、そのうちなるほどを得られそうなので Gist へ。
一応 Nim だとこう書く (というか書ける?) んですよ、という例にはなっていると思う。

レポート

遅刻

21:10 着席。
この時点でやる気の無さが分かる。

A - Buttons

問題を読んで頭に疑問符が沢山浮かぶ。

あなたは、いずれかのボタンを押すことを 2 回行います。

って何よ。え? n 回じゃないの? みたいな。
ABC の A 問題っていうのはこういうものらしい。

書くだけみたいなやつ。

B - Great Ocean View

問題を読んで(ry

書くだけ。

C - Coloring Colorfully

与えられた文字列を x 箇所書き換えて
0101010

1010101
にしろ。x の最小は? という問題。

問題の通り、与えられた文字列と上記 2 つの書き換えの回数を数えて、小さい方を返せば良い。

この辺りから自分が競技プログラミングに慣れていないという醜態が顕になる。
最初から上みたいに書いてある訳じゃないのが競技プログラミングなんですね。
まあ現実の問題って全部そうなのですが。
「えー、なんか巧いやり方あるの? どういう問題なんだー?」
と考えながらトイレに立った。
トイレの中で
「バカにしてんのか!!」
と気づく。

この辺りは簡単と言ってなめてないでパターンゲーをちゃんと記憶していくことが大事なのかな?
苦手な作業だけど、難しい問題になったときにこの辺ミスると悔しくて死ぬので、まあゆっくりやって行きたいですね。

D - Handstand

111000010101100
みたいなのから k(given) 箇所の 0 の塊を 1 にできる。
1 を最大いくつ並べられるか。
という問題。

解き方は解説を見たら分かるやつです。
私的には別に難しくないけど、どうやって実装するのが良いのかとか言われると黙り始めるという感じ。

私は

  • 1 と 0 の塊の長さをそれぞれ数える
  • 連続した k 個の 0 を埋めたらどうなるかを左からなめる。

で解いた。

解答曰く、0 か 1 が始まるインデックスだけ持っとけばいいよねとのこと。
まったくもってその通りですね。

合計 2 回落とした

  • なんか良くわからない実装を初めてしまって 1 回落とす。
  • k 個も書き換えるところ無いよーというコーナーケース想定して無くて 1 回落とす。

ハイ。お恥ずかしい。
後者はまあ、急ごうと思ってしまったのが悪いということにできるけど、前者はよろしくない。
原因としては、とにかく速いコードを書けるなら書きたいと思ってしまったこと。
この辺り、ちゃんと自分のアルゴリズムの計算量を考えられて、どのくらいの時間で実行が終わるかを概算できるようになると変わるのでしょうね。
まあ、好成績者のコードを見ていると私がやろうとしていたことが綺麗に実装されて要るのですが。

次、私のコードが必要ないことを結構しているお話。
最速のコードと私のコードで 200 倍くらい速さが違ってきています。
私のコードが無駄なことをたくさんしているのは分かったので、次回から気をつけて行きたい。

まとめ

  • ABC、思っていたよりも問題が簡単でびっくりする。
  • 自分の書いたアルゴリズムの計算量オーダーを見積もれるようにならなきゃ今後辛そう。
  • 場合分けが地獄になる答えはできるだけやめましょう。
  • アルゴリズムが頭の中で完成する前に手を動かし始めるのをやめましょう。
  • 今回は紙を使わなかったが、コンテスト前に用意しようね。
  • D 問題、文字列を同じ数の 0 の塊をはさみながら長さを調べれば良いの、なんとなく覚えておこう。

おまけ

別の人の答え

163 行目。
このマクロは笑った。
最近マクロ職人みたいなこともやっているので (patty にコントリビュートしたり、nimly 作ったり) そのうち自分用マクロ定義する日は来るかもしれない。

2019/04/14