イバコの生存記録

毎日更新が目標。「その日一番考えたこと」を書き留めていきます。

115. 【入水】AtCoder参加記録(AtCoder Beginner Contest 253)

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でしたね…)。

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

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

114. AtCoder参加記録(AtCoder Beginner Contest 252)

20回参加でレート 1147 です。

 

 

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

ABCEを通して、DFGExは未解答です。

 

各問題の感想など。

A

0分55秒。

char として出力するだけ。

 

B

4分24秒。

嫌いなインデックスを HashSet で持ち、A の最大値を出しておきます。A を順番に見て、A の最大値かつ嫌いなインデックスであれば Yes。全部見て引っかからなければ No。

 

C

10分34秒。

予め、各  i について文字とインデックスの対応を取っておきます。その後、揃える文字について全探索(10通り)し、現在時刻から最も近くで揃えられるリールを探し、それを止める…を  N 回繰り返して所要時間を計算します。これの最小値が答え。

なお、現在時刻の加算については、最後のリール以外は +1 しておく必要があります(そうしないと入力例2 が 0 になってしまう)。

文字数を  \sigma = 10 として計算量は  O(\sigma N^2)

 

D

最初10分ほど考えましたが、全く方針が立たないのでスキップ。E はすぐ解けたので、Fと見比べて D の方が見込みあるかな…と、だいぶ考えたんですけど分かりませんでした…。普通に実力不足。

 

E

24分41秒(D の考察時間含む)。

ダイクストラ法で採用する辺を出力するだけ…だったのでみんな解いてきそう…と思っていました。ただ、木に引っ張られて最小全域木を考えた人がそれなりにいたようです。グラフ系はアルゴリズムを正確に理解しているか問われる問題が多く、これもそうでしたね…。

 

F

なんかマージソート的なイメージだな…と思いましたが、明らかに自分の知識セット範囲外だったので、適当に考えてすぐDに戻りました。

 

G, Ex

見てないです。

 

 

とりあえず、前回 ARC のまぐれ青パフォ一発屋で終わらなくてホッとしました。そろそろ入水が見えてきましたが、パフォーマンス的に水パフォ中位以上に突き抜けられていないので、今のままだとまだ遠いな~、という気持ちです。

113. newはやっぱり重いらしい

今日この問題を解いていて、定数倍改善で TLE が取れたのでメモ…。

atcoder.jp

 

問題ですが、しばらく考えて幅優先探索しかないかなぁ、と思い、状態をどのように持たせるか考察しました。 S はビットと見なして整数値で持たせられますが、現在のインデックスも必要なので、独自クラスや Tuple で表現したところ普通に TLE 祭りでした。

 

これ以上改善案も無かったので解説を見ると、ほぼ自分と同じことをやっていました。ということは定数倍が重いのか…となって、まぁ new してるところが重いのかな、と状態を整数で表現し切ることにしました。具体的には、 S 0 から  2^N - 1 の整数で表現されるので、現在のインデックス  i i \times 2^N を足して状態にしてしまおう、という作戦です。

これだけで普通に通ってしまいました。

 

new を削るだけでここまで差が出るか…という感想でした。特に幅優先・深さ優先探索辺りは計算量が読みづらいので、独自クラスの扱いには慎重になりたいな、と思います。

112. AtCoder参加記録(AtCoder Regular Contest 140)

19回参加でレート 1131 です。

 

 

今回はパフォーマンス 1681 です。初めての青パフォ!

ABCを通して、DEFは未解答です。3ペナですが、十分すぎる成果。

 

各問題の感想など。

A

16分6秒(Bから戻ってきた後の所要時間)。

まず、 f(T) はどのように求められるか考えました。入力例を見ると、自然数  n を小さい方から見て、先頭から  n 文字のループで文字列が構成される場合  f(T) = n となるみたいです。 N \le 2000 なので、 1 \le n \le N n 文字ループが作れるか、作るとしたら何文字変換すればよいか、を見れば  O(N^2) で行けそう…と考えました。実際には  n N の約数だけ見れば良いのでもっと余裕があります。

文字の変換は、ループさせる文字列の  i 文字目( 1 \le i \le n)で最も多く使われている文字を採用して、それ以外を変換すればよいです。変換する文字の合計数が  K 以下ならOK、そのときの  n が答えです。

 

この辺りまで5分ほどで薄っすら思い浮かびましたが、ちょっと確信を持てなかったのと実装が明らかに重かったので、頭の整理がつくまで一旦パスしてBを見ました(えらい)。

 

B

41分04秒(Aの考察時間を含む)。

変換後に ARC が新たにできるかが焦点です。偶数回目の操作 ARC → AC ではどうやってもできません。奇数回目の操作 ARC → R では、AARCC のようなパターンでできます。よって、正規表現で書くと (A+)ARC(C+) のようなパターンがあれば奇数回目の操作で変換「したい」です(注意すべきは、必ずできるとは限らない点です)。

ある ARC から新たな ARC を作れる回数は、前後のAとCの連続数のうち小さい方です。各 ARC についてこの数をカウントしておき、この数が 0 である ARC は別にカウントします。前者は奇数回目で優先的に選択し、後者は偶数回目で優先的に選択します。偶数回目で後者がない場合、仕方がないので前者を選択します。

結局、このような ARC の個数の計算に  O(N) 掛かり、あとは変換をシミュレートするだけなので、大きく見積もっても  O(N) です。

 

これも実装が重いですが、Aよりは楽そうだったのでこちらから片付けました。実装ミスで1ペナ。

 

C

51分52秒。

ABが解けた時点でだいぶ安堵して、かなりリラックスしながら「解ければラッキー」くらいの気持ちで解いていました。

なるべく真ん中の値から初めて、小さい方・大きい方…のようにジグザグ取っていけば良さそう?と直感。たとえば、 (N, X) = (5, 1) なら、2文字目は真ん中の値にして  (1, 3, 4, 2, 5) のような形です。これでジグザグに取れなくなったら、余ったものを適当に後ろへくっつけます。

あんまり確信は無かったですが、正直これ以外思いつかなかったのでその通りに実装。小さい方・大きい方どちらから優先的に取るか、 N が偶数のときの「真ん中」の取り方、で  2 \times 2 通り試して、 O(4N) くらいの実装にしました。この場合分けのアイデアは、昨日の ABC E問題の教訓でもあります。

 

WA が出るたびに運良く通らないパターンが見つかり、実装を修正できました。3回目の提出で半分ほど通った時点で WA が出ず、「これは…!」と思いました。めっちゃ心臓バクバク言ってました。

 

D, E, F

見てないです。

 

 

前回のARCは惨敗でしたが、今回はかなり上手く行きました!青パフォ出せたのがとても嬉しいです。正直、ARCは運ゲーみたいなところがありますが、たまに大当たりを引くと最高の気分になりますね。誰かがパチンコって言ってたな…。

今日も音楽を聞きながらのんびりやってましたが、やっぱり自分はこっちのスタイルが良さげなので続けていきます。

111. AtCoder参加記録(AtCoder Beginner Contest 251)

18回参加でレート 1041 です。

 

 

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

ABCを通して、DFGExは未解答です。Eは通せず。またも3完…。難易度は D > E でしたね。

 

各問題の感想など。

A

2分6秒。

色々考えるのが面倒だったので、長さごとに場合分けしました。

 

B

4分59秒。

パッと見て、取る個数ごとに全探索して HashSet で取れる数を管理すればOK…とは思いましたが、Bにしては難しくない?という感想でした。

 

C

4分18秒。

問題文の読解の方が難しかったです。結局、今まで出ていない文字列が来た時に最高点とそのインデックスを更新すればよいだけ。

 

D

入力の最大値が2進数で20桁だったので、ビットごとに考えれば上手く構成できるのかな…と試行錯誤していましたが、300個以下に納めるという制約がどうしても満たせませんでした。

10分くらい考えて方針が立たないので飛ばしました。

 

E

初回提出 48分26秒(Dの考察時間含む)。

初めは PriorityQueue で貪欲法を考えて実装を進めていましたが、DP っぽいことに気付いてそちらにシフトしました。入力例が合ったのでキタ、と思って提出したら全然ダメでした。結局そこから進められませんでしたが、方針と遷移はおよそ合っていて、もう一手、場合分けが足りていなかったです。

 

F, G, Ex

見てないです。

 

 

このところ、ほとんど合ってるのにあと一手足りなくて通せないような問題が多く、典型的な停滞期だなぁ、と思います。。

単純に問題数をこなせていないのだと思いますが、こう続くと精神的には辛いところがありますね。引き出しの足りなさはひらめきでカバーするしか無いですが、そのためにはリラックスが必要で、今日から音楽を聞きながら参加するようにしています。これ自体は割と自分に合っていそうなので、続けていこうと思います。

110. AtCoder参加記録(AtCoder Beginner Contest 250)

17回参加でレート 1037 です。

 

 

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

ABCを通して、EFGExは未解答です。Dは通せず。久々に3完で終わってしまいました。

 

各問題の感想など。

A

3分5秒。

イメージを捉えるのが面倒だったので、すべてのマスで条件式を確認して個数を数えました。

 

B

6分50秒。

Bにしてはやや難しい?
こちらは作りたい盤面のイメージを捉える方が楽な問題でした。分かれば後は構成するだけ。

 

C

9分36秒。

配置を表す配列と、ボール番号からインデックスへの辞書を用意して操作するだけ。初め、右端のボールが「左端」とループすると誤読していて入力例が合わず不思議に思っていました。デバッガでループを追っているうちに、誤読に気づきました。変な設定の問題だな…と思います。

計算量は  O(N)

 

D

初回提出6分54秒。

少し前似たような問題が出ていたので、 p, q \le 10^6 の隠れ制約があることにはすぐ気付きました。この範囲の素数列挙は  O(N \log N) なので十分間に合って、あとはとりあえず全探索で間に合うか?と方針を立てました。

最初の回答を通してみると、TLEはしないので全探索で間に合うと判断。ただし、大量の WA が出ていてどう考えてもオーバーフロー。簡単なオーバーフロー検知は入れていましたが、不十分でした。その後色々足掻いたものの、上手い回避方法が無くて撃沈。

解説を見て、浮動小数点数で大まかに見積もる手法を知りました。これを入れるだけで普通に通りました…。

仮にオーバーフロー検出方法を知っていて、初回提出で通せていればパフォは 883 から 1358 まで上がっていたようです。Eも通せていた可能性があるので、実際はより痛いです。

 

E

スキャナをそれぞれ持たせるイメージで、しゃくとり法的なやり方で解けそうだと思いました…が、Dの失敗もあって集中力が持たず、20分ほど実装してみて入力例が合わず、諦めました。

 

F, G, Ex

見てないです。

 

 

連休最終日でしばらく競プロに触れていなかったということもあるのか、恐ろしく集中力が無くて終始フワフワと解いてました。Eを解いている途中で完全に集中の糸が切れて、Dのオーバーフロー検知をグダグダこねくり回す虚無タイムに入っていました。

とりあえず ABC に参加して競プロへの意識が戻ってきたので、また明日から頑張りたいです。

109. 一次合同方程式を拡張ユークリッド互除法で解く

一次合同方程式  ax \equiv b \pmod{m} を解くことを考えます。競技プログラミングでは稀に必要となる知識で、たとえば以下のような問題で要求されます。

atcoder.jp

 

この記事では、

  • 【理論編】一次合同方程式  ax \equiv b \pmod{m} の解の個数
  • 【実装編】拡張ユークリッド互除法による一次合同方程式の解き方

という流れで記述します。

 

【理論編】一次合同方程式  ax \equiv b \pmod{m} の解の個数

まずは結論から。

一次合同方程式  ax \equiv b \pmod{m} は、 \gcd(a, m) = d として、

  •  b d の倍数でないなら解を持たない
  •  b d の倍数であるなら  d 個の解を持つ

 

証明

(1)  \gcd(a, m) = 1 のとき唯一の解が存在することについて

 \gcd(a, m) = 1 とする。

 \{x_1, x_2, \dots, x_m\} を、 m を法とする剰余系として定める。このとき、 \{ax_1, ax_2, \dots, ax_m\} m を法とする剰余系となる。
なぜなら、 ax_i \equiv ax_j \pmod{m} となるとき、 a, m は互いに素なので両辺を  a で割って  x_i \equiv x_j \pmod{m} となり、これは  i = j と同値であるため。

よって、任意の  b に対して  ax \equiv b \pmod{m} となる  x = x_i が唯一存在する。

 
(2)  b \gcd(a, m) の倍数でないとき解が存在しないことについて

 ax \equiv b \pmod{m} に解があると仮定すれば、 ax = b + ms s は整数)と表せる。変形して  b = ax - ms とする。

 \gcd(a, m) = d として、 a = da', m = dm' とおくと、 b = d(a'x - m's) と表せる。つまり、 b d の倍数となる。

よって、 b d の倍数でないなら、背理法的に解は存在しない。

 
(3)  b \gcd(a, m) = d の倍数のとき解が  d 個存在することについて

(2) の議論の続きで、 b d の倍数として、 b = db' とおく。あらためて式を整理すると、

 ax \equiv b \pmod{m}
 \iff ax = b + ms
 \iff da'x = db' + dm's
 \iff a'x = b' + m's
 \iff a'x \equiv b' \pmod{m'}

ここで、 a', m' はその作成方法から互いに素。よって、 a'x \equiv b' \pmod{m'} の解について、(1) より  x \equiv x' \pmod{m'} なる  x' 0 \le x' \lt m')が唯一存在し、 x = x' + m't t は任意の整数)と表せる。

ここから、元の方程式の解の個数を考える。

 x m を法として合同となるのは、ある  t_1, t_2 について、 x \equiv x' \equiv x' + m't_1 \equiv x' + m't_2 \pmod{m} となるとき。つまり、 m'(t_1 - t_2) \equiv 0 \pmod{m} となるときで、すなわち、 m'(t_1 - t_2) = mu u は整数)であるとき。

このとき、

 m'(t_1 - t_2) = mu
 \iff \frac{m}{d}(t_1 - t_2) = mu
 \iff t_1 - t_2 = du
 \iff t_1 - t_2 \equiv 0 \pmod{d}

すなわち、 x m を法として合同となるのは、 t に対して  d を法として合同な整数を与えたときであり、よって解は  d 個存在する。

(証明終わり)

 

【実装編】拡張ユークリッド互除法による一次合同方程式の解き方

まず、 ax \equiv b \pmod{m} \iff ax = b + mt t は整数)を満たす  x を求めたいので、 \gcd(a, b, m) = d として、 a = da', b = db', m = dm' と置いて  a'x = b' + m't \iff a'x \equiv b' \pmod{m'} を考えてもよいです。以降、この操作を行った後と考え、 \gcd(a, b, m) = 1 であるとします。

 

 ax \equiv b \pmod{m} \iff x \equiv a^{-1}b \pmod{m} を解きたいので、 a の逆元  a^{-1} を考えます。 m素数であるとは限らないので、フェルマーの小定理による逆元導出は使えません。

ここで、逆元を導出するための一次合同方程式は  ax \equiv 1 \pmod{m} と表せます。先程の証明 (2)(3) より、逆元が存在するためには  \gcd(a, m) = 1 であることが必要です。よって、 \gcd(a, m) \neq 1 のとき、解は存在しません

さらに式を変形すると、

 ax \equiv 1 \pmod{m}
 \iff ax + my = 1

となり、これは拡張ユークリッド互除法により解けます。

 

拡張ユークリッド互除法

今回はだいぶ説明を省略して書きます(いずれ丁寧目な記事を出したいです)。

 ax + by = \gcd(a, b)
 a = bq + r

とします。上の式は求めたい一次不定方程式、下の式は  a \div b を表しています。下の式を上の式に代入して、

 (bq + r)x + by = \gcd(a, b)
 \iff b(qx + y) + rx = \gcd(b, r)

です。なお、ユークリッド互除法より  \gcd(a, b) = \gcd(b, r) です。変形後の式の形に注目すると、元々の一次不定方程式と同じ形をしています。一段階変形した後の  (x, y) に相当する変数を  (x', y') と置くと、

 a = b
 b = r
 x = y'
 y = qx - x' = \lfloor \frac{a}{b} \rfloor y' - x'

となります。ここから、再帰的に解を求めることができます。

ユークリッド互除法と同様の操作のため、計算量は  O(\log \min(a, b)) です。

 

参考文献

aozoragakuen.sakura.ne.jp

algo-logic.info