little star's memory

競プロの参加記など

mapに情報を記録しながら順に見ていくやつ

$1\le i<j\le N$であって〇〇をみたすものの個数を求めよというタイプの問題。普通に二重ループをすると間に合わないけど、mapに情報を記録しながら一重ループをすると間に合う。

AtCoder Beginner Contest 137 C - Green Bin

https://atcoder.jp/contests/abc137/tasks/abc137_c

$s$が$t$のアナグラムであることを確かめる方法の1つは、$s$をソートしたものと$t$をソートしたものが一致すること。すぐに思いつく方法は、$i,j$を二重ループして、$s_i$が$s_j$のアナグラムになっているものを数える方法。これは間に合わない。そこで、$j$を1から$N$まで動かし、$s_i$が$s_j$のアナグラムになっているような$i \ (i<j)$の個数を数えるという方法を考える。これはmapを使うと上手くできる。具体的には

  • $map[s]$は、ソートした結果が$s$になるような文字列の個数を表す。
  • $s_j$をソートした結果を$t_j$とし、答えに$map[t_j]$を加算する。
  • $map[t_j]$の値を1増やす。

これで二重ループから単ループになって、間に合う。

AtCoder Beginner Contest 166 E - This Message Will Self-Destruct in 5s

https://atcoder.jp/contests/abc166/tasks/abc166_e

条件は$|i-j|=A_i+A_j$であり、$i<j$と仮定すると$j-i=A_i+A_j$になる。$i$を含む項を左辺に、$j$を含む項を右辺にもっていくと$A_i+i=j-A_j$となる。これも二重ループを行う代わりに、次のようにmapを使えばできる。

  • $i$を1から$N$まで動かす。
  • 答えに$map[i-A_i]$を加算する。
  • $map[A_i+i]$の値を1増やす。

AtCoder Grand Contest 023 A - Zero-Sum Ranges

https://atcoder.jp/contests/agc023/tasks/agc023_a

$s_i=a_1+\ldots+a_i$とする(累積和)。$a_L+\ldots+a_R=0$は$s_R=s_{L - 1}$となる。よって$s_i=s_j$となる$i,j \ (i<j)$の個数を数える問題になる。$s_i$の値の個数をmapに記録しながらやるとできる。

No.1072 A Nice XOR Pair

https://yukicoder.me/problems/no/1072

$1\le i<j\le N$であって$A_i \oplus A_j=X$となるものを数える問題。式変形すると$X\oplus A_j=A_i$となる。よってmapに$A_i$の値を入れていき、$X\oplus A_j$がいくつあるかを求めるとできる。

Codeforces Round #596 (Div. 2, based on Technocup 2020 Elimination Round 2) D. Power Products

https://codeforces.com/contest/1247/problem/D

$a_i, a_j$を素因数分解したときの指数をベクトルとしてみたものを$\vec{e_i}, \vec{e_j}$とする。条件は$\vec{e_i}+\vec{e_j}$の各要素が$k$の倍数になることとなる。 C++だとmapにvectorが載せられるらしい。