notepad.exe

つまり覚え書き

ABC104 D - We Love ABC

AtCoder アルゴリズム D問題

解説を見ながら少しでもかみ砕こうとした記録

D - We Love ABC

ABC104 D - We Love ABC

全ての文字列のABC数の合計を求める問題

DPを使って解く
何らかの組み合わせの最大値や総数を10^{9} + 7で割った余りを求めるなどはDPを使う問題と連想できそう

今回の問題でのDPの考え方は「S の先頭から i − 1 文字目までに対する処理（? の置換と丸つけ）をすでに 行っていて、これまでに丸を j 個つけている場合の、S の残りの部分に対する処理を行う方法の個数」で、

  • j < 3で「次に丸を付けるべき文字or?」なら数え終わっている文字の次の文字に組み合わせの数を引き継ぐ
  • j = 3で「?」ならABCのどれでもいいので一つ前の組み合わせに3をかけるそうでなければ前の組み合わせを引き継ぐ

をDPすればよさそう

コード中の計算で

dp[i][j] = dp[i+1][j] * (s.charAt(i) == '?' ? 3L : 1L);

が3つ選び終わっていて今の対象の文字が「？」であればそれまでの組み合わせのすべてに「A, B, C」のいずれかをくっつけれるので3倍するところ。

if(j < 3 && (s.charAt(i) == '?' || s.charAt(i) == "ABC".charAt(j))) {
    dp[i][j] += dp[i+1][j+1];
}

ここが例えば2個つけていたら対象の文字が「A」または「？」のようにABC数を作れるかどうかで加算しているところ。

提出コード(写経しただけ)

ABC104参加記録

AtCoder アルゴリズム

久しぶりにCで苦戦した回でした。

AtCoder Beginner Contest 104

A - Rated for Me

どのコンテストでレーティングが変化するか求める問題

  • 1200以下ならABC
  • 2800以下ならARC
  • それ以外ならAGC をif文で書いて出力すると解けます。

提出コード

B - AcCepted

入力された文字列が条件に当てはまるかチェックする問題

  • S の先頭の文字は大文字の A である。
  • S の先頭から 3文字目と末尾から2文字目の間（両端含む）に大文字の C がちょうど1個含まれる。
  • 以上の A , C を除く S のすべての文字は小文字である。

S の先頭の文字は大文字の A である。

この条件は1文字目がAでない時にWAを出力するだけ

S の先頭から 3文字目と末尾から2文字目の間（両端含む）に大文字の C がちょうど1個含まれる。

  • 文字列全体からCを空文字に置き換えたとき
  • 3~(末尾-2)文字目までの中でCを空文字で置き換えたとき

この二つをやってどちらも置き換え前と文字列の長さが１文字だけ違えば途中にCが一つだけあることがわかる。

以上の A , C を除く S のすべての文字は小文字である。

上記二つの条件に当てはまっている段階で先頭にA, それ以外にCが一つだけあることがわかっているので、 この二つを除いた残りが全部小文字であるかループして調べれば答えがでます。

提出コード

C - All Green

解くべき問題を最小にする問題
全部解くとボーナス点がついて処理が増えるので、最初に全部解く点数を決めてしまいます。

全部解く問題の組み合わせは最大でも 2^{10} = 1024通りなので全探索しても問題なさそうです。 全部解くと決めたものの得点をすべて足して点数が足りればその時も問題数を記録します。

すべて足りて点数が足りないときはすべて解くものではないものの中で点数が一番大きいものを何問か解く。 何問か解いて点数が届くのであればその時の問題数を記録する。 もしその点数を全部解いてしまうのであれば別の組み合わせのことを指しているのでこの時は無視します。

上記の二つの条件で記録されている問題数のうち最小のものが答えとなります。

アルゴリズム的にはbit全探索 + Greedyです。 本番中はbit全探索の部分で詰まってしまったので精進不足ですね…

提出コード

D - We Love ABC

本番中にほとんど手を出すことができなかったので省略

勉強会でお話したサイトの紹介

【サポーターズ勉強会】ゼロから始める競技プログラミング

こちらの勉強会でお話したサイトの紹介です
supporterzcolab.com

AtCoder

URL: https://beta.atcoder.jp/

日本語で競プロができる楽しいサービス。

AtCoder Problems

URL: http://beta.kenkoooo.com/atcoder/

AtCoderのコンテストと問題の一覧を見ることができます。
ユーザ名を入力すれば精進の記録として活用できます。

[Qiita] AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～

URL: https://qiita.com/drken/items/fd4e5e3630d0f5859067

何をすればいいかこれを見ればまとまっています。

[Qiita] AtCoder 版！蟻本 (初級編)

URL: https://qiita.com/drken/items/e77685614f3c6bf86f44

上記の記事と合わせて読むといいです。

AIZU ONLINE JUDGE

URL: https://onlinejudge.u-aizu.ac.jp/home

チュートリアルに使うもよし、実装の練習に使うもよしのサイトです。

Hacker Rank

URL: https://www.hackerrank.com/

コースがあるのでそれに沿って勉強できます。