geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

AtCoder Biginner Contest 258 参加記録

Loop ABC

コンテスト中AC:A〜D
コンテスト後にEを自力AC。コンテスト中に漠然とした解法まで思い浮かんでましたが、実装間に合わず。
A〜Dは特に書くことがないので、Eについて書きます。

2022/07/08追記
Eの実装中の同値類などは誤りなので、無視してください。

E - Packing Potatoes

説明のため、じゃがいもは円環に並んでおり、N-1番目のじゃがいもまで行ったら0番目に戻るものとします。

1\leq i\leq Nの各iについて、空の状態の箱にi番目のじゃがいもから箱詰めを開始したとします。この箱の箱詰めを終了し、次の箱の箱詰めをA_i番目から開始するとします。
i\rightarrow A_iという関係性を有向辺とみなしてグラフ化します(この関係性は一定です)。

頂点0から出発して有向辺を辿ることを繰り返すと、鳩の巣原理により高々N回で1回訪問済みの頂点に辿りつき、以後ループします。

有向辺を1回辿るということと、箱詰めが1回終了したことが対応します。従って、K回目の箱詰めを始めたじゃがいもの番号は、有向辺をK-1回辿って、辿り着いた頂点番号に対応します。

K-1回でどこの頂点番号に辿り着くかというのは、まず、ループ前の非ループ部とループ部に分けて配列に記録しておきます。非ループ部ならそのままその頂点番号を返し、ループ部に辿り着くなら、ループに属する頂点数をループのサイズとして、ループサイズでmodを取ることでO(1)で求められます。

以上から、i番目のじゃがいもから始めた時に箱に詰めることになるじゃがいもの個数B_iを予め計算しておけば、各クエリにO(1)で答えられます。

過去にもこのような構造をもつ問題は何度か出題されており、構造体Loopとして計算できるようにしてあります。
結構出題されるので、計算方法の詳細は別記事にまとめてみたいと思います。

次に、A_i,\ B_iの求め方です。愚直にX以上となるまで足し続けることは計算量的にできません。まずは円環で並ぶWを何周するか求めます。これは、Wの和をSとすると、\lfloor \frac{X}{S} \rfloor周する必要があります。これをQとしておきます。

残りはX\ mod\ S必要です。これをRとします。残りは一周未満であることが確定します。

合計がR以上となるのに残り何個のじゃがいもが必要かを求める方法としては、Wを2つ繋げたW'を用意し、累積和Sを求めます。
i番目のじゃがいもについて、R+S_{i-1}をキーとしてSを二分探索することで求めることができます。 (但し、i=0の時S_{i-1}=0)

二分探索した結果、W_i + W_{i+1} + \cdots + W_j\geq R となる、jが求まったとします。
すると、
A_i \leftarrow (j+1)\ mod\ N
B_i \leftarrow N\times Q + j-i+1
となります(実装では累積和を取る時にインデックスがずれて計算がおかしくなったので、注意)。
Submission #32991116 - AtCoder Beginner Contest 258

AtCoder Biginner Contest 257 参加記録

ABC 二分探索 BFS 貪欲法 ダイクストラ

コンテスト中AC:A〜D
コンテスト後にEを自力ACできたので、こちらに書いておきます。

2022/07/01 追記 Fも自力で解けたため追記

C - Robot Takahashi

誤った解法でかなり時間をロスしてました。
また、コンテスト後にこの記事を書いていて、嘘解法であることがわかりました。コンテスト中の嘘解法とコンテスト後の正しいと思われる解法書いておきます。

W_iを大人と子供に分けます。
大人を
A=\{A_1,\ \cdots ,\ A_M\}
子供を
C=\{C_1,\ \cdots ,\ C_K\}

とします。
A,Cのいずれかが空の場合は、N人達成可能です。以下、そうでない場合を考えます。

大人の判定が正しくなる個数を全探索します。この場合、実数xの候補として、Aの要素のみを考えればよいです。

例えば、C_j \lt A_i \leq C_{j+1}という位置にA_iが居るとします。C_j \lt x \leq C_{j+1}の範囲でxを動かしても、子供の判定結果に影響を与えません。また、C_j \lt x \leq A_{i}の範囲にすると、A_iの判定を正しいものにできます。
よって、x=A_iとして、損をすることがないです(A_i = C_{j+1}のケースで少し悩みましたが、これも問題ありませんでした)。
なお、C_jやC_{j+1}が存在しない場合でも、同様となります。

以上から、x=A_1,\ \cdots ,\ A_Mとした時に正しく判定できる人数をカウントします。Aの人数は明らかです。Cの人数は、Cを予めソートしておくことで、二分探索可能です。

コンテスト中の実装は以下のような感じです。
Submission #32731821 - NS Solutions Corporation Programming Contest 2022（AtCoder Beginner Contest 257）

コンテスト後に、この実装の反例が存在することがわかりました。

5
00100
10 20 30 40 50

このケースでは、実装xをx\gt 50として、子供の判定を全て正しくすることで、正しい判定を4人にできます。
しかし、最初の実装だと、3人になってしまいます。
なぜこのようなことになるかというと、大人の正しい判定が0人となる場合を考慮できていないためです。

これを正しく判定するためには、Aに\inftyを入れておけばよいです(\inftyを正しい判定となる人数に含めてはだめです)。

Submission #32806566 - NS Solutions Corporation Programming Contest 2022（AtCoder Beginner Contest 257）

D - Jumping Takahashi 2

Sは、ある値以上ならOKで、それ未満はNGという境界があります。そこで、二分探索できないか検討します。

二分探索の判定処理にかかる見積もります。
まず、以下が言えます。

  • ジャンプ力xで全てのジャンプ台に到達できるかは、始点となるジャンプ台を1,\ \cdots ,\ Nまで全探索し、どれか1つでも達成できればよい。

次に、

  • ジャンプ力x、始点sですべてのジャンプ台に到達できるかは、幅優先探索によりO(N+M)で判定できる。

ここで、Mは辺数であり、今回の場合全2点間に辺がある完全グラフとみなせるため、M=\frac{N(N-1)}{2}です。よって、今回はO(N^2)です。

以上から、ジャンプ力xで全てのジャンプ台に到達できるかという判定にかかる計算量はO(N^3)です。

ジャンプ力として考えられる最大をS_{max}とすれば、全体の時間計算量はO(N^3 log{S_{max})}です。
S_{max}=10^{18}とかでも、間に合うと想定でき、二分探索で問題ないことがわかります。

ここからが割と重要で、コンテスト中4回WAを出しました。S_{max}をいい加減に大きくするとオーバーフローします。

というのも、幅優先探索で、ジャンプ台間で移動可能かの判定には問題文中の以下の式を使います。

P_i S \geq |x_i - x_j|+|y_i - y_j|

P_iは最大で10^9になるため、ジャンプ力Sが10^{10}くらいになるとP_i Sがオーバーフローしてしまいます。

そこで、S_{max}をしっかり目に見積もります。
(-10^9,\ -10^9)と(10^9,\ 10^9)間を移動する時、

|x_i - x_j|+|y_i - y_j| = 4\times 10^9となり、右辺が最大です。また、P_i = 1の場合、

S \geq 4\times 10^9かどうかを判定することになるので、S_{max}は4\times 10^9を見積もれば良いことになります。実際にこれでACできました。

その他の方法としては、__builtin_smull_overflowでオーバーフロー判定し、オーバーフローする場合は常に移動出来ることにしておいても良いかもしれません。
Submission #32746202 - NS Solutions Corporation Programming Contest 2022（AtCoder Beginner Contest 257）

E - Addition and Multiplication 2

10進数X,Yについて、考えます。Xの上からi桁目(の整数)をX_iという様に表現します。

X\gt Yの時、以下が言えます。

  1. Xの桁数がYの桁数より真に大きい
  2. XとYの桁数が等しいとき、上からi-1桁目までが等しいなら、X_i \gt Y_i (但し、便宜上X_0 = Y_0)

1番目の条件より、出来るだけxの桁数を大きくすればよいです。そこで、支払う金額が最小の整数dを選び、可能な限り置き換えを行います。なお、支払う金額が最小のものが複数ある場合、そのうち最大の整数を選びます。

次に2番目の条件より、xの最上位桁から優先的にdより大きい整数に変更できないか検討します。変更後の整数についても大きい方から優先的に選びます。なお、xの桁の2つ分を1つの別の整数に変更すると、桁数が減るので、変更は1対1で行います。

残金がなくなり、変更操作ができなくなった時のxが答えです。

i桁目についての具体的な変更方法は、残金をN'とすると、C_dを払い戻したと考え、N'+C_d \geq C_jなら、i桁目をjとし、残金をN' \leftarrow N' + C_d - C_jと更新します。
Submission #32759248 - NS Solutions Corporation Programming Contest 2022（AtCoder Beginner Contest 257）

F - Teleporter Setting

町を頂点、テレポーターを辺とした無向グラフとみなします。移動時間は辺の距離とみなします。
一旦簡単のため、全て連結であるとしておきます。

iに全ての未接続だった辺が繋がった場合を考えます。
最短距離は以下のパターンに限定されます。

(1) 未接続だった辺を経由しない
最短距離は、未接続だった辺を無視した1\rightarrow Nの最短距離となります。

(2) 未接続だった辺を経由する
1\rightarrow iとi\rightarrow Nの経路に分けて考えます。最短距離は2つの最短距離の合計です。

  • 1\rightarrow i

    • 1から直接iに行く
      最短距離は未接続の辺を無視した1\rightarrow iへの最短距離となります。

    • 未接続だった辺を持つ頂点sを経由してiに行く
      sは1から最も近い頂点を選びます。この時、1\rightarrow s\rightarrow iという移動となります。最短距離は未接続だった辺を無視した1\rightarrow sへの最短距離+1です。

  • i\rightarrow N

    • iから直接Nに行く
      最短距離は未接続だった辺を無視したi\rightarrow Nへの最短距離となります。

    • 未接続だった辺を持つ頂点tを経由してNに行く
      tはNから最も近い頂点を選びます。この時、i\rightarrow t\rightarrow Nという移動となります。最短距離は未接続だった辺を無視したt\rightarrow Nへの最短距離+1です。

以上より、各iに接続した時の1からNへの最短距離は、(1)又は(2)のパターンのいずれか小さい方となります。

s,t及び未接続の辺を無視した場合の最短距離は、未接続の辺を無視したダイクストラ法を1及びNのそれぞれを始点として1回ずつ行えば求めることが可能です。

1からNに行けない時は、最短距離が\inftyになるようにすれば求めることができます。詳細は実装参照。
なお、s,tが存在しない場合もあるので、注意が必要です(WAしました)。
Submission #32861308 - NS Solutions Corporation Programming Contest 2022（AtCoder Beginner Contest 257）

AtCoder Beginner Contest 256 参加記録

ABC 強連結成分分解 出次数1の有向グラフ 上界・下界を見積もる

コンテスト中AC:A〜E

C - Filling 3x3 array

i+j+k=Sとなる(i,j,k)の組が何通りあるか考えます。これは、S個の区別のないボールを横1列に並べ、N-1個のボールの間から2つ選んで区別のない仕切りを置き、仕切りの左から順にボールの個数を整数として、i,j,kに割り当てる組合わせに等しいので、_{N-1}C_{2}通りです。

これは、i,jについて、それぞれ1,\ \cdots ,\ Sまで全探索することで、O(S^2)でこれらを全て列挙できます。また、全組み合わせはN=30のケースで_{29}C_{2}=406通りで、かなり少ないです。

(i,j,k)の組が少ないことがわかったので、マスへの整数の割り当てについても次から示すように全探索できます。

これから示すマスの文字は以下のようなイメージです。

a b c
x y z
p q r

1行目と2行目が確定すれば3行目も確定します。そこで、以下のような解法となります。

a_i+b_i+c_i=h_1、x_i+y_i+z_i=h_2となる組を全探索で列挙する。
列挙したものを
V=\{(a_1,\ b_1,\ c_1),\ \cdots ,\ (a_M,\ b_M,\ c_M)\}
W=\{(x_1,\ y_1,\ z_1),\ \cdots ,\ (x_K,\ y_K,\ z_K)\}
とする。
V,Wの要素の全組について、以下を調べる。

V_i,W_jについて、これらの組からp = w_1 - a_i - x_j,\ q = w_2 - b_i - y_j,\ r = w_3 - c_i - z_jを計算する。
p \gt 0,\ q\gt 0,\ r\gt0,\ p+q+r=h_3を全て満たすなら答えに+1する

V,\ Wの全要素の全組の全探索は、O(MK)で、最大でも406\times 406 = 164836で、問題ありません。

実は、コンテスト中はi+j+k=Sを満たすものが何通りあるかの見積もりが間違っていました。
区別の無いボールS個と、区別の無い仕切り3個を横1列に並べる通り数として計算していました。_{S+3}C_{3}です。
これは、i+j+k+l=Sを満たすi,j,k,lの組であって、それぞれ0以上の場合の通り数です。

Submission #32614557 - Tokio Marine & Nichido Fire Insurance Programming Contest 2022（AtCoder Beginner Contest 256) この解法はコンテスト後に見直したものです。

E - Takahashi's Anguish

キャンディを食べる順序を有向辺と見なせそうなので、グラフの問題で考えてみます。
また、人X_iが人iより前にキャンディを食べるというのがややこしいので、以下のように言い換えてみます。

最初の不満度はS=C_1+\cdots +C_Nである。人iの後に人X_iがキャンディを食べると不満度はC_i減少する。不満度の最小値を求めよ。

このように考えると、人iの後に人X_iにキャンディを食べさせて得られる不満度の減少量を最大化する問題となります。 ここでは、減少量をスコアと表現します。

人を頂点とみなし、iからX_iに向かうコストC_iの有向辺を持つ有向グラフを考えます。
これは、出次数1の有向グラフであり、このグラフに含まれる全ての連結成分は以下を満たします。

  • 閉路をただ1つ持つ
  • 任意の頂点から有向辺を辿る移動を繰り返すと連結成分内の閉路にたどり着き、無限ループに入る

これは一応、当ブログのAtCoderの過去問の記事で証明してみてあります。(あまり自信はないです)
リンク (ネタバレ注意)

この有向グラフの各頂点に1回ずつ訪れることを考えると、頂点を訪問順に並べた数列AをPとすることができます。

訪問順を考える際、uを始点とする有向辺e=(u,\ v,\ C_u)をもつ頂点uを訪問した時に、

  • vが未訪問なら、コストC_uを得る(スコアに加算する)。そうでない時、得られない。

とすることで、スコアの取得条件との辻褄があいます。

スコアの上界を見積もります。
各連結成分には閉路が存在します。各閉路について、閉路に属する辺の内の1つは確実にコストを得ることができません。この得ることができないコストには各閉路で最小のものを選ぶのが最適です。

以上から、閉路Cyc_iに属する辺のコストの内、最小のものをw_iとし、その和をS_w = w_1+\cdots + w_Mとすると、スコアの上界はS - S_wとなります。
実はこれは常に達成可能です。

これを説明するために有向グラフG=(V,E)の連結成分の1つComp_i = (V',E')を考えます。
Comp_iにはただ1つ閉路が存在するので、これをCyc_iとします。
Comp_iの部分グラフであって、T_j\rightarrow Cyc_iという感じで閉路と接続するT_jを考えます。

T_jは閉路を含まないため、トポロジカル順に頂点に訪問していくことで、T_jに属する辺及び、T_jとCyc_iを繋ぐ全ての辺(言い換えればT_jに属する頂点を始点とする全ての有向辺)のコストを得ることができます。

Cyc_iに接続する全ての各部分グラフについてトポロジカル順に訪問した後、Cyc_iのうちコスト最小の有向辺の終点から訪問を開始し、閉路を一周すれば、閉路のコスト最小の有向辺以外のコストを全て得ることができます。

減少量(スコア)の最大値はS-S_wであることが分かったので、当初の問題に戻るとSから減少量の最大値S - S_wを引いた値が答えなので、結果として、不満度の最小値はS_wです。

以上より、解法は、

  • 各連結成分の閉路Cyc_1,\ \cdots ,\ Cyc_mのコスト最小をw_1,\ \cdots ,\ w_mとすると、w_1 +\cdots +w_mが答え

ということになります。

閉路の求め方の実装ですが、強連結成分分解を利用しました。
atcoder::scc_graphを使うと、強連結な頂点集合が二次元配列で得られるので、列の大きさが2以上であれば閉路と見なすことができます。列の大きさが2以上の各行から最小値を得れば良いです。
Submission #32566831 - Tokio Marine & Nichido Fire Insurance Programming Contest 2022（AtCoder Beginner Contest 256)

AtCoder Beginner Contest 255 参加記録

ABC 二分探索

コンテスト中AC:A
惨敗でした。コンテスト後ですが、自力でEまでは解けました。

2022/07/14 E問題の赤字部分がiになっていたので、jに修正

B - Light It Up

半径Rの2乗R^2を二分探索します。
2乗しているのは、long doubleなどの実数だと誤差が怖いためです。

二分探索では、以下を判定基準にします。

  • 全ての人がA_1,\cdots ,A_Nのいずれかの人が持つ明かりに照らされる

これはO(NK)で全探索できますが、コンテスト中はこの判定の実装が間違っていました。

R^2の上限として、10^{18}を見積もっても、十分余裕がありました(厳密には2\times 10^{10}くらい？)。

最後に2乗根をとって答えとします。
https://atcoder.jp/contests/abc255/submissions/32422863

C - ±1 Operation 1

等差数列S=\{a_1,...,a_N\}とします。
Xは、Sの最も近い要素にするのが最適です。
値の大小順にXをSに挿入すると以下の3通りが考えられます。

  1. X,\ a_1,\ \cdots ,\ a_N
  2. a_1,\ \cdots ,\ a_l,\ X,\ a_r,\ \cdots ,\ a_N
  3. a_1,\ \cdots ,\ a_N,\ X

それぞれのケースの答えは、

  1. |X-a_1|
  2. min(|X-a_l|,|X-a_r|)
  3. |X-a_N|

です。
1,3のケースは簡単に求められます。問題は2のケースですが、これは二分探索により求められます。

コンテスト中はD\lt 0のケースが抜けていました。
Submission #32422643 - Aising Programming Contest 2022（AtCoder Beginner Contest 255）

D - ±1 Operation 2

例えば、AのX未満の要素がB_1,\ B_2,\ \cdots ,\ B_mであったとします。

これをXにしたい時にかかる操作回数は、

X - B_1 + X - B_2 + \cdots + X - B_m

式変形すると、

X+X+\cdots + X - (B_1 + B_2 + \cdots + B_m)

となり、S_B = B_1 + B_2 + \cdots + B_mとすると、

X\times m - S_B

となります。

同様に、Xより大きいAの要素をC_1,\ C_2,\ \cdots ,\ C_nとすると、必要な操作回数は、

S_C - X \times m

となります。

余談ですが、式は説明のために書きましたが、コンテスト中は棒グラフを書いて、Xで線を引く感じをイメージしました。

解法ですが、X未満とXより大きい要素の和を効率よく得られればよいです。Aの順序は無視できるため、Aを昇順ソートして、累積和を計算しておくと、二分探索して和を得られます。
具体的には以下のようになります。

  1. Aを昇順ソートする
  2. Aの累積和Sを得る
  3. 各クエリについて、以下を行う
    1. 二分探索で、ソート済みのAの要素の内X未満の最大値A_sと、Xより大きい要素の最小値A_tを得る。
    2. X\times s - S_s + S_N - S_{t-1} - X\times (N-t)を出力する

なお、A_s,A_tが存在しない場合の例外処理が必要です。

コンテスト中はクエリの処理部分を以下のようにしていました。

X以上の最小値A_sを二分探索で得る(lower_bound)。
X\times s - S_s + S_N - S_{s} - X\times (N-s)を出力する

A_1,\ \cdots,\ A_sとA_{s+1},\ \cdots ,\ A_Nに分けるような方法です。

この実装は、AにXが存在すれば、おそらく問題なく動作すると思うのですが、そうで無い場合、例えば以下のようなケースで答えがおかしくなります。
A=\{1,5\},\ X=3

1,5を3にするのにそれぞれ2回の操作が必要なので、計4回となるはずです。しかし、上記の実装だと、A_s=5となり、3\times 2 - (1+5)=0となってしまいます。

おそらくA_sを大きい方の和に入れておけばよかったです。つまり、
A_1,\ \cdots,\ A_{s-1}とA_{s},\ \cdots ,\ A_N

という風に分けておけばよかったものと思います。

Submission #32420079 - Aising Programming Contest 2022（AtCoder Beginner Contest 255）

E - Lucky Numbers

コンテスト後に解きましたが、思わぬところでTLEになり解決に時間がかかりました。

A_iはA_1とS_0,\ \cdots ,\ S_{i-1}で表現できます(便宜上、S_0 = 0とします)。具体例を示すと、

A_1 = S_0 + A_1
A_2 = S_1 - S_0 - A_1
A_3 = S_2 - S_1 + S_0 + A_1

という感じです。 ここで、定数部分をV_iとします。
そうすると、A_iは以下のように表現できます。

  • iが偶数の時、A_i = V_i + A_1

  • iが奇数の時、A_i = V_i - A_1

また、V_iは、以下の漸化式で計算できます。

V_i = S_{i-1} - V_{i-1}

ここまでで前準備が終了です。

少なくとも1つはラッキーナンバーにしないと損をするので、A_1,\ \cdots ,\ A_Nがそれぞれ、X_1,\ \cdots ,\ X_Mである時のラッキーナンバーの数を全探索します。

A_j = X_iである時を考えます。
A_1は以下のように計算できます。

  • \color{red}{j}が偶数の時 A_1 = X_i - V_j

  • \color{red}{j}が奇数の時 A_1 = -(X_i - V_j)

A_1が求まると、A_mがラッキーナンバーX_kとなるためのV_mが満たすべき条件がわかります。すなわち、

  • mが偶数の時 V_m = X_k - A_1

  • mが奇数の時 V_m = X_k + A_1

従って、予めV_1,\ \cdots ,\ V_Nについて、偶奇を分けてハッシュマップに個数をカウントしておけば、上記を満たすようなものの個数をO(1)で得られます。

A_j = X_iのときに、X_1,\ \cdots ,\ X_MとなるものがあるかをO(1)で調べられるので、時間計算量はO(NM^2)となり、問題ないと思われました。

しかし、実装時C++のunoredered_mapでこれを実装するとTLEになりました。

結局、V_iとその個数をpairにしたvectorを昇順ソートし、lower_boundすることでACしました。
Submission #32478157 - Aising Programming Contest 2022（AtCoder Beginner Contest 255）

AtCoder Beginner Contest 254

ABC 整数論 素数 素因数分解 線形篩

コンテスト中AC:A〜C,E
AtCoder Beginner Contest 254 - AtCoder

解けなかったDを解説見てACしたので少しだけ付け足しして書いておきます。

D - Together Square

この問題では、以下の命題が重要そうです。

i\times jが平方数となるための必要十分条件は、任意の素数pについて、i,jに含まれるpの個数の偶奇が等しい

厳密な証明までは必要なさそうですが、一応理解を深めるため、ここでは証明しておきます。(素人なので、間違っていたらすみません)

まず、以下の補題を証明します。

整数Xが平方数である\Leftrightarrow任意の素数pについて、Xに含まれるpの個数が偶数

[証明]

[ \Rightarrow ]Xは平方数であるから、x=\sqrt{X}を満たす整数xが存在する。xの素因数分解をx=p_1^{a_1}\times p_2^{a_2}\times \cdots \times p_k^{a_k}とすると、
X=x^2=(p_1^{a_1}\times p_2^{a_2}\times \cdots \times p_k^{a_k})\times (p_1^{a_1}\times p_2^{a_2}\times \cdots \times p_k^{a_l})=p_1^{2a_1}\times p_2^{2a_2}\times \cdots \times p_k^{2a_k}
となり、示された。

[ \Leftarrow ] Xの素因数分解をX=p_1^{a_1}\times p_2^{a_2}\times \cdots \times p_k^{a_k}とすると、a_1,a_2 ,..., a_kは偶数なので、
x=p_1^{\frac{a_1}{2}}\times p_2^{\frac{a_2}{2}}\times \cdots \times p_k^{\frac{a_k}{2}}
を満たす整数xが存在し、先程と同様な議論でx^2=Xとなるため、Xは平方数である。

では、元の命題を証明してみます。

[証明]

[ \Rightarrow ]対偶を示す。
ある素数pについて、i,jに含まれる個数の偶奇が等しくないとする。
偶数個であるものをp^{2n}、奇数個であるものをp^{2m+1}とおく。
i\times jに含まれるpの個数に着目すると、
p^{2n}\times p^{2m+1}=p^{2n+2m+1}=p^{2(n+m)+1}
となり、pは奇数個となる。補題より、i\times jは平方数では無い。よって、対偶が示された。

[ \Leftarrow ]任意の素数pについて、i,jに含まれる個数が共に偶数個である場合、それぞれp^{2n},p^{2m}とすると、i\times jに含まれる個数もp^{2n+2m}=p^{2(n+m)}となり偶数である。共に奇数個である場合p^{2n+1},p^{2m+1}とすると、p^{2n+1+2m+1}=p^{2(n+m+1)}となり偶数となる。よって、偶奇が等しい場合i\times jに含まれる任意の素数の個数は偶数個となり、補題よりi\times jは平方数である。

証明は以上です。
ここまでで、i\times jが平方数となるためには、i,jの素因数の個数の偶奇が等しい必要があることがわかりました。
次に、そのような組の求め方です。

Xの素因数の内、奇数個である素因数の1乗の積f(X)を考えます。
60=2^2\times 3\times 5なら、f(60)=3\times 5
900000=2^5\times 3^2\times 5^5なら、f(900000)=2\times 5
です。

f(X)は素数の1乗の積なので、含まれる素数に対して一意に定まることから、素数の偶奇の状態に対しても一意に定まります。
そのため、f(X)=f(Y)ならX,Yの素因数の偶奇の状態が等しいと判断できます。

以上から、以下の解法が導かれます。

  • i=1,...,Nについて、f(i)を求め、同一なf(i)の個数をカウントする
  • f(x)の個数をcnt_{f(x)}とすると、_{cnt_{f(x)}}C_2を全てのf(x)について計算し、総和をとったものが答え

これが公式解説の解法です。(この記事では、f(x)を別物として定義しています。)

f(x)の求め方ですが、公式解説やユーザ解説に色々方法がありますが、こちらのユーザ解説で実装してみました。線形篩を知らなかったので、勉強になりました。
Submission #32343255 - AtCoder Beginner Contest 254

AtCoder Biginner Contest 253 参加記録

ABC 包除原理 DP マンハッタン距離

コンテスト中AC:A〜E
NOMURA Programming Contest 2022（AtCoder Beginner Contest 253） - AtCoder

B - Distance Between Tokens

マンハッタン距離に関する問題です。
'o'である2箇所をS_{i,j},S_{i',j'}とすれば、答えは、

|i-i'|+|j-j'|

です。
Submission #32006932 - NOMURA Programming Contest 2022（AtCoder Beginner Contest 253）

C - Max - Min Query

多重集合SをC++の多重集合multisetで解けます。

実装は後ほど記載のリンク参照。

WAを出したのですが、S.erase(i)をS.erase(x)にしてしまってあり、こうするとSの中のxが全て削除されてしまいます。

補足ですが、Sに追加される個数が高々Q個なので、削除される回数も全体で高々Q回です。

Submission #32020504 - NOMURA Programming Contest 2022（AtCoder Beginner Contest 253）

D - FizzBuzz Sum Hard

基本的な包除原理です。
1からNまでの全体の和Sから不要なものを引くことを考えます。

1\leq i \leq NまでのA,Bの倍数であるiの和をS_A,S_Bとおきます。
S - S_A -S_Bとすると、Aの倍数かつBの倍数であるものを余分に1回引いてしまっています。

そこで、1\leq i \leq NまでのAの倍数かつBの倍数であるiの和をS_{AB}とおきます。
すると、S - S_A -S_B+S_{AB}で答えを求められます。

Aの倍数かつBの倍数であるiは、AとBの最小公倍数をLとして、Lの倍数となります。よって、S - S_A -S_B+S_Lを求めればよいです。

具体的な計算方法です。
まず、Sは、\frac{N(N+1)}{2}です。

S_A,S_B,S_Lは以下のように求められます。
1\leq i \leq Nに含まれるXの倍数の個数をnとします。nは下式により求まります。
n=\lfloor \frac{N}{X} \rfloor - \lceil \frac{1}{X} \rceil +1

求めたいものは

S_X=X+2X+\cdots+nX

なので、

S_X=X(1+2+\cdots +n)=\frac{Xn(n+1)}{2}

で求められます。
Submission #32025795 - NOMURA Programming Contest 2022（AtCoder Beginner Contest 253）

E - Distance Sequence

A_iとしてあり得るのは1,...,Mなので、数列の状態数は、NM個であり、DPできそうです。

dp[i][j]:=数列Aのi番目がjであるような数列の個数

このテーブルをi=1,...,Nの順に更新していくことを考えます。

遷移は、問題文の条件を考えると、

dp[i][j]\leftarrow (dp[i-1][1]+\cdots\ + dp[i-1][j-K]) + (dp[i-1][j+K]+\cdots\ + dp[i-1][M])

という感じになります(後の説明のために()で括ってあります)。
愚直に1個ずつ足していくと遷移に時間計算量O(M)かかり、全体でO(NM^2)となり、間に合いません。

そこで、遷移にかかる計算量を落とせないか考えてみます。
すると、
dp[i-1][1]+\cdots\ + dp[i-1][j-K]
及び
dp[i-1][j+K]+\cdots\ + dp[i-1][M]
は連続した区間の和となっています。　 このような場合、累積和によって、計算量を落とせます。

具体的には、

dp_S [i][j]:=dp[i][0]+dp[i][1]+\cdots + dp[i][j]

とします。但し、便宜上dp_S[i][0]=0としておきます。

このようにすると、先程の遷移の右辺は、
dp[i-1][1]+\cdots\ + dp[i-1][j-K]=dp_S [i-1][j-K]
dp[i-1][j+K]+\cdots\ + dp[i-1][M]=dp_S [i-1][M] - dp_S [i-1][j+K-1]

という風になり、O(1)で計算できるようになります。

実装時、いくつか気をつける点があります。

  • j-K\lt 0となる可能性があるので、max(0,j-K)をとる。

  • j+K-1\gt Mとなる可能性があるので、min(M,j+K-1)をとる。

更に、上記2つでそのまま実装すると、K=0の時にコーナーケースとなります(dp[i][j]が2回足されてしまうはず)。
そのため、

  • K=0のときは、遷移をdp[i][j]\leftarrow dp_S [i-1][M]とする。

このようにしておけばよいです。
Submission #32041363 - NOMURA Programming Contest 2022（AtCoder Beginner Contest 253）

AtCoder Beginner Contest 252 参加記録

ABC ダイクストラ ハフマン符号

コンテスト中AC: A〜F

C - Slot Strategy

解法は公式解説と同じだったので、実装例だけ書いておきます。

S_iの左からj_i番目に文字xがあるとして、j_iを配列に記録しておきます。これを、
v_x =\{j_1,...,j_N\}
とします。

これを昇順ソートして、ランレングス圧縮すると、文字xが何番目に何個出現するかという組が得られるので、あとは公式解説の方法で計算できます。
Submission #31861075 - AtCoder Beginner Contest 252

D - Distinct Trio

"3つがすべて異なる"は、"2つ以上同じものが存在することの補集合"と捉えられます。

そこで、各整数について、ちょうど2個同じ場合とちょうど3個同じ場合の総和を求め、3つを選ぶ総数から引くことにします。
なお、重複なく選ぶことを前提とします。

では、その求め方です。
ここで、cnt_iを整数iの出現数とします。

  1. 整数iがちょうど2個同じ
    cnt_i \geq 2である必要があります。
    iを2個選ぶ組み合わせは_{cnt_i}C_2通りです。
    残り1つはi以外ならなんでも良いので、N-cnt_i通りです。
    よって、_{cnt_i}C_2 \times (N-cnt_i)通りです。

  2. 整数iをちょうど3つ選ぶ
    cnt_i \geq 3である必要があります。
    整数iから3つ選ぶ組み合わせなので、_{cnt_i}C_3です。

  3. 全体から3つを選ぶ総数
    _{N}C_3となります。

3から、各整数についての1,2の総和を引けば答えとなります。

時間計算量は、O(min(A_{max},N))かなと思います。なお、A_{max}はAに含まれる整数の最大値です。

E - Road Reduction

d_2,...,d_Nが、都市1から各都市への最短路であれば、条件を満たすことができます。
辺のコストが非負整数なので、ダイクストラ法で最短経路を求められます。ダイクストラ法で最短路に使用する辺がわかるので、これを残しておけば、そのまま問題の答えになります。

この方法によって、もう一つの答えの条件である辺がN-1個になる、すなわち木になるかどうかについてですが、コンテスト中は、閉路はできないだろう、と直感的に解いてしまい、考察が不十分だったので、もう少ししっかり考えてみます。

説明1
ダイクストラ法の各段階において。最短路が見つかっている頂点集合をS、見つかっていない頂点集合をTとします。
ここから、Tのある頂点vの最短路が決定するとします。

もし、Sに含まれる頂点u_1,...,u_mがvと辺で繋がっていたとしてもその中から最短路として選ばれるのはただ1つです。 よって、SとTの任意の辺を繋いで閉路ができることはないです。

また、Sに含まれるもの同士で繋がることもあり得ません。

以上より、ダイクストラ法の各段階で、閉路が生成されることはないので、最終的に出来上がるものは木になります。

説明2

以下を証明してみます。
無向グラフG=(V,E)にダイクストラ法を適用し、始点sからの最短路を見つける。ダイクストラ法の各段階において、sからの最短路が見つかっている頂点数がk個であるとき、この頂点集合をV'_kとおく。また、V'_kに含まれる任意の頂点への最短路を構成する辺集合をE'_kとする。

V'_k,E'_kからなる、Gの部分グラフG'_k=(V'_k,E'_k)は常に木であることを示す。なお、木であるとは、以下が成り立つことである。

  • G'は連結
  • |E'| = |V'|-1

G'_1のとき、V'_1にはsのみが存在し、連結です。|V'|=1,\ |E'| =0より、|E'| = |V'|-1を満たします。

G'_kのときに成り立つと仮定します。
ダイクストラ法によって、V\backslash V'_kに含まれるある頂点vの最短路が決定されるとします。
この時、最短路決定に使用された辺e=(u,v)が存在します。なお、頂点uはV'_kに含まれる頂点の１つです。

V'_kにv、E'_kにeがそれぞれ追加されたものがV'_{k+1},E'_{k+1}となります。

まず、仮定よりG'_kは連結です。また、新たに追加されたvはuと連結なので、G'_{k+1}は連結です。

次に、|V'_k| =| V'_{k+1}| -1、|E'_k| = |E'_{k+1}|-1です。仮定より、|E'_k| = |V'_k|-1が成り立っているので、代入することで|E'_{k+1}| = |V'_{k+1}|-1が得られます。

以上で、帰納法によって、G'_k=(V'_k,E'_k)は常に木であることが示せたと思います。

Submission #31869657 - AtCoder Beginner Contest 252

F - Bread

解法は公式解説と同じでした。

公式解説のように解法の正当性を厳密に証明できませんでしたが、コンテスト中に大雑把に考えていたことを書きます。

操作の逆を考えたとき、長さxと長さyのパンから長さx+yのパンを得ることを合体と呼ぶことにします。

まず、入力例1からどのように操作すると解が悪化するのか考えました。
例えば、
2+2=4
4+1=5
5+1=6
7+1=7
とすると、解は4+5+6+7=22になり、16より悪化します。
これより、大きい数に合体していくと解は悪くなりそうだとわかりました。ということは、逆に小さいものを2つ選んで合体していけばよいだろうと考えました。

次に、小さいものを2つ選んで合体すると、その後の解に影響を与えるか考えてみました。例えば、入力例1で、最初に1と1を合体した場合と1と2を合体した場合を考えます。

この操作によって、2と3のいずれかが生成されるわけですが、2や3はまた更に合体しないといけないので、追加で2または3のコストがかかります。それなら、1と1を合体したほうがよいです。

こんな感じでしたが、一応ACはできました。
Submission #31875956 - AtCoder Beginner Contest 252