2022-08-07

128. AtCoder参加記録（AtCoder Beginner Contest 263）

プログラミング AtCoder

先週は体調不良のためお休み。

32回参加でレート 1336 です。

今回はパフォーマンス 1495 です。

ABCDを通して、FGExは未解答です。Eは通せず。

各問題の思考過程など。

A

問題

3分22秒。

制約の文どういうこと…？と思いましたが、あんまり関係なさそうなので気にしないことにしました。

Dictionary で枚数を保持して判定しましたが、なんか無駄に複雑になったような気もします。

ACコード

B

問題

3分13秒。

$i \rightarrow P_i$ の有向辺を張って、 $N$ から辿って $1$ に辿り着いたときの深さが答え。

ACコード

C

問題

5分35秒。

辞書順に順列を生成するのはライブラリ化していたので、これを少し調整して狭義単調増加列のみ生成するようにしました。

ACコード

D

問題

13分34秒。

すぐには分からなかったので、入力例 1 を書き出して考えてみる。
貪欲に考えてみるが、ちょっと無理そう。
$x$ と $y$ 両方あるのが厄介なので、 $x$ だけ考えてみる。
全部 $L$ に置き換えてみて、各項の差分を考える。 $x$ を決めた時の総和への影響は、差分の累積和（ $c_i$ とする）によって $O(1)$ で求められる。 $y$ についても同様。
$y$ が決まっているなら、最適解は $\displaystyle \min_{1 \le i \le N - y}c_i$ である。これはセグメント木で $O(\log N)$ で求められる。
あとは $y$ を全探索すれば $O(N \log N)$ で間に合う。

ACコード

E

問題

初回提出51分44秒。解けず。

最初20分くらい考えていた方針は破綻してそうだったので、EDPCの似た問題を思い出し、解き方がすぐ思い出せなかったので解説記事を読む。これと同じことをすればよさそう。
$dp[i] := i にいるとき N へ辿り着くまでにサイコロを振る回数の期待値$ とすると、 $\displaystyle dp[i] = 1 + \frac{1}{A_i + 1}dp[i] + \frac{1}{A_i + 1}\sum_{j=1}^{A_i}dp[i+j]$ 。
式を整理して $\displaystyle dp[i] = \frac{A_i + 1}{A_i}\left( 1 + \frac{1}{A_i + 1}\sum_{j=1}^{A_i}dp[i+j] \right)$ 。
総和計算で TLE しそうだが、ここは累積和なりで何とかなりそう…だけど、ゴチャってきたので一度投げてみる。

…と、これで提出してみると、TLE の他に RE が出る（WA は出なかった）。最大ケースでやってみると、まさかの StackOverflow。再帰のメモ化忘れでもない。

どうも自作のライブラリがダメだったらしい。

（以下、Upsolve）

何故か有理数ライブラリを使っていたけど、翌朝冷静に考えると必要なかった…。再帰でやると逆にややこしかったので、 $dp[i]$ を考える時 $dp[j] (j \gt i)$ は評価済みであるという性質を利用し、逆順でDPテーブルを更新してAC。

Upsolveコード

F, G, Ex

見てないです。

Dまでがとても順調だったので温まりましたが、E解けなかったのは悔しいですね。期待値DPはまだまだ身についてない感が強いです。

2022-07-23

127. AtCoder参加記録（AtCoder Beginner Contest 261）

プログラミング AtCoder

31回参加でレート 1316 です。

今回はパフォーマンス 1258 です。

ABCDEを通して、FGExは未解答です。A, Bでそれぞれ1ペナ。

各問題の思考過程など。

A

問題

初回提出3分34秒、そこからACまで2分37秒。

何故か気が向いて、カッコよく分岐だけで解こうとしてしまいました。案の定バグらせたので素直にループ回して数え上げました…。

ACコード

B

問題

初回提出8分39秒、そこからACまで1分44秒。

「誰が誰に勝ったのか」「誰が誰と引き分けたのか」を辞書で持って全探索しました。もっと賢いやり方はあったと思いますが…。

実装をバグらせて1WA。やっぱり変に実装長くなる解法は避けたい…。

ACコード

C

問題

3分38秒。

C# は文字列の一致判定を $O(1)$ で行えるとみなしてよく、辞書のキーとしても持てるので、普通にループ回してやればよいです。本当にやるだけでした（なんでC問題？）

ACコード

D

問題

7分28秒。

最近DPばかりやってたので、すぐ見えました。

$dp[i, j ] := (i 回コイントスした直後にカウンタが j であるときの貰えるお金の合計最大値)$

状態数は $O(N^2)$ 、連続ボーナス判定は予め辞書を持っておけば $O(1)$ でできて、各回遷移は表裏2状態しか取らないのでこれでOK。

初期状態は $dp[0, 0] = 0$ で、それ以外 $-\infty$ で初期化しておきます。 $-\infty$ 以外の状態から配るDPをして、 $i$ 回連続ボーナスを $B_i$ とすると、

表の場合: $dp[i + 1, j + 1] = \max(dp[i, j] + X_{i+1} + B_{j + 1})$
裏の場合: $dp[i + 1, 0] = \max(dp[i, j])$

答えは $\max_{j}(dp[N, j])$ 。

ACコード

E

問題

71分33秒。ギリギリで解けたのは良かったですが、時間使いすぎ～～～

初め60分近く考えていた方針は、「操作 $1$ ～操作 $i$ の結果を事前計算して、ループごとにこの値を使って演算する」でした。ところが、結合則の成り立たない演算が混じっているのでかなり大変で、実装してみたもののそもそもサンプルが合いませんでした。というか、後ろから先にやって大丈夫なのかあんまり自信が無かったです。

サンプルが合わない時点でこの方針は間違っているな…と思い、半ば諦め気味でしたが、ふと「ビット演算はビットごとに独立して考える」という言葉が浮かび、急に解法を閃きました…。

あるビットが操作 $1$ ～操作 $i$ によって変換される結果は常に等しい
各ビットは高々2状態しか取らず、操作対象の数も高々30ビット。
各位置のビットについて、 $0, 1$ それぞれが操作 $i$ まででどのビットに変換されるか保持しておく。このメモ変数自体はループを通して保持し、操作の適用はループごと1回ずつ行う。
ループごとに、 $X$ の各ビットがどちらになっているか確認して、先ほどのメモからどのように変換されるか確認する。その後、そのビットから数を再構成する。

思いついたのが終了10分前とかで、かなり焦りながらバグらせつつ実装しました。なんとか終了1分前に入力例1の合う実装になって、この解法なら1つ合えば他も大丈夫なはずとぶん投げてAC。

ACコード

F, G, Ex

見てないです。

Bまで遅すぎ・ペナ出しすぎで良くなくて、Dはかなり早くてOK、Eは…変な方針に固執しすぎちゃイカン、という感じでした。ここのところ調子よくないですね…。

2022-07-17

126. AtCoder参加記録（AtCoder Beginner Contest 260）

プログラミング AtCoder

30回参加でレート 1323 です。

今回はパフォーマンス 1582 です。

ABCDを通して、EGExは未解答です。Fは通せず。

各問題の思考過程など。

A

4分15秒。

何とでも実装できますが、Dictionary を使ってやりました。問題の制約に対して無意味に実装が複雑化したので、あんまり良くなかったかもです。

B

6分25秒。

制約が小さいので書かれている通りにやればOKです。HashSet と OrderByDescending や Where を使ってゴニョゴニョやりました。業務コードっぽい。

C

6分34秒。

シミュレートしてみると、結局、変換できるだけ変換するのが最適だと分かります。なので、愚直シミュレートすればよいです。

レベルごとに赤い宝石の数リスト、青い宝石の数リストを作っておきます。レベル $N$ からスタートして、降順に宝石を変換していきます。同じレベル・同じ色の宝石はまとめて変換します。最後にレベル1の青い宝石の数を出せばOK。

D

9分44秒。

表向きで見えているカードの数字とその山にあるカードリストを管理する Dictionary、表向きで見えているカードの数字を管理する MultiSet を用意して、後は適当に実装すればOKです。計算量は $O(N \log N)$ 。

E

解けず。全然方針が立たなかったので、飛ばしてFを考えていました。

F

解けず。この解法では間に合わないだろうと思いつつ投げましたが、案の定TLE3回でした。

問題文をよく読むと、「 $V_2$ のある2頂点で $V_1$ のある同一2頂点と接続している頂点は存在するか？」ということだと理解
$V_2$ 側が小さいので、ここを二重ループで回してよい
あとは、 $V_2$ から取り出した2頂点それぞれと接続している頂点を見て、共通するものが2つ以上あればOK…だけど、この計算をどうやっても対数や定数時間に落とせない
BitSet が少し頭をよぎったが、これやったところで $O(ST^2)$ が64倍高速化されるだけなので無理だな…と諦め
間に合わないとわかりつつ適当にごまかした実装で投げたが、やっぱりTLE

G,Ex

見てないです。

Dまでは（自分としては）やるだけの問題でしたが、実装が重かったからか思った以上にパフォーマンスが出ました。ちょっと業務っぽい感じでしたね。

今日は重い実装でも落ち着いてコーディングできたので良かったです。E, F 解けなかったのであんまり競プロ感無かったですが…。

昨日と合わせて -5 なので、現状維持という感じです。やっぱり青は遠いな…。

2022-07-16

125. AtCoder参加記録（AtCoder Regular Contest 144）

プログラミング AtCoder

29回参加でレート 1289 です。

今回はパフォーマンス 886 です。久々に大失敗。

Aを通して、BDEFは未解答です。Cは通せず。

各問題の思考過程など。

A

11分29秒。

問題文が難しい。とりあえず $M$ を最大化することを考えてみる。 $x$ を2倍したときに繰り上がりが発生するとダメそうな雰囲気。ということは、使えるのは 4 までの数字。 $x$ を最小化したいのだから、桁数をなるべく削りたいので 4 で埋められるだけ埋めて余りは先頭にくっつける…で良いのか？

と考えて、証明できないですがそれっぽいので投げてみると通りました。もう少し早く投げればよかった。

B

解けず。

貪欲法で色々考えていましたが、どうやっても上手く行きませんでした。解を二分探索とか全く発想できなかったので、今回は解けない問題に分類されるものでした。1時間くらい使ってしまったのが非常に勿体なかったです。

C

初回提出108分52秒。解けず。

辞書順なので何らかの貪欲法を考える
$K$ 項めまでは $A_i = i + K$ で埋めていくのが最適。
これを考えると、 $\displaystyle \left \lfloor \frac{N}{K} \right \rfloor \le 1$ であるときは解を構成できない。
$A_{K+1}$ はなるべく 1 にしたいので、 $K + 1 \le i \le N$ は $A_{i+K}$ に持っていきたい。これが無理になったら $A_{i-K}$ に埋めていく。こんな感じの貪欲法？

手元で考えたテストケースは通ったので投げてみましたが、半分ほど落ちて残念な結果に。解説を読むとそこそこ近いところまで考察できていたようなので、もう少し時間があれば通っていた可能性が高いです。早くBを捨てればよかった。

D, E, F

見てないです。

取捨選択が下手だな～、と悔やまれる結果でした。2ヶ月ぶりに緑パフォを取ってしまいました。ARCはいったん問題文全部見ておいた方がいいですね…。

2022-07-09

124. AtCoder参加記録（AtCoder Beginner Contest 259）

プログラミング AtCoder

28回参加でレート 1328 です。

今回はパフォーマンス 1348です。

ABCEを通して、GExは未解答です。D, Fは通せず。Cで1ペナ、Eで1ペナ。

各問題の思考過程など。

A

5分9秒。

いつもと違って問題文を読むだけでは状況整理が困難だったので、数直線を使って考えました。0歳のときの身長を出して、そこから逆算するような方法を取りました。

B

4分53秒。

回転行列適用するだけか…これ中高生可哀想な問題では、と思いつつ、ラジアン変換周りで何故かバグを埋めたりで若干時間がかかりました。悲しい。

C

初回提出4分35秒、そこからACまで2分20秒。

ランレングス圧縮して色々考えればよさそう。

圧縮後のリストサイズが異なっていればNG
そうでない場合、順番に圧縮後の要素を見ていって
1. 文字の種類が異なればNG
2. 連続数が等しければ次の要素を見に行く
3. $S$ 側の連続数が1なら操作できないのでNG
4. $S$ 側の連続数が $T$ 側より多ければ、減らすことはできないのでNG（ここで 1WA）
ここまでNGが出てなければOK

D

初回提出6分16秒。5WA で正答に至らず。

円の交差判定は「円の内側にすっぽりはまっている」「円同士が交差している」「それ以外」を見ればOK。各円同士を見るのも $O(N^2)$ で十分。あとは、円同士が同じ連結成分に属していればよいので Union-Find でくっつけていけばよい…と分かってはいましたが、誤差にやられました。

冷静に考えると、2乗距離で判定すると浮動小数点数を避けられたんですね…。というか、いつもならこちらで考えていたのに何故か今日は sqrt を使ってしまいました。無念。

E

初回提出22分50秒、そこからACまで5分40秒。

LCMがどのようになるか考察すると、すべての $p_{i, j}$ について $e_{i, j}$ の最大指数を採用したものの積になります。つまり、ある $i$ について $a_i = 1$ に書き換えたならば、 $a_i$ を構成する素数の指数が先ほど考えた最大指数と等しければ、LCMは変化します。ただし、厳密には他の $a_j (i \ne j)$ で、同じ素数について最大要素がある場合はそれが残るので、その素数については変化しません。

以上より、まずはこの前計算を行います。

各 $p_{i, j}$ について、 $\max e_{i, j}$ と、 $e_{i, j} = \max e_{i, j}$ であるような要素数 $c_{p_{i, j}}$ を求める。
各 $p_{i, j}$ について、HashSet $S_p$ に $p_{i, j}$ を追加する。
$c_{p_{i, j}} \ne 1$ である $p_{i, j}$ は $S_p$ から除去する。

あとは、「何種類あるのか？」の判定ですが、指数の変化する素数集合の種類数を見ればよいので、Zobrist-Hash を使うと楽です。

HashSet $S_{ans}$ を用意する。
を走査する
1. ハッシュの集合 $S_h$ を用意する。
2. を走査する
  1. $S_p$ に $p_{i, j}$ が含まれる、かつ、 $e_{i, j} = \max e_{i, j}$ であれば、 $S_h$ に $H(p_{i, j})$ を追加する。ここで、 $H$ はハッシュ関数。
3. $S_h$ の Zobrist-Hash を $S_{ans}$ に追加する。
$S_{ans}$ のサイズが答え

とても単純なバグを埋めてしまって 1WA。

F

Dを通せないのでこちらも見ていました。

直感として、重みの大きい順に貪欲に取っていけばよいのでは…？と書いてみるとサンプルは通ってしまう。そんなに簡単なはずがないと思いつつ提出すると、案の定落ちまくる。後から考えると例外パターンが作れたので、残り時間的にも間に合わないと断念しました。

G, Ex

見てないです。

なんか全体的に遅くて、Dも通せていなくて…う～ん、という感じです。E で Zobrist-Hash を使えたのが気持ちよかったです。しょうもないバグで 1WA 出しましたが…。

2022-07-03

123. C# でBitSetを自作した話と、C# の定数倍高速化について少し

プログラミングデータ構造

昨日の ABC258-G問題で BitSet という（C++の）データ構造を利用する想定の問題が出ました*1。

atcoder.jp

BitSet は、MultiSet と同じく C# には（似たようなものはありますが）存在しないデータ構造です。C++だと通るらしい愚直解は通らなかったので、この問題でテストしつつ BitSet をライブラリ化することにしました。

BitSet とは

ざっくり言えば、BitFlag を bool ではなく long（64bit 整数）で保持し、ビット演算を駆使することで64倍高速な処理を実現するデータ構造です。やや大げさですが、 $10^2$ ループ弱計算量を落とせると考えるとそれなりに効く場面があるかもしれません。

C# における BitSet

C++ の BitSet と完全に一致した API を持つデータ構造はありませんが、C# には BitArray という同じようなデータ構造があります。BitArray ではビット演算はサポートされていますが、フラグの立っている数をカウントする Count の API が存在せず、やや不便です。

そこで、C++ と同じような API を持つ BitSet クラスを自作することにしました。

実装

先ほどの問題の AC コードに貼り付けています。シフト演算は未実装です。

各演算は自分で考えて書いているので、もう少し効率のよい書き方があるかもしれません。すべての演算についてランダム値を用いたテストを通しているので、正確性はあると思います。

atcoder.jp

定数倍高速化の話

これを書いている中で、今まで少し気になっていた定数倍高速化周りについて知見が得られたので共有しておきます。

class と struct どっちが速い問題

C# の class はヒープ、struct はスタックにインスタンスが生成されます。この関係で速度面ではわずかに struct が有利とされているのですが、struct は値渡しがデフォルトになるなど扱いに注意が必要な面もあります。

インターネットを検索してみてもどちらが良いかは諸説あり、結局どうなんだろうというのをこの問題で試してみました。

こちらが class 版の結果で、こちらが struct 版の結果です。ざっくりまとめると、以下のような結果になりました。

class 版の実行時間に対する struct 版の実行時間の割合
- 最大値: 110%
- 最小値: 94%
- 100%未満のケース率: 89% (25/28)
- 平均値: 97%

悪化する場合もありましたが、9割弱のケースで実行時間が削減され、削減された実行時間の平均は 3% でした。実行時間の減少だけでいうと、2498ms が 2349ms に削減（-149ms）したものが最も大きかったです。

以上のことから、今回のケースは struct の方が有利でしたが、決定的な差にはならないと結論付けました。とりあえずライブラリは struct にしておこうと思います。

Linq 重い問題

Count の計算に Linq を使った場合、TLE が発生して通せませんでした。これを通常のループでインデックスアクセスに置き換えるだけで通るようになりました。

こちらが Linq を使った版、こちらが通常のループに置き換えた版です（双方114行目から）。ざっくりまとめると、以下のような結果になりました（Linq 版で TLE したケースはまともな比較ができないので除外しています）。

Linq 版の実行時間に対する通常ループ版の実行時間の割合
- 最大値: 121%
- 最小値: 58%
- 100%未満のケース率: 86% (12/14)
- 平均値: 73%

ケース率だけ見ると微妙な気もしますが、TLE 分を除いて14ケースしか比較できてないのでここはあまり気にしない方が良いかもしれません。注目すべきは平均値で、3割弱ほど実行時間が削れています。

以上のことから、ループ内で Linq を利用するのは避けた方が無難と結論付けました。なんでここまで遅くなっているのか分かりませんが…。

*1:C++だと愚直解も通ってしまったようですが…

2022-07-02

122. AtCoder参加記録（AtCoder Beginner Contest 258）

プログラミング AtCoder

27回参加でレート 1325 です。

今回はパフォーマンス 1626 です。

ABCDEを通して、FExは未解答です。Gは通せず。Eで2ペナ。

各問題の思考過程など。

A

1分56秒。

$K \lt 60$ であるかで場合分けしました。ゼロ埋め出力の方法をググるのにやや時間がかかりました（いつも忘れる…）。

B

8分10秒。

「ん、貪欲法か？難しくない？」と思いましたが、よくよく考えると「開始地点・進む方向」で全探索が十分間に合いました。最大10桁で 64bit 整数の範囲内には収まるようになってます（これがはみ出てたらもう少し厳しかった）。

進む方向の種類数を $\sigma$ として $O(\sigma N^3)$ 。

C

5分5秒。

クエリ 1 によって何が起こるかを考えると「末尾の $x$ 要素がそのままの順番で先頭へ追加される」と言い換えられます。よって、順番は変わらず文字列の開始地点が変わるということなので、「開始地点」を保持してそれを適当に操作すればいいです。

計算量は $O(Q)$ 。

D

5分45秒（Eを解いてからの経過時間）。

初め2分ほど考えて「DPか？」と思いましたが、 $X$ が大きすぎるので違う。さっぱり方針が立たないので、一旦無視することにしました。

Eを解いてからもう一度考察して、すぐに解けました。

新ステージは順番通りにしか遊べない。今まで出てきたステージを繰り返し遊ぶのならば、「ゲームプレイ」が最短のものを遊び続けるのが明らかに最適。ということは、「ステージ」を進めていく中でこの2択をシミュレートし続ければ $O(N)$ で間に合う。
ステージを頭から順番に走査する。とする。
番目のステージについて、
1. 今までプレイしてきた総時間、 $\displaystyle t = \sum_{j = 1}^{i}(A_j + B_j)$ を計算する。総和計算は、実際には前の結果を保持しておきループごとに $O(1)$ で行う。
2. $m \leftarrow \min(m, B_i)$ とする。
3. あと $y = X - i$ 回遊ぶ必要があるので、 $ans \leftarrow \min(ans, t + my)$ として答えを更新していく。
4. $y = 0$ ならループを終了する

E

初回提出39分18秒、そこからACまで15分13秒。

考察も実装も重い。

（周期メモを作るパート）

$i$ 番目の芋から箱詰めを始める場合、必ず同じ状況が再現される。ということは、周期性を使う問題。以降、芋のインデックスは $\pmod N$ で考える。
$i$ 番目の芋から $j$ 番目の芋（ $i \gt j$ の場合もある）まで詰めた場合の重さ合計は、累積和を2つ連結しておけば $O(1)$ で計算できそう。 $W$ の2重累積和を $\displaystyle C_i$ とする（ただし、 $C_0 = 0, 0 \le i \le 2N$ とする）。
$k$ 番目の箱に詰められる芋の個数を管理するリスト $L$ 、芋の開始インデックス → 箱のインデックスを記憶する Dictionary $d$ を用意する。 $i \leftarrow 0, s \leftarrow 0$ とする。
$i$ が $d$ のキーに含まれるならループに入っているので、 $s \leftarrow d[i]$ として終了（箱のループ開始地点を表す。これをやってなくて入力例2 が合わず、10分以上悩んだ）。
$i$ 番目の芋から箱詰めする際、何個芋を使うのか高速に求めたい。まず、 $N$ 個の芋をすべて使う場合を考えて、 $n = \left\lfloor \frac{X}{C_N} \right\rfloor N$ 個使うことが分かる。
次に、ここからはみ出た分（ $w = X \pmod{C_N}$ ）を充填する芋の数を考える。ただし、 $w = 0$ ならこの処理は行わない（ここで色々バグらせて 2WA）。
愚直に求めると間に合わないので、累積和に対して二分探索で $C_j - C_i \ge w$ を満たす $j$ を見つけて、 $n \leftarrow n + (j - i)$ とする。
$d[i] \leftarrow |L|$ として、 $L$ に $n$ を追加し、 $i \leftarrow j$ とし、4. に戻る。