Tenka1 Programmer Beginner Contest 2019 参加レポート with Nim-lang
AtCoder の Tenka1 Programmer Beginner Contest 2019 に参加したレポートです。
使用言語は当然 Nim。
要約
問題
結果と感想
A, B しか通せなかった。
D に関しては通せなくても良いかな。
C を通せなかったのは単に私の実力不足という感じ。
「どうして思いつかなかったのか」という気持ちではあるのだけれども、思いつかない実力なのだから飲み込むしか無い。
このあたり、ゆっくり経験を蓄えて行きたいところ。
一応全て解いて Gist にしたので御覧ください。
解答
前回に引き続き Gist で。
| import strutils, sequtils | |
| let | |
| abc = stdin.readline.split({' '}).map(parseInt) | |
| a = abc[0] | |
| b = abc[1] | |
| c = abc[2] | |
| if (a < c and c < b) or (b < c and c < a): | |
| echo "Yes" | |
| else: | |
| echo "No" |
| import strutils, sequtils | |
| let | |
| n = stdin.readline.parseInt | |
| s = stdin.readline | |
| k = stdin.readline.parseInt | |
| sk = s[k - 1] | |
| var | |
| ans = "" | |
| for c in s: | |
| if sk == c: | |
| ans = ans & c | |
| else: | |
| ans = ans & "*" | |
| echo ans |
| import strutils, sequtils | |
| let | |
| n = stdin.readline.parseInt | |
| s = stdin.readline | |
| var | |
| sp = 0 | |
| dt = 0 | |
| rds = 0 | |
| rdd = 0 | |
| for c in s: | |
| if c == '.': | |
| inc(dt) | |
| else: | |
| inc(sp) | |
| var mn = dt | |
| for c in s: | |
| if c == '.': | |
| inc(rdd) | |
| else: | |
| inc(rds) | |
| let nw = dt - rdd + rds | |
| if mn > nw: | |
| mn = nw | |
| echo mn |
| import strutils, sequtils, math, tables | |
| proc powMod(n, m, by: int): int = | |
| if m == 0: | |
| return 1 | |
| else: | |
| return (n * powMod(n, (m - 1), by)) mod by | |
| let n = stdin.readline.parseInt | |
| var | |
| dp, dpn: Table[int, Table[int, int]] | |
| sm = 0 | |
| sa: seq[int] = @[] | |
| ret = 3.powMod(n, 998244353) | |
| #echo ret | |
| dp = initTable[int, Table[int, int]]() | |
| dpn = initTable[int, Table[int, int]]() | |
| dp[0] = initTable[int, int]() | |
| dpn[0] = initTable[int, int]() | |
| dp[0][0] = 1 | |
| dpn[0][0] = 1 | |
| for i in 1..n: | |
| let a = stdin.readline.parseInt | |
| sa.add(a) | |
| sm = sm + a | |
| dp[i] = initTable[int, int]() | |
| dpn[i] = initTable[int, int]() | |
| for k in dp[i - 1].keys: | |
| # for all | |
| dp[i][k] = (dp[i - 1][k] * 2 + (if dp[i].hasKey(k): dp[i][k] else: 0)) mod 998244353 | |
| dp[i][k + a] = (dp[i - 1][k] + (if dp[i].hasKey(k + a): dp[i][k + a] else: 0)) mod 998244353 | |
| #echo "----" | |
| #echo ret | |
| #echo sm | |
| #echo dp[n] | |
| #echo dpn[n] | |
| for k in dp[n].keys: | |
| if k * 2 >= sm: | |
| ret = (((ret - dp[n][k] * 3) mod 998244353) + 998244353) mod 998244353 | |
| if k * 2 == sm: | |
| for i in 1..n: | |
| for ik in dpn[i - 1].keys: | |
| if ik * 2 > sm: | |
| continue | |
| let a = sa[i - 1] | |
| # for not | |
| dpn[i][ik] = (dpn[i - 1][ik] + (if dpn[i].hasKey(ik): dpn[i][ik] else: 0)) mod 998244353 | |
| dpn[i][ik + a] = (dpn[i - 1][ik] + (if dpn[i].hasKey(ik + a): dpn[i][ik + a] else: 0)) mod 998244353 | |
| ret = (ret + dpn[n][k] * 3) mod 998244353 | |
| echo ret |
レポート
遅刻
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 が絡む演算をするなら細心の注意を払え→いやもうなんか作ろう。
おまけ
- もしかして: Nim って遅い?
- もしかして: Nim じゃなくて私のコードが遅い?
- ということで: 今度調べたり聞いたりします。