Yuulis.log

トンネルを抜けるとそこは参照エラーであった。

【AtCoder】AtCoder Beginner Contest 380 - 参加記 | 茶コーダーが解くAtCoder

AtCoder コンテストまとめ ABC プログラミング

コンテスト時間: 2024-11-16(土) 21:00 ~ 2024-11-16(土) 22:40 (100分)

A - 123233

Difficulty:16

解答時間: 2:10

6桁の正整数が与えられるので、この整数が以下の条件を全て満たすか判定せよ。
- $N$ の各桁のうち、 $1$ は丁度1つである。
- $N$ の各桁のうち、 $2$ は丁度2つである。
- $N$ の各桁のうち、 $3$ は丁度3つである。
$N$ を文字列として受け取り、全走査しながら1, 2, 3の個数を数えていけばよい。

B - Hurdle Parsing

Difficulty: 27

解答時間: 2:45

長さの正整数列から、次のように文字列を生成した。生成された文字列が与えられるので、正整数列を復元せよ。
1. $S =$ |と初期化する。
2. の順に、次の操作を行う。
  - $S$ の末尾に-を $A_i$ 個追加する。
  - $S$ の末尾に|を1個追加する。
$i = 2$ から $S$ を見ていき、 $S_i =$ |となるまでカウンターを増やし、それを出力していく。その後、カウンターを初期化する。

C - Move Segment

Difficulty: 223

解答時間: 36:16

0, 1のみからなる長さ $N$ の文字列 $S$ が与えられる。 $S$ の中で先頭から $K$ 番目の1の塊を、 $K-1$ 番目の1の塊の直後まで移動した文字列を出力せよ。
とりあえず $S$ をランレングス圧縮して、0と1の塊が全体の塊の何番目にあるかを2つの配列に持っておく。
1の塊を出力する際にカウンターを増やしていき、カウンターが $K-1$ のとき $K$ 個目の1の塊を出力する。
合計3つのインデックス管理をしなければならず実装に時間がかかってしまったが、よく考えると1の塊の前後は必ず0の塊なので、 $K-1$ 個目の1の塊の次は0と1の塊をswapしてやればよいことになる。

D - Strange Mirroring

Difficulty: 849

解答時間: 32:21

英文字からなる文字列 $S$ が与えられる。 $S$ に以下の操作を $10^{100}$ 回繰り返すとき、全ての操作を終えた後の $S$ の先頭から $K_i \: (i = 1, 2, \cdots, Q)$ 文字目をそれぞれ求めよ。
1. まず、 $S$ の大文字を小文字に、小文字を大文字に書き換えた文字列を $T$ とする。
2. その後、 $S, T$ をこの順に連結した文字列を新たな $S$ とする。
各操作ごとの $S$ を書き出していくと、以下のようになる。
1. $S$
2. $S | T$
3. $ST | TS$
4. $STTS | TSST$
5. $STTSTSST | TSSTSTTS \cdots$
これを最後から再帰的にさかのぼっていくことを考えると、以下のような再帰関数f(文字列 s, インデックス k, 文字列の長さ l)が構築できる。なお、flip(x)は文字列の大文字小文字を反転したものを示す。
1. $l = |s|$ のとき(ベースケース)、 $s_k$ を出力する。
2. そうでないとき、として、
  - $K \lt l$ のとき、f(s, k, l)を呼び出す。
  - そうでないとき、flip(f(s, k - l, l))を呼び出す。
$s_k$ が区切り線の前後どちらにあるかで場合分けするイメージ。

結果

Performance: 995

Rating: 673 → 710 (+37) Highest更新！

緑も見えてきた。