2022-06-25

121. AtCoder参加記録（AtCoder Beginner Contest 257）

プログラミング AtCoder

26回参加でレート 1285 です。

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

ABCDを通して、EFGExは未解答です。Cで1ペナ。

各問題の思考過程など。

A

1分47秒。

愚直にやっても十分間に合うと判断したので、問題文の通りにやりました。

B

8分21秒。

初め「一番右のコマは動かさない」と誤読していました…。各コマがどの位置にあるか保持しておけば愚直にシミュレートするだけで良いです。誤読やバグらせがあって妙に時間がかかってしまいました。

C

初回提出15分7秒、そこからACまで3分54秒。

初め数分、答えで二分探索する方針を考えてしまいました…。最近覚えたことが出てきてしまう病。

体重の昇順で並べておく
大人の合計人数を数えておく
「体重 → 正しく判定できた人数」の Dictionary を用意する
順番に見ていって、Dictionary を更新していく（同じ体重の人がいる場合は新しい値で更新）
1. 「ここまでに出てきた子供の人数」と「大人の合計人数からここまでに出てきた大人の人数」を引いたものが正しく判定できた人数
Dictionary の Value の最大値が答え

$X$ は実数を取れるので、間が $1$ しか空いてないパターンなどは考えなくてもOKです。また、このアルゴリズムだと全員大人だった場合の最適判定ができないので、「体重0 → 大人の合計人数」を最初に Dictionary へ追加しておく必要があります（1WA）。

ソートに一番時間がかかって $O(N \log N)$ 。

D

45分56秒。遅すぎる…。

ジャンプ台 $i$ と $j$ のマンハッタン距離を $d(i, j)$ として、ジャンプ台 $i$ から $j$ への移動に必要なジャンプ力は $\displaystyle \left\lceil \frac{d(i, j)}{P_i} \right\rceil$ 。これをコストと捉えると、完全有向グラフが見える。

ここから、25分くらい考えていた方針。よく考えたらこの方針でも解けたかも…？

コスト降順に並べて、入次数が 0 になる頂点が現れるまで削っていき、最後に削った辺のコストが答えでは？
色々実装をバグらせたものの、結局正しい答えは出て来ない。そもそも、始点は任意に選べるので、入次数が 0 になる頂点が 2 つ現れた時点でアウトか…。これを修正しても正しい答えは出ない（何かバグらせていた？）

ここで、「始点は任意に選べる、そこから任意の頂点へ遷移できる、経由するコスト最大値を最小化したい…」という状況を改めて考える。すると、「これワーシャルフロイド法に状況似てるな…」と気付く。制約的にも $O(N^3)$ が通るのでこれが想定解では？

ワーシャルフロイド法の最小コスト更新を $c(i, j) \leftarrow c(i, k) + c(k, j)$ から $c(i, j) \leftarrow \max(c(i, k), c(k, j))$ に変える
得られたコスト行列から、始点 $i$ について終点 $j (i \ne j)$ へのコストの最大値をそれぞれ出して、それらの最小値が答え（ABC255-B問題みたいな処理）

E

4完に75分かかった時点でかなり諦めがあって、「貪欲法でいけそう…」と解法を整理していたところで終了となりました。

F, G, Ex

見てないです。

難しい回ではありましたが、流石に解くの遅すぎ・バグらせすぎでした。ABCはきちんと思考がまとまってない状態でコードを書き始めてしまう癖があって、それが仇となった気がします。ある程度紙上で考えて、確信を持ってからコードを書く練習が必要そうだな…と思います。

今の自分は、おそらく十分青パフォを狙える武器が揃っているのですが、その使い方が下手な状態です。この段階では解ける問題を増やすより、早く解く練習をした方が良いかもしれないと思いました。

2022-06-20

120. AtCoder参加記録（AtCoder Regular Contest 142）

プログラミング AtCoder

25回参加でレート 1292 です。

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

ABCを通して、DEFは未解答です。Aで2ペナ。

各問題の思考過程など。

A

初回提出8分18秒、そこからACまで14分43秒。

コーナーケースに自力で気付きましょう問題。

$K$ の末尾が 0 の場合は不適なので答えは 0。それ以外で、 $K$ を「そのまま」「ひっくり返した」数列それぞれの末尾に 0 を 0 個以上追加した数が $x$ の候補。高々12桁なのでこれを全探索すればよさそう。
$K$ について、「ひっくり返した」方が小さくなる場合は答えは 0 になることに気付いていなかった（1WA）
$K$ が回文的な数列になっている場合、重複してカウントしていた（1WA）

合計 2WA でした。もう少し注意深く行きたかったです。

B

23分59秒。

色々考えるものの、筋の良い解き方が見えない。でも、NG条件が厳しいのでそんなに難しくはないはず？とりあえず、「作った盤面が条件を満たすか？」を判定するデバッグ用の出力を追加。
こういう問題は最終的に簡単な答えになりがちなので、思いついた法則で適当に盤面を作ってみる。すると、「順番に並べたものから、奇数列目とその右の数を入れ替える」で、なんか通りそうな雰囲気。
$N = 500$ でも問題ないことを確かめたので、デバッグ出力を消して提出、無事AC。

これでいいのか…？という感じですが、まぁそういう問題だったのかもしれないです。

C

49分9秒。

細かいところを詰めるのが大変な問題。

①と直接つながっている頂点を見つける（クエリ）
1. 直接つながっている頂点が無ければ、②が単独で直接つながっているので $1$ が答え
①と直接つながっている頂点たちと②の距離を尋ねて、その最小値（とする）と個数を見る（最大クエリ）
1. $d \ne 2$ なら、その頂点を経由するのが最短ルートなので $1 + d$ が答え
2. $d = 2$ かつ、そのような頂点が 2 個以上あるなら、①と②は直接つながっている（①経由で距離 2 になるパターンしかない）ので $1$ が答え
以降、 $d = 2$ かつ、そのような頂点が 1 個だったとする（ $V$ と表現します）。ここまで、 $(N - 2) + 1 = N - 1$ クエリであることに注意。
今から考えるのは、「②は①と直接つながっているのか、そうでないのか？」です。
②と直接つながっている頂点を見つける。と直接つながっていることはない（そうであればになる）ので、それ以外の個について尋ねる。ここまでクエリ。
1. ここで、そのような頂点が無ければ、①と②は直接つながっている（かつ、②に子がいない）ことが分かるので $1$ が答え
先ほど求めた頂点から 1 つを適当に取る。その頂点と①、その頂点ととの距離を尋ねて、①からの方が近いなら、そうでないならが答え（2 クエリ、合計クエリで終了）
1. これは、②が①の子になっているのか、 $V$ の子孫になっているのか調べています

状況整理が甘く、5. の判定をどうすれば良いのかで20分くらい悩みました。テスト方法もよく分からなかったので、書き上げて即投げしてめでたくAC。

D, E, F

見てないです。

久々のARCでしたが、青パフォですしいい感じの戦果でした。A や C をもう少し上手く切り抜けたかったですが、まぁ実力相応でしょう。状況整理もっと素早くできるようになりたいですね。

2022-06-18

119. AtCoder参加記録（AtCoder Beginner Contest 256）

プログラミング AtCoder

24回参加でレート 1245 です。

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

ABCDEを通して、FGExは未解答です。Eで2ペナ。

各問題の感想など。

A

50秒。

256と掛けた問題？普通に計算すればOK。

B

4分17秒。

単純にシミュレートすればOK。駒を進める時は逆順に走査するとバグりにくいです。

C

10分39秒。

左上から $2 \times 2$ マスが決まれば残りのマスは和の情報から算出できます。よって、この4マスについて全探索すればよいです。計算量は $M = 30$ として $O(M^4)$ 。

若干バグらせて3分ほど時間取られました。

D

6分16秒。

図を書いて考えると、ああこれ imos 法だな…とすぐ分かりました。左 +1、右 -1 として、最後に累積和を取るフェーズで 1 以上になっている連続した区間が求めるものです。

E

初回提出13分1秒、そこからACまで38分16秒。

入力例を見て、「最もヘイトを買わない人から順に配っていけばよいのでは？」と直感。ただ、あまり証明は見えませんでした。とりあえずそのように実装してみるとサンプルは合うので投げてみる。半分以上 WA で、一旦撤退しました。

そこからしばらくFを考えていて、Eへ戻ってきたときに「配るたびに "最もヘイトを買わない人" って変わるやん」と気付く。PriorityQueue に突っ込んで、配った人がヘイトを持つ人の分だけ減らして…とやるが、PriorityQueue は一度取り出してもう一度突っ込む必要があったことに気付く（ここで 2WA 目）。仕方ないので MultiSet に変更して、1800ms とギリギリで通せました。

F

パッと見てまた遅延セグ木かな、と思い、とりあえず $D$ がどのように $A$ で表されるか算出しました。ただ、一律同じ値の変動になるわけではないので、これどうするんだろう…といろいろ考えましたが、結局いい方法は浮かびませんでした。

実際難しかったみたいですね。お気に入りに入れていた人誰も通せていなかった…。

G, Ex

見てないです。

今日はコンディション的には問題なく、Dまではかなりいいスピードで解けていました。Eを通せないままFに悩んで、時間経過でパフォ溶かしたのが勿体なかったなー、と思いますが割と結果論な気がしています。

2022-06-11

118. AtCoder参加記録（AtCoder Beginner Contest 255）

プログラミング AtCoder

23回参加でレート 1231 です。

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

ABCDを通して、FGExは未解答です。EはTLE、Cで1ペナ。
今日全体的に難しかった（というより実装が大変だった）ですね。

各問題の感想など。

A

1分50秒。

特に言うことなし。

B

9分47秒。

Bとしてはそこそこ難しいのでは…？
明かりを持っている人・持っていない人に分類して、「明かりを持っていない人」それぞれについて持っている人への最短距離を出します。これらの最大値が答え。

全探索で十分間に合います。なんかバグらせてて無駄に時間を食いました…。

C

初回提出9分13秒、そこからACまで2分0秒。

対象となる等差数列の最小値と最大値を出しておきます。これは $O(1)$ でできます。 $X$ がこの最小値以下、最大値以上なら差を出すだけです。考えるべきは間にあるときです。 $(X - \min A) / D$ とすれば、どの項とどの項の間に $X$ が位置するのか分かるので、近い方との差を出せばいいです。これも $O(1)$ で出せます。

$D \lt 0$ のパターンでバグるコードになっていて 1WA。

D

23分7秒。

$A$ の順番に意味は無いので、昇順に並べておきます。 $X$ に対して必要な操作回数は、 $A$ の各要素と $X$ の差の絶対値の総和です。これを定数～対数時間で行う、という問題と読み替えられます。

こう考えると、 $A$ の総和と $XN$ の差で求まるのでは？と思ってしまいそうですが、実際は差を取る順番が逆になるケースがあるので上手く行きません。ここは、二分探索で $X$ がどの位置にいるか判定して、自分以下の要素、自分より大きい要素で差を取る順番を変えればいいです。その範囲での総和を知りたいので、累積和配列を作って $O(1)$ で取得します。

以上、 $O(Q \log N)$ ですが、これもバグらせまくって無駄に時間が掛かりました。

E

初回提出23分0秒。

$A_i$ を 1 つ定めればすべての項が芋づる式に出てきます。最適な状態ではラッキーナンバーが何処かにあるのが必要条件なので、ラッキーナンバーのある位置とラッキーナンバーの種類で全探索すればよいのでは？と思いました。ここまで $O(NM)$ です。

あとは、上の条件でラッキーナンバーがいくつあるのか、という計算を $O(1)$ で行えばいいのですが、本当に何故か分からないのですが普通に $O(N)$ の処理を書いていて当然 TLE しました。脳がバグっていた…。

ここから、判定を定数時間で行えないか考察。いろいろ数字を変えてみると、適当に定めた $A$ と、ひとつ項を定めた場合の奇数番目・偶数番目の項の変動は、定めた項と定めた数列における該当項の差に依存して固定だと気付きました。そのため、適当に $A_1 = 0$ みたいに定めて各数が何個あるかカウントしておき、判定フェーズで足したり引いたりした数の個数を出せば $O(1)$ で出来る…と考えて、ずっとバグらせていました。

入力例 2 が合わなかったので提出せず終了。

F

一瞬見ましたが、通りがけ順の定義を読むのが面倒だったので、まだ考察が進んでいたEの方に賭けました。

G

一瞬見ましたが、「禁じ手」の数が多すぎてちょっと今の自分には無理そう…と思ったので逃げました。

Ex

見てないです。

普段の練習でもそうなのですが、最近妙にバグらせることが多くて今日のABCも不安がありました。案の定バグらせまくっていてちょっとダメでした。

解法は見えるし考察から間に合うことも分かってるのですが、何故か細部を詰め切るのが下手になっています。短期間に集中しすぎている系の症状な気がするので、ちょっと意識的に競プロから離れた方がよいかもです。

この一週間は、問題を解くペースを少し下げてみようかなと思います。

2022-06-05

117. AtCoder参加記録（AtCoder Beginner Contest 254）

プログラミング AtCoder

22回参加でレート 1225 です。

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

ABCEを通して、FGExは未解答です。DはTLE、Eで1ペナ。

各問題の感想など。

A

1分16秒。

ゼロ埋め出力の方法をググるのが面倒だったので、string で取って出力しました。

B

4分36秒。

見た目難しいですが、書いてある通りに実装すればよいです。

C

8分42秒。

発想でしかない問題。Cにしては難しくない…？と思いましたが、通してる人数を見るとそうでもなさそうでした。

バブルソートみたいな処理ができるのですが、観察すると入れ替えられるのはインデックスを $K$ で割った余りが等しい箇所のみだと分かります。逆に、そのような箇所であればバブルソートと同じ操作なので、自由に入れ替えられます。

よって、まず昇順ソートして各要素が $K$ の剰余インデックスに何個あるかカウントした後、元々の数列の剰余インデックスを求めて先ほど求めた数を引いていき、上手くいかない箇所があれば No、最後まで上手く行けば Yes となります。

最初のソートがボトルネックで、計算量は $O(N \log N)$ 。

D

最初の提出まで34分7秒。

難しい…。色々やりましたが、結局 TLE は取れませんでした。早く E へ行くべきでした。

E

初回提出23分21秒、そこからACまで2分19秒。

制約に「与えられるグラフの各頂点の次数は 3 以下」「 $0 \le k_i \le 3$ 」という非常に怪しいものがあるので、これに注意します。

入力例の図を書いて考えてみます。 $0 \le k_i \le 3$ なので、ある頂点から距離 3 以内の頂点のみ見ればよいです。これは幅優先探索をすればよいだけです。各頂点の次数は 3 以下なので、高々 39 本の辺しか見ることはないです（ $3 + 9 + 27$ ）。ということは、すべての頂点についてこの操作を行っても $O(39N)$ の計算量となり、間に合いそうです。

ただ、若干定数倍が重そうなので念のため実行時間制限を見ると、やや長めになっています。つまりこれが想定解っぽいです。

というわけで、予め各頂点について距離 3 までの頂点番号の総和を求めておき、クエリが来たらここから $O(1)$ で返答することにしました。

初回提出は距離 3 で幅優先探索を打ち切るのを忘れていて、メモ用配列の範囲外アクセスで RE でした。

F, G, Ex

見てないです。

今日はなんだか心がざわついており、あまり集中できない回でした。全体的に難しかったということもありますが…。

Dに固執してしまったのが最大の反省点。詰まったときにEも少し見ていたのですが、チラ見したときは $0 \le k_i \le 3$ の制約に気付いていなくて「こんなのどうやれば良いんだ」となっていました…。早く D を切るべきだった。

前回がたまたま簡単だっただけで、今回は最近の難易度が戻ってきたなー、という感想でした。次の目標は青パフォ安定ですが、まだまだ遠そうです。

2022-05-29

116. AtCoder水色になりました

プログラミング AtCoder

昨日の AtCoder Beginner Contest 253 で無事入水できました。

実は、参加当初からコンスタントに緑パフォくらいは取っていたので、成長が明確に色へ反映されたのは今回が初めてになります。というわけで、色変記事というのを書いてみようと思います。

読んでくれる方の為になりそうな精進方法あたりの内容を先において、自分語りは後においておきます。

精進方法について
- 戦略的に解く問題を選択する
- 解いてきた問題
  - 1～2ヶ月目
  - 3～4ヶ月目
  - 5ヶ月目～
- 問題との向き合い方
メンタル的な話
- レートは気にしすぎない方がいい
- 自分に合ったコンテスト参加環境
水色までに習得した知識など
- 以前から利用（理解）していたこと
- AtCoderを始めてから理解したこと
自分の経歴など
- 競技プログラミングについて
- 嗜好について
- 学力について

2022-05-28

115. 【入水】AtCoder参加記録（AtCoder Beginner Contest 253）

AtCoder プログラミング

21回参加でレート 1221 です。水色になりました！

今日はとりあえずいつもの記録用記事を書いて、入水記事はまた別に書こうと思います。

今回はパフォーマンス 1701 です（自己ベスト）。

ABCDEFを通して、GExは未解答です。Eで2ペナ。

各問題の感想など。

A

1分32秒。

やり方は色々あると思いますが、ソートして真ん中の値と $b$ を比較する方法にしました。

B

3分22秒。

マンハッタン距離を出せばOKです。

C

10分43秒。

Dictionary で各値がいくつ含まれているかと、MultiSet でキーを昇順・降順それぞれ保存していい感じに実装します。

D

7分17秒。

包除原理の簡単なやつを使う問題。

「1～Nの和」から、「Aの倍数または Bの倍数」の数を引けばいいです。

E

初回提出15分17秒、そこからACまで7分51秒。

$dp(i, j) := (長さ i、最後の要素が j となる条件を満たす数列の数)$

として DP。最小ケースで範囲外アクセスすることに気付けず、無駄に2ペナ。これはもったいなかったです。

F

53分30秒。終了28秒前の提出…！

色々考えましたが、最終的に以下のような思考にたどり着きました。

クエリ1 のみなら遅延評価セグメント木で計算が間に合う
そもそも慎重に考える必要があるのは「クエリ3」の対象となっている成分のみ
ある成分が「乱される」のは「クエリ2」の影響による場合のみで、出力の直前にある「影響するクエリ2」のみに依存している
クエリ3 で対象とする行と、そこに影響するクエリ2 を予め覚えておき、「影響するクエリ2」実行後の値・セグ木のその成分の値を記憶しておく。クエリ3 にたどり着いたとき、「クエリ2実行後の値 + セグ木の現在値 - セグ木の過去値」を出力する

時間が無かったので入力例1 が合っているのを確認して即投げしましたが、WAが出ずジャッジが通っていく様を見て「うおお…」ってなってました。

G, Ex

見てないです。

前回「まだ水色遠いな～」と言っていましたが、運良くFを通せて無事入水できました！！最近は青diffを中心に解いていて、今日初めて自力で通すこともできましたが、その成果が出てきたように思います（今日のFも青中位寄りのdiffでしたね…）。

もともと緑くらいのパフォはコンスタントに出していて実質緑からのスタートでしたので、ようやく成長が表に出始めた感じがあります。というわけで、初めてのまともな（？）色変記事を別にまとめようと考えています。

とりあえず、色が変わって嬉しい！