Tenka1 Programmer Beginner Contest 2019 参加レポート with Nim-lang

AtCoder の Tenka1 Programmer Beginner Contest 2019 に参加したレポートです。
使用言語は当然 Nim。

要約

問題

Tenka1 Programmer Beginner Contest 2019

結果と感想

A, B しか通せなかった。
D に関しては通せなくても良いかな。
C を通せなかったのは単に私の実力不足という感じ。
「どうして思いつかなかったのか」という気持ちではあるのだけれども、思いつかない実力なのだから飲み込むしか無い。
このあたり、ゆっくり経験を蓄えて行きたいところ。

一応全て解いて Gist にしたので御覧ください。

解答

前回に引き続き Gist で。

レポート

遅刻

21:10 着席。
この時点でやる気の無さが分かる。
(1 週間ぶり 2 回目。コレで全問通せていないのだから今回は悔やんでどうぞ。)

A, B

書くだけ。(いつもの)

C - Stones

与えられる文字列を
.……
という文字列に変換するためには、いくつの文字を変換すればよいか。
という問題。

冷静に考えれば O(n) なのだが、なんだか O(n^2) の回答しか頭に思い浮かばなかった。
文字列をなめるときに持っておく変数を 1 つ (今までに見た . の数) 増やせば O(n) になることに気づかなかったのは単純にアホ。
しかし、まあこういうことも初心者ならではということで許してもらおう。
次回からはこういうミスでコケないようにしたい。

D - Three Colors

解説は自分で問題からタブの「解説」に行って読んでください。

一言で言うと、「組み合わせって怖い」

単純に解けなかった。
数え上げ問題は結構 DP を使って解きがちですよ、というのを知らないというところからスタート。
めっちゃ計算量の多いコードを書いて、そもそも書き終えることができずにコンテストが終了した。

DP の作り方に関しても、こいつは結構工夫が要るっぽい。
友人と話しながらとりあえず解けるコードを書き終えたが、いまいち理解しているか怪しいため、もう一度しっかり確認したい。

Nim の int の扱いについて

input:

import math

echo 3^1000
echo 3^1001
echo int.high

output:

6203307696791771937
163179016665764195
9223372036854775807

マジ? 手元環境ではオーバーフローで落ちるんだけど。version の違いヤバイ。

という記事を書いたんですが、どうも、こいつ assert で落としているみたい。
なので -d:release だと無視されます。
……どっちにしても、このあたり気をつけて演算しないといけないっすね。
オレオレ mod タイプを定義し始める時代が来てしまったかもしれない。

まとめ

  • 簡単な文字列に対する考え方テクを身に着けていきましょう。
  • 数え上げは DP で。
  • Nim で mod が絡む演算をするなら細心の注意を払え→いやもうなんか作ろう。

おまけ

D の AC 一覧

  • もしかして: Nim って遅い?
  • もしかして: Nim じゃなくて私のコードが遅い?
  • ということで: 今度調べたり聞いたりします。
2019/04/20