ARC106-D Powers を直感的に解く

今更ですが、ARC106-D Powers の簡単な解説を書きます。

問題リンク:

atcoder.jp

問題概要:

長さ N の数列 \{A_i\} がある。 1 \leq X \leq K それぞれについて、

\displaystyle{
\left( \sum_{i \lt j} (A_i+A_j)^X \right) \ {\rm mod} \ 998244353
}
を求めよ。
1 \leq N \leq 2 \times 10^5
1 \leq K \leq 300
1 \leq A_i \leq 10^8

解法:

対称性から \displaystyle{\sum_{i \lt j} (A_i+A_j)^X = \frac{1}{2} \sum_{i \neq j} (A_i+A_j)^X} なので、これを求めます。(こちらの方が後の計算が楽です。)
まず括弧の中を展開すると、


\begin{aligned}
\sum_{i \neq j} (A_i+A_j)^X
&= \sum_{i \neq j} \left(\binom{X}{0} A_i^X + \binom{X}{1} A_i^{X-1} A_j + \cdots + \binom{X}{X} A_j^X \right) \\
&= \binom{X}{0} \sum_{i \neq j}  A_i^X + \binom{X}{1} \sum_{i \neq j}  A_i^{X-1} A_j + \cdots +\binom{X}{X}  \sum_{i \neq j}  A_j^X
\end{aligned}

となります。
二項係数は高速に前計算できるので、\displaystyle{ \sum_{i \neq j} A_i^k A_j^l \ (0 \leq k,l \leq K)} が高速に求まればよいです。


突然ですが、次のような長方形を考えてみましょう。


f:id:null_mn:20201030061131p:plain


すると、 \displaystyle{ \sum_{i \neq j} A_i^k A_j^l} は次の赤い部分の面積に一致します。


f:id:null_mn:20201030061029p:plain


これは次の(緑の面積)-(青の面積)で求まります。


f:id:null_mn:20201030061149p:plain

f:id:null_mn:20201030061141p:plain


緑の面積は  (A_1^k + \cdots + A_N^k)(A_1^l + \cdots A_N^l) 、青の面積は  A_1^k A_1^l + \cdots + A_N^k A_N^l で求まるので、
\displaystyle{ \sum_{i \neq j} A_i^k A_j^l = \sum_{i} A_i^k \sum_{i} A_i^l - \sum_{i} A_i^{k+l}}
が成り立つとわかります。

よって、  0 \leq k \leq K に対し  \displaystyle{\sum_{i} A_i ^k} を前計算しておくことで \displaystyle{ \sum_{i \neq j} A_i^k A_j^l} が求まり、最初の式の値も求まります。


このように二重和が登場する場面では、分割された長方形の面積を考えることで式変形を直感的に行える場合がしばしばあります。
式変形自体は特に目新しいものではないですが、「直感的にわかる」ことは発想を得る上で重要だと思うので、是非役立ててみてください。
 

ICPC2020模擬国内 参加記

いつも通りstoq, momohara, hanyuのチームharaharaで模擬国内2020に参加しました。

覚えてる範囲で書きます。

 

開始前

30分前に起床する(すいません)。ごはんを食べ損ねる。TLを見るとももはらさんも同じことやってた。

A~Cの割り振りを決める。いつも大体同じ

 

コンテスト

ももはらさんがA、はにゅさんがB、僕がCを開く。しばらくしてA, Bが通る。

Cがなかなか解けずかなり焦る。忍小宮って誰?ようやくそれっぽいコードがかけたものの、出力ファイルを覗くと個数が負になってたのでデバッグする。かなり時間をかけてAC。ここまでで1時間ちょっと。

Fの考察に取り掛かっている間にはにゅさんが2-SATを書いて O(N^3) でEを通す。すごい。

その後ももはらさんがDで苦戦してたっぽいのでコードを見る。よくわかりませんでした(ごめんなさい)。少ししてからDが通る。すごい。ここまでで2時間くらい。

順位表を見るとF, Gが不可能そうなのでHを見る。許容誤差 10^{-10} で二度見した。ループがあるとき0、ないとき-1/mを出力するコードを書いたらサンプルが合ったけど流石に通らなかった。そうこうしているうちにコンテストが終了する。

 

結果

f:id:null_mn:20201026011208p:plain

5完で全体24位でした!チームメイトが強くてとても助かりました。感謝....…

ライバルチームのstate_of_the_artに数十秒差で負けたのがちょっと悔しいですが、十分な順位を取れたので満足です。予選本番は20位以内を目指します。

 

おわりに

寝坊には気を付けましょう。

 

 

秋分コンテスト2020感想

秋分コンテストに参加しました!13位という高成績を残せて満足です。癖の強い問題が多くてとても楽しめました。

記憶に残ってる問題について書きます。

 

 

B : Self Introduction

そのまま"I am stoq"で出したらAC。ユーザー名が入ってればACになるっぽい?

 

C : ピクトセンス

全部よくわからなかったので、候補の文字列をいい感じにソートして探した。最後2つはわかりません。

 

E : Soup, Abandoned

結構粘ったんですけどダメでした。OEISも探したけど見落としてたっぽい。

というか秋分とか数列とか質問しても特に何もなかった気がする、ツンデレ

 

G : くそなぞなぞ

鉄arrayくらいしかわかりませんでした。くそなぞなぞ茶coderには難しい

 

H : 手紙 1 I : 手紙 2

変体仮名と万葉仮名をがんばって解読しました。こういう解読系の問題は好きかも。

 

L : Sqrt

20ペナの末にAC(?)「±√正」とか出してた。

 

O : 沖縄

wikipedia見たら答え載っててびっくりしました。

 

S : Cat nuke' Challenge

問題文からsが抜けてるので補完して投げるとWAの表示が。Textでサンプル出力を投げると1ケースはACになるので、ソースコードに問題があると予想しました。

どうやらソースコードに's'が含まれるとダメらしく、std::cinもscanfも使えなくて詰み。初心者用Python入門記事を読んでなんとかACしました。Pythonでの初ACがこれなの面白い。

 

上のタブとユーザー名からもs消えててびっくりしました。

f:id:null_mn:20200923010535p:plain

 

T : |あ|み|だ|く|じ|

First ACです!(30:58)

Dxlibとかでがんばるのも考えましたが、画像処理に不慣れなので人力でがんばりました。(照)

 

W : 嗚呼、恍恍惚惚 曠古、杲杲煌煌、兀兀甲骨

甲骨文字の一覧を引っ張ってきて気合で全完。

 

Y : A/B Problem

そのまま出す。「ソースコードに'/'を入れてはいけない」と言われ、キレる。

std::divideで書き直す。「ソースコードに"div"を入れると減点」と言われ、キレる。

__int128でよくわからない二分探索をしてAC。

 

_ : Echo

配点が負のケースがあるので、すべてに正解してしまうと-135点になる。正解するケースを選んで得点を最大化する問題。普通に競プロの問題でありそうだけど解けませんでした......

ローカルで乱択を回してなんとか部分点獲得。

 

感想

普段のコンテストとは全く違う問題ばかりで楽しかったです!運営のみなさん、ありがとうございました。

1053の性質

注意

内輪ネタです。

1053とは:

mattyan1053.hatenablog.com

 

 概要

「1053」という数の性質を列挙しただけの記事です。

 

自明な性質

・実数である。

・整数である。

・奇数である。

 1053 = 3^4 \times 13

・2進法で表すと10000011101。

 1053 = 18^2+27^2

 

非自明な性質

OEISからの引用が多め。

 

・"1053"の連続する部分文字列を全て列挙すると、素数であるものと素数でないものが同数となる。

素数であるものは5, 3, 05, 53, 053、素数でないものは1, 0, 10, 105, 1053です。

 

・マッチ棒を使って次のような三角形を作るとき、必要なマッチ棒の本数は1053本。

 

f:id:null_mn:20200705191205p:plain

3n(n+1)/2 \ |_{n=26} = 1053 に由来します。

 

・Iccanobif numberである。

Iccanobif numberは次の漸化式で定義される数列 \{R_i\} の要素です。

R_0 = 0,\ R_1=1,\ R_{i+2}=rev(R_{i+1}) + rev(R_{i}) \ (i \geq 0)

ただしrevは文字列としての反転を表します。Fibonacci numberに反転を加えたものなのでIccanobif numberと呼ばれます。

 

 n^2+3n+1 \ |_{n=32} = 1053

 

 3(n^3+n+1) \ |_{n=7} = 1053

 

 p_{1053} \equiv -1 \ ({\rm mod} \  1053) 。ただし p_ii 番目の素数

p_{1053} = 8423 = 1053 \cdot 8 -1 です。

 

 \displaystyle 51= \sum_{i=1}^{r} a_i  \ (a_j-a_i = 0,1 \  (i \lt j) , \ a_1=1) となる (r,a_1, \dots, a_r) の組は1053個。

1から始まり差が0か1の広義単調増加列で、和が51のものは1053通りです。

 

・1053を3つの0でない平方数の和で表す方法は、順序の違いを除いて8通り。

1053\\=2^2+5^2+32^2=3^2+12^2+30^2=4^2+14^2+29^2=4^2+19^2+26^2\\=6^2+21^2+24^2=10^2+13^2+28^2=11^2+16^2+26^2=13^2+20^2+22^2

となります。

 

 

 適宜追記予定。

競プロでよく使われるC++の略記まとめ

(初心者向けの記事です)

競プロでたまに見るC++のテクニカルな表記をメモ程度にまとめておきます。

自分自身はあまりこのような表記は使わないのですが、他の人のコード、特にライブラリ化している部分においてはよく使われている気がします。他の人のコードを読むのに役立てれば幸いです。

 

・if(n)

if(n != 0) と同義です。intからboolの変換では0以外が1(true)、0が0(false)に変換されます。

 

・if(!n)

if(n == 0) と同義です。上と同様。

 

・if(n & 1)

if(n % 2 != 0) または if(abs(n) % 2 == 1) と同義です。最下位のbitが立っているかどうかで偶奇の判定ができます。(nが負の場合の挙動を考慮していなかったので修正しました。)

 

・if(~n)

if(n != -1) と同義です。~nはnの補数を表します。

 

・while(q--)

while文をq回繰り返します。Codeforcesなどのクエリ式の問題でよく使われます。

 

・a=i++

a=i, i++; と同義です。iを加算し、aに加算前のiを代入します。

 

・(a *= b) %= m

a = a*b%m と同義です。

 

・a = !!b

a = (bool)b と同義です。bが0以外のときa=1, bが0のときa=0となります。

 

・b ^= 1 (bはbool型)

b = !b と同義で、bの真偽値を反転させます。略記というほどじゃないかも。

 

・if(a ^ b) (a, bはbool型)

aとbのいずれか一方のみがtrueのときif文を実行します。便利です。

 

 ・if (foo) return !printf("%d\n", x);

xを出力して0を返します。printfの返値は出力した文字数であるため、演算子「!」を作用させると0になります。

 

・if (foo) return puts("-1"), 0;

 -1を出力して0を返します。コンマ演算子を用いると、コンマで区切られたすべての式を評価した後で一番右のものを返します。

 

他にもいろいろあると思いますが、とりあえず思い付いたものを書き連ねました。参考になればうれしいです。

また、自分が一目で理解できないものは、デバッグが困難になるのでなるべく書かないようにしましょう。

 

他にも追加したほうがいいよ!ってものがあれば教えてください。

yukicoder contest 247 writer感想

yukicoder contest 247のwriterのstoqです。初めての作問なので至らない点もあったと思いますが、全体的にいい感じにできた気がします。

 

コンテストリンク:

https://yukicoder.me/contests/262

yukicoder.me

 

注意したこと

・assertで制約外のテストケースがないか確認する。

・問題文のサンプルと実際のサンプルが一致しているかを確認する。

C++以外お断りコンテストにならないように実行時間に余裕を持たせる。

・コーナーケースがある場合は全て入れる。

・解説を省略しすぎない。

・難易度を低く見積もりすぎない。(低いよりは高い方がいいので)

 

問題ごとの講評

各問題についても色々書き留めておきます。

!注意!解法のネタバレを含みます。

 

A. Fruit Rush

tester: fukafukataniさん

First AC: Taprisちゃんさん

一問目なので簡単めにしました。ソートができるかどうかと A_i が全て負のコーナーケースに気付けるかが本質です。選ぶ果物の個数を0個以上にするか一瞬迷いましたが、無はミックスジュースではないのでやめました。

 

B. Zero (Novice)

tester: trineutronさん

First AC: uwiさん

ギャグ枠です。愚直を投げると、なんと!……通る(は?)

書いた後で愚直が通るのに気付きましたが、テストケース作っちゃったしまあいいかということで出題。ちなみに32bit整数の愚直は A = 2^{32}-1, B=2^{32} で落ちます。(trineutronさん指摘ありがとうございます)

 

C. Zero (Advanced)

tester: tran0826さん

First AC: heno_codeさん

ある連続する区間の数を何個か選んで足し合わせた数の取りうる値の範囲は、1つの連続した区間となります。これはよく出題される事実なので覚えましょう。

modはその都度取っても最後に一気に取っても変わらないので、区間M の倍数があればYes、そうでなければNoです。

 

D. Zero (Exhaust)

tester: tran0826さん

First AC: heno_codeさん

CとDの難易度差が大きい気がしたのでちょっと反省。

{\rm mod} \ P 上では割り算ができることを踏まえると、遷移の対称性が見えてきます。

DとEと統合して  P, \ K \leq 10^9 にするか迷いましたが、そうすると行列累乗なしで手計算またはWolframAlphaで解けてしまうのでやめました。

 

E. Zero (Maximum)

tester: tran0826さん

First AC: maspyさん

行列累乗の典型題があんまりない気がしたので作ってみました。verify用にどうぞ。

行列累乗やるだけなのでDより簡単だったかも?

あと問題名の括弧内は某大人気音楽ゲームの難易度から取っています。早く自粛から解放されて音ゲーしたい......

 

F. PQ Permutation

tester: kakiraちゃん

First AC: LayCurseさん(優勝おめでとうございます!)

場合分けが100個あるタイプの実装問です。基本知識は貪欲と累積和くらいしかないので、場合分けをしっかりできるかどうかが鍵となります。僕は最初嘘二分探索を書きました。

 最後の面倒な構成パート(解説の後半、(II)の最後)は、次図のように実装すると簡単に書けます。(  P=7, \ Q=3,\ m=5 の例)

 

f:id:null_mn:20200501084114j:plain

 

std::rotateは一番好きなstdです。

余談ですが、この問題は寝てるときに夢の中のARCで出題されていた問題です。起きて解いたらなんか良さげな感じだったのでパクって出題。夢の中のARC、すまん!w

 

追記:テストケースが滅茶苦茶弱かったみたいなのでリジャッジを行いました。お手数をおかけしました。テストケース作成って難しいですね……

難易度も一旦★3.5に下げたんですけどAC状況を見て★4に戻しました。

感想

参加してくださった皆さん、及びtesterの方々、ありがとうございました。

作問の楽しさに気付いてしまったのでまた出題したいですね。

 

n重ループを書きたくなる再帰全探索を巻き戻しテクを使って解く

先日のABC165-Cが難しかったようなので、おすすめの実装法を紹介してみます。
この問題に限らず、愚直にやるとn重ループを書きたくなってしまう全探索問題全般に適用できるのでオススメです。

問題リンク:
atcoder.jp

とりあえずコードを乗せます。

#include <iostream>
#include <vector>
#include <iterator>
using namespace std;

int n, m, q;
int a[50], b[50], c[50], d[50];

int dfs(vector<int> &v)
{
  if (v.size() == n)
  {
    // 数を選び終わったのでシミュレート
    int sum = 0;
    for (int i = 0; i < q; i++)
    {
      if (v[b[i]] - v[a[i]] == c[i])
        sum += d[i];
    }
    return sum;
  }

  int last = (v.empty() ? 1 : v.back());
  int Max = 0;
  for (int i = last; i <= m; i++)
  {
    // 追加 -> 先を探索 -> 削除
    v.push_back(i);
    Max = max(Max, dfs(v));
    v.pop_back();
  }
  return Max;
}

int main()
{
  cin >> n >> m >> q;
  for (int i = 0; i < q; i++)
  {
    cin >> a[i] >> b[i] >> c[i] >> d[i];
    a[i]--, b[i]--;
  }
  vector<int> v;
  cout << dfs(v) << endl;
  return 0;
}

関数dfsは「現在選んだ数が順にv1, v2, ..., viであるとき、それ以降の要素をうまく定めたときの題意の値の最大値」を取得する関数です。
引数にvectorの参照を取ることで、どの階層においても同じvectorを参照できます。別に参照じゃなくてもいい場合もありますが、値のコピーが行われるため遅いです。

vectorのサイズがnのときは数をn個選び終わったということなので、問題文の値をシミュレートした結果を返します。

それ以外のとき、vectorの末尾の要素(vectorが空の場合は1)をlastとすると、次に選べる数はlast, last+1, ..., Mとなります。
追加する要素をiとしたとき、

vectorの末尾にiを追加する。
・要素を追加した新たなvectorに対してdfsを呼ぶ。返値の最大値を更新する。
vectorの末尾を削除する。

という操作をひとまとめにして行うことで、各ループの開始時と終了時にvectorの値が変化しないようにしつつ先の探索を行うことが出来ます。

イメージとしては、数を追加してその先を全て調べた後、Undo操作を行って追加をなかったことにする感じ。


この考え方は同じような問題全般に適用できます。
抽象的に言い換えると、

・あるコンテナ(再帰関数全体において共通)に変更を加える。
・関数を再帰的に呼び、先を探索する。
・変更を打ち消す操作を行い、変更をなかったことにする。

となります。このとき変更および変更のUndo操作が高速に動作する必要があります。変更/Undoの計算量が重い場合は別の方法を検討しましょう。(DFSが想定解の問題ではあんまりなさそう?)

類題

パナコン2020-D String Equivalence

問題リンク:
atcoder.jp

こちらもかなり難しいと言われていた気がします。

文字列c1c2c3...ciに新たな文字を追加する際に追加できるのは、今まで使った文字、及び使用済み文字の(アルファベット順で)最大のものより1だけ大きい文字に限ります。
現在の文字列とその文字列内の最大の文字を引数に取ることで上手くいきます。

提出コード:
Submission #12677860 - Panasonic Programming Contest 2020


ABC114-C 755

問題リンク:
atcoder.jp

こちらも同様のDFS全探索題です。ただし今回は長さが特に決まっているわけではないので注意です。

提出コード:
Submission #12678082 - AtCoder Beginner Contest 114
(あまりきれいではないですが、頭を使わずに書けるのが強みです。)


ABC165-F LIS on Tree

問題リンク:
atcoder.jp

同コンテストで出題された、木上の狭義最長増加部分列(LIS)を求める問題。
全探索ではないですが、vectorの扱い方が先程の問題と同じなので紹介しておきます。
LISについてはこの記事が詳しいです。
qiita.com


先程と同様に、dpテーブルを更新、先を探索、更新を取り消すとすればよいです。
dpテーブルを更新した際にその頂点までのLISも求めておきましょう。

提出コード:
Submission #12677558 - AtCoder Beginner Contest 165


おわりに

n重ループは視認性がアレなので再帰関数を使いましょう。(コンテスト本番に関してはその限りではない)
最近はABCや企業コンの300, 400あたりにDFS全探索題が多いので再帰を使えると強みになると思います。