3匹の猫

みみねこの競プロ精進メモ

助けてください【ACLを含むとコンパイルできない】

手元環境でACLAtCoder Library)が使えない
参考:AtCoder公式告知ページAtCoder Library (ACL) - AtCoder

環境

まじで何もわからないので手あたり次第に書いていく

OS:Windows10 Home

エディタ:VSCode

f:id:mmnkblog:20201022102520p:plain
VSCodeのバージョン情報(コミットだけなんか怖いのでモザイク)

コンパイラ:MinGWのg++(gcc version 9.2.0 (MinGW.org GCC Build-2) )。Pathを通しているのでどこのフォルダからもコンパイルできるはず。

ディレクトリ?の構成:C:/HOGEHOGE/kyopuroソースコードを保存している。

ACLの入手元:
GitHub - atcoder/ac-library: AtCoder Library
から。リポジトリがあったのでクローンした。するとac-libraryというフォルダがC:/HOGEHOGE/kyopuro/ac-libraryというような位置に配置された。また、リファレンスを読むとac-libraryフォルダのなかにatcoderというフォルダがあって、それを普段使っているフォルダに置けと書かれているのでC:/HOGEHOGE/kyopuro/atcoderとなるようにコピペして貼り付けた。(コピペしていいのだろうか?)

コード

ファイル名はmain.cppC:/HOGEHOGE/kyopuro/main.cpp

3^{10}\pmod {10^9+7}を出力するだけ。3^{10}=59049なのでmodを取る必要はないが、まあACLを使う例と考えてください。

#include <iostream>
#include <atcoder/all>

int main(){
	long long ans = atcoder::pow_mod(3, 10, 1000000007);
	std::cout << ans << std::endl;
	return 0;
}

手元の環境でやりたいこと

以下のコマンドでファイルmain.cppコンパイルして、実行したい。
g++ main.cpp -o main -std=c++17 -I .

実行した結果

コンパイルに失敗し、次のようなメッセージが出力される。(長すぎるので前半部分だけ)

PS C:\HOGEHOGE\kyopuro> g++ main.cpp -o main -std=c++17 -I .
In file included from ./atcoder/internal_math:1,
                 from ./atcoder/modint.hpp:4,
                 from ./atcoder/modint:1,
                 from ./atcoder/convolution.hpp:7,
                 from ./atcoder/convolution:1,
                 from ./atcoder/all:1,
                 from main.cpp:1:
./atcoder/internal_math.hpp: In member function 'unsigned int atcoder::internal::barrett::mul(unsigned int, unsigned int) const':
./atcoder/internal_math.hpp:56:36: error: expected primary-expression before 'unsigned'
   56 |             (unsigned long long)(((unsigned __int128)(z)*im) >> 64);
      |                                    ^~~~~~~~
./atcoder/internal_math.hpp:56:36: error: expected ')' before 'unsigned'
   56 |             (unsigned long long)(((unsigned __int128)(z)*im) >> 64);
      |                                   ~^~~~~~~~
      |                                    )
./atcoder/internal_math.hpp:56:68: error: expected ')' before ';' token
   56 |             (unsigned long long)(((unsigned __int128)(z)*im) >> 64);
      |                                  ~                                 ^
      |                                                                    )
./atcoder/internal_math.hpp:56:68: error: expected ')' before ';' token
   56 |             (unsigned long long)(((unsigned __int128)(z)*im) >> 64);
      |                                 ~                                  ^
      |                                                                    )
In file included from ./atcoder/internal_type_traits:1,
                 from ./atcoder/modint.hpp:5,
                 from ./atcoder/modint:1,
                 from ./atcoder/convolution.hpp:7,
                 from ./atcoder/convolution:1,
                 from ./atcoder/all:1,
                 from main.cpp:1:
./atcoder/internal_type_traits.hpp: At global scope:
./atcoder/internal_type_traits.hpp:15:47: error: '__int128_t' was not declared in this scope; did you mean '__intptr_t'?
   15 |     typename std::conditional<std::is_same<T, __int128_t>::value ||
      |                                               ^~~~~~~~~~
      |                                               __intptr_t
./atcoder/internal_type_traits.hpp:15:57: error: template argument 2 is invalid
   15 |     typename std::conditional<std::is_same<T, __int128_t>::value ||
      |                                                         ^
./atcoder/internal_type_traits.hpp:16:59: error: template argument 2 is invalid
   16 |                                   std::is_same<T, __int128>::value,
      |                                                           ^
./atcoder/internal_type_traits.hpp:18:46: error: template argument 1 is invalid
   18 |                               std::false_type>::type;
      |                                              ^
./atcoder/internal_type_traits.hpp:22:47: error: '__uint128_t' was not declared in this scope; did you mean '__uintptr_t'?
   22 |     typename std::conditional<std::is_same<T, __uint128_t>::value ||
      |                                               ^~~~~~~~~~~
      |                                               __uintptr_t
./atcoder/internal_type_traits.hpp:22:58: error: template argument 2 is invalid
   22 |     typename std::conditional<std::is_same<T, __uint128_t>::value ||
      |                                                          ^
./atcoder/internal_type_traits.hpp:23:68: error: template argument 2 is invalid
   23 |                                   std::is_same<T, unsigned __int128>::value,
      |                                                                    ^
./atcoder/internal_type_traits.hpp:25:46: error: template argument 1 is invalid
   25 |                               std::false_type>::type;
      |                                              ^
./atcoder/internal_type_traits.hpp:29:47: error: '__int128_t' was not declared in this scope; did you mean '__intptr_t'?
   29 |     typename std::conditional<std::is_same<T, __int128_t>::value,
      |                                               ^~~~~~~~~~
      |                                               __intptr_t
./atcoder/internal_type_traits.hpp:29:57: error: template argument 2 is invalid
   29 |     typename std::conditional<std::is_same<T, __int128_t>::value,
      |                                                         ^
./atcoder/internal_type_traits.hpp:30:31: error: '__uint128_t' was not declared in this scope; did you mean '__uintptr_t'?
   30 |                               __uint128_t,
      |                               ^~~~~~~~~~~
      |                               __uintptr_t
./atcoder/internal_type_traits.hpp:31:48: error: template argument 1 is invalid
   31 |                               unsigned __int128>;
      |                                                ^
./atcoder/internal_type_traits.hpp:31:48: error: template argument 2 is invalid
./atcoder/internal_type_traits.hpp:31:48: error: template argument 3 is invalid
./atcoder/internal_type_traits.hpp:31:49: error: expected identifier before ';' token
   31 |                               unsigned __int128>;
      |                                                 ^
./atcoder/internal_type_traits.hpp:35:51: error: 'is_signed_int128' was not declared in this scope  
   35 |                                                   is_signed_int128<T>::value ||
      |                                                   ^~~~~~~~~~~~~~~~
./atcoder/internal_type_traits.hpp:35:69: error: wrong number of template arguments (1, should be 3)
   35 |                                                   is_signed_int128<T>::value ||
      |                                                                     ^

こだわり

こうすれば動く集

ACL関係の記述をやめる

シンプルに出力するだけ。コマンドは変えなくても動いたので、コンパイラはちゃんと生きているはず。

#include <iostream>

int main(){
	long long a = 59049;
	std::cout << a << std::endl;
	return 0;
}

AtCoderのコードテストに投げる

そのまま投げたら普通に通ったので、ソースコード中に文法などのミスがある可能性はつぶれた。

こうしても動かない集

インクルードするのをatcoder/allじゃなくてatcoder/mathにしてみる

pow_modはatcoder/mathにあるのでやってみた。

#include <iostream>
#include <atcoder/math>

int main(){
	long long ans = atcoder::pow_mod(3, 10, 1000000007);
	std::cout << ans << std::endl;
	return 0;
}

コンパイルは通らなかったがエラーメッセージの量が10分の1くらいに減った。(以下全文ママ)

PS C:\HOGEHOGE\kyopuro> g++ main.cpp -o main -std=c++17 -I .
In file included from ./atcoder/internal_math:1,
                 from ./atcoder/math.hpp:8,
                 from ./atcoder/math:1,
                 from main.cpp:2:
./atcoder/internal_math.hpp: In member function 'unsigned int atcoder::internal::barrett::mul(unsigned int, unsigned int) const':
./atcoder/internal_math.hpp:56:36: error: expected primary-expression before 'unsigned'
   56 |             (unsigned long long)(((unsigned __int128)(z)*im) >> 64);
      |                                    ^~~~~~~~
./atcoder/internal_math.hpp:56:36: error: expected ')' before 'unsigned'
   56 |             (unsigned long long)(((unsigned __int128)(z)*im) >> 64);
      |                                   ~^~~~~~~~
      |                                    )
./atcoder/internal_math.hpp:56:68: error: expected ')' before ';' token
   56 |             (unsigned long long)(((unsigned __int128)(z)*im) >> 64);
      |                                  ~                                 ^
      |                                                                    )
./atcoder/internal_math.hpp:56:68: error: expected ')' before ';' token
   56 |             (unsigned long long)(((unsigned __int128)(z)*im) >> 64);
      |                                 ~                                  ^
      |                                                                    )
PS C:\HOGEHOGE\kyopuro>

ACLGithubからじゃなくてZIPファイルから持ってくる

バージョン管理が楽だとsnukeさんが言っていたので頑張ってGithub経由で落としてみたがそれが原因かもしれないので、ZIP形式で配布されている方を解凍してその中のatcoderフォルダをコピペして使うことにした。
結果変わらず。

自分なりに調べた内容について

エラーを読み解く

./atcoder/internal_math.hpp: In member function 'unsigned int atcoder::internal::barrett::mul(unsigned int, unsigned int) const':
./atcoder/internal_math.hpp:56:36: error: expected primary-expression before 'unsigned'
   56 |             (unsigned long long)(((unsigned __int128)(z)*im) >> 64);
      |                                    ^~~~~~~~

上記のエラーのあたりを頑張って読むと、「『unsigned』の前にprimary-expressionが来るんじゃないの?」「括弧の対応がおかしくない?」みたいなことを言われてるっぽい。ただ、コンパイラが指摘しているファイルはACLの中身なので、これを書き換えたところで根本的な解決にはならない。
エラーを読んでわからないときはGoogleの検索欄にコピペしてみると良い。C++くらい有名な言語だと日本語でまとめられていることも多い。
qiita.com
上記の記事によれば、明示的な型変換ができる型(simple-type-specifier)とできない型が存在するらしい。例として、signed charlong longは明示的型変換ができないと書かれている。特にこの記事では、gccコンパイラでのみエラーが出たと書いてあるのでgccを使っているせいなのかもしれない。
ACLunsigned long long型の変数をunsigned __int128に変換しているが、これは果たして明示的型変換ができる型なのか?
en.cppreference.com
ここでリファレンスを読んで明示的型変換ができる型の一覧のようなものを見つけたが、そもそも「__int128」って何なのかよくわかってないことに気付く。今まで使ったことない(多分128bitのクソデカint型みたいなやつなのは想像つく)ので、それを調べてみる。

boostとかが関係してるらしい?調べてもよくわからなかったが、__int128はやっぱりlong long型よりでかい128bitの多倍長整数型のことをいうらしい。__int128_tというパチモンもみつけたけど違いが分からない。おわり

コマンドが悪いのか?

ここまでで、何のせいでコンパイルできないのか考える。gccACLの相性が悪いせいに見えるが、AtCoderのコードテストは通っている。なので、うちの環境にいるgccと、AtCoderにいるgccは別物で、うちのgccACLの相性が悪いのかな?
ここで、AtCoderで「C++(GCC9.2.1)」を選択してコンパイルするときに実行されるコマンドは以下のものである。
g++ -std=gnu++17 -Wall -Wextra -O2 -DONLINE_JUDGE -I/opt/boost/gcc/include -L/opt/boost/gcc/lib -I/opt/ac-library -o ./a.out ./Main.cpp
ここで見たことのないオプションがいくつか見えるので全部解読する。

-std=gnu++17:早速違うものが出てきたのでこれで手元でも実行してみるが変わらず。
-Wall:文法チェックのために警告・エラーをすべて表示するオプション。
-Wextra:これも警告を全部出すオプション。
-O2:最適化オプション。
-DONLINE_JUDGE第 3 章 C++ コンパイラオプションの使い方 (Sun Studio 12 Update 1: C++ ユーザーズガイド)によれば、シンボル ONLINE_JUDGE をプリプロセッサに定義します。よくわからない
-I/opt/boost/gcc/include:boostという名前があるので、これがあると__int128が使えるようになるのかな?とおもったけど特に変わらず。
-L/opt/boost/gcc/lib:このディレクトリにあるライブラリを検索しているらしい。
-I/opt/ac-libraryatcoderフォルダではなくac-libraryフォルダを指定している。そういえばatcoderフォルダはac-libraryフォルダに含まれているのだからわざわざコピペしなくてもいいのか。序盤にあった謎が一つ解けた!
-o ./a.out ./Main.cpp:この辺の関係がよくわからない

とりあえず今日はここまで(解決しなかったら追記予定)。もし記事を読んでいる方でこれが原因じゃないの?と思うことがあれば、どんなに細かいことでも遠慮なくお願いします…

ACL Beginner Contestの感想

略称はABLらしい。明日から使えるムダ知識をあなたに

100-200-300(1)-0-0-0で1ペナ3完600点。

A - Repeat ACL

ACLという文字列をK回だけ出力する。Kは5パターンしかないのでif文を用いて5通りの分岐を記述すると解ける。また、ループを用いると問題文の処理をそのまま実装できるので楽。

計算量は、O(K)

B - Integer Preference

A以上B以下の範囲をXC以上D以下の範囲をYと呼ぶことにする。

2人が好きな整数が存在するということは、範囲Xと範囲Yが重なっているということ。ここで、①「範囲Xの最大値が範囲Yの最大値より小さい」と仮定すると、範囲Xの最大値が範囲Yの最小値より大きければ重なっていることがわかる(等しくても重なる)。これは入力の数値を用いて表現するとC \le Bで判定できる。もし①の条件を満たしていないならACBDを入れ替えることで同様の判定式で判定できる。

計算量は、O(1)

f:id:mmnkblog:20200926233151p:plain
BよりDの方が大きいことを仮定した場合の範囲の重なり方

C - Connect Cities

都市を頂点、道路を辺と見たグラフを考える。1回の操作により、異なる2つの連結成分*1 を辺でつなぐことができる。初めの状態で連結成分がX個あるなら、この操作をX-1回行えば必ず連結成分が1個になるので、答えはX-1である。

あとは連結成分の個数を数えられれば良い。これにはDFSを用いて全頂点を走査する方法や、UnionFindで頂点集合を管理する方法がある。今回はUnionFindを用いて実装した。

ACLでは、UnionFindという名前ではなく「DSU(Disjoint Set Union)」と呼ばれている。同じ集合に属するならばその集合の代表元も同じなので、setなどを用いて代表元の個数を数える。

計算量は、DFSを用いる方法でO(N)、UnionFindとsetを用いる方法でO(N\log N)

D - Flat Subsequence

ここから解けなかったので簡潔に書く。

DP。単純に書くと遷移にO(N^2)かかってしまうところを、セグ木を使うとO(N\log N)で書ける。

E - Replace Digits

遅延セグ木を使うと(Q\log N)で書ける。

感想

水色なのに茶パフォとってしまったのでしばらく謹慎する

*1:無向グラフにおいて、辺でつながっている頂点のまとまりのこと

実力もないのに数学力だけで水色に這い上がるな

AtCoderACLを非難する記事ではありません。


実力もないのに数学力だけで水色に這い上がって生きてきた僕は今回のABLで茶パフォを出しました。原因はACLに含まれているものを中心としたデータ構造の性質の理解と、その応用例に関する知識不足です。つまり僕が100%悪いです

克服するために少なくともACLのpracticeコンテストの問題全部通すまではコンテストに一切出ないことにします。精進する時間もとれなさそうなのでしばらくはコンテストに出ないと思います。


タイトルは自分を含めた競プロerに向けた警告です。数学力だけあってもだめです数学問が出ても周りは「数学問かよー」というだけで喜んでるのはお前だけですいいことは何一つないのでこれを読んでいる数学得意なまじめな人はコツコツ学んでコツコツレートをあげましょう

AtCoder Beginner Contest 179の感想

「愚直にやると遅いから高速化する!」の考えは大事。

100-200(1)-300-400-500-0で1ペナ5完1500点。

A - Plural Form

文字列を複数形に変換する。文字列の末尾がsかそうでないかで処理が変わる。具体的な処理の流れとしては、入出力を除くと「文字列の末尾の文字を取得」「その文字がsかどうかを判定」「文字列の末尾に文字列を連結」の3つとなる。それぞれの処理の仕方がわからないときは素直にググるべし。

計算量は入出力がボトルネックで、O(|S|)

B - Go to Jail

iに対して、サイコロの目がゾロ目かどうかを保存するboolean型の配列を用意する。この配列の中で、"true"が3個以上続いている箇所を調べたい。この判定は、「今"true"が何個続いているか?」という変数を用意して、前から順番にi番目とi+1番目の値を判定していくとできる。どちらも"true"なら変数の値を1増やし、そうでないなら変数を0にする(0にするのを忘れて1ペナ)。変数の値を0にする直前の値が連続でゾロ目が出た回数なので、この回数が1度でも3以上になったことがあるなら答えはYesとなる。

計算量はO(N)

C - A x B + C

愚直に解くなら、1からNまでの範囲でA, B, Cを回して実際に計算するという方法がとれる。ただしこの方法だと計算量はO(N^3)となりTLEしてしまうので、効率の良い別の解法を考える。

Nが固定されているので、他のもう1文字を固定して考えるとよさそうだと考える。どの文字を固定するかで解法が変わる。

  • Aを固定する場合

この場合、Bを決めれば元の式を変形させることでC = N - A \times Bとなり、Cの値が1パターンに決まる。Cの値は正でないといけないので、0 \lt C = N - A \times Bである。変形するとA \times B \lt N、さらに変形するとB \lt \frac{N}{A}となり、Bの値も一意に決まることがわかる!(不等号を等号に直せばB = \lfloor \frac{N-1}{A}\rfloor となる)
あとはAに関するループを回して総和を取ればよい。計算量は、O(N)

  • Cを固定する場合

式変形するとAB = N-Cとなるので、N-Cの約数がいくつあるかを数えたい。ある整数に対して約数の個数を求めるのにはO(\sqrt{N})の計算量がかかるので、全体ではO(N\sqrt{N})の計算量となり、このままだと間に合わない可能性が高い。ここで、N-Cの値は1からN-1まで連続した値をとるという特徴を利用すると、約数の個数の総和を計算量O(N\log N)で高速に計算することができる。やり方を書こうと思ったけどうまく書けなかったので、これは読者への課題とする…(ググって)
全体の計算量ももちろんO(N\log N)


どちらの方法でもすぐ通せるようならかなり強いと思う。今回はAを固定する方法で通した。

D - Leaping Tak

dp[i] := マスiまで移動する通り数
という風な1次元の動的計画法を考えたいが、移動方法は最大でN通りあるため、普通に書くと計算量がO(N^2)となりTLEする。(公式解説を見ると、実はO(N\log N)でも解けるらしい?)

現在見ているマスをiとすると、入力が区間で与えられることから移動先となりうるマスはある程度固まっていることがわかるので、これを利用する。先ほどの配列dpのほかにもう一つの配列aを用意して、区間の始まりであるa[i+L]dp[i]を足し、区間の終わりであるa[i+R]dp[i]を引く。こうすることで、配列aに対して累積和を前から実行でき、マスiまで見たときのa[i]はまさにマスiまでの遷移方法の通り数となる。

計算量は、O(NK)

E - Sequence Sum

愚直に計算するとO(N)だが、制約が大きいためTLEとなる。より高速な解法を考える。

数列Aの各項はすべてMで割った余りであるので、各項の値は0以上M未満である。さらに数列Aはひとつ前の項に対する漸化式によって定義されているため、同じ値が2回以上登場するなら、そこから周期的にループする。ここで鳩ノ巣原理より、第(M+1)項までに値が重複するので、「第1項から周期に乗るまでの総和」+「周期を繰り返した回数×1周期の項の総和」+「1周できなかった分の余りの総和」が答えとなる。これを求めるには、周期の長さと1周期の総和がわかればよい。

計算量は、O(M)

ちなみにダブリングというテクニックでも解けるらしいがそちらの方はわかりません。一般に、周期に注目して解ける問題はダブリングでも解ける、は正しそうだけど、どうだろうか。

F - Simplified Reversi

解けなかった。愚直に石を置き換える解法だと、空間計算量の時点ですでにO(N^2)かかるため現実的ではない。黒い石で構成された長方形領域を考えるとき、操作を加えても分割される長方形は高々1つだけで、すべてのクエリが終わっても領域の個数はN個ほどしかないな、ということには気づいた。これを使ってうまく解けないか悩んでいたがここでタイムアップ。この発想はかなり近いところまで行ってたようで、例えば縦のラインに白い石が置かれたとき、それより右側の黒い石が置き換えられるのは縦に置くようなクエリが飛んできた時だけなので、そのような列(同様に行も)をメモしておけばよかったっぽい。

終了時のTwitterのTLを見た限りでは、遅延セグ木で解いている人が多そうだった。遅延セグ木がわからないのでもっと精進します。


感想

D問題に少し時間をかけてしまったがしっかり5完できたのはよかった。

AtCoder Beginner Contest 178の感想

具合が悪いのでさらっと書きます

100-200-0-400-0(3)-0でノーペナ3完700点。

A - Not

1なら0を、0なら1を出力する。if文で実装できるし、排他的論理和でエレガントに書くこともできる。O(1)

B - Product Max

全通り試すと間に合わない。(B問題にしては厳しいね?)
負の数×負の数=正の数 だったりするので場合分けをしようか迷うが、よく考えると範囲の最大値・最小値の組み合わせをすべて試せばそのどれかが最大値となる。
\max (ac, ad, bc, bd)が答え。O(1)

C - Ubiquity

考えられる数列の総数は10^N通り。0を使わない数列は(10-1)^N通り。9を使わない数列は(10-1)^N通り。0も9も使わない数列は(10-2)^N通り。
実はこれらの数値が求められれば、あとは包除原理で導出できる。10^N-2\times 9^N+8^Nが答え。O(N)

D - Redistribution

dpで解いた。
dp[i][j] := 数列の長さがiで、その総和がj
とする。遷移を簡単にするために、数列に0以上の整数、つまり3未満の数も含んでいいことにする代わり、答えを求めるときは数列の全要素に3を足したものとしてみる。
遷移は、dp[i+1][j] = dp[i][j] + dp[i][j-1] + ... + dp[i][0]となる。実装時は累積和を使って右辺をO(1)で求める。
dp[i][S - 3 * i]の総和が答え。O(S^2)

E - Dist Max

(追記:誤答の内容について)木の直径を求める感じで、「ある適当な点から一番遠い点」から一番遠い点までの距離を出力したがWAだった。2点間の距離は木ではなくグラフである。

Googleによると、45度回転させてマンハッタン距離をチェビシェフ距離に変換して軸ごとに見ると解けるらしい。やったことがないので解けませんでした。
ちなみに前にも45度回転させて考える問題を解けなかったので大反省。

F - Contrast

なんかAGCのA問題に出てきそうな問題。ちゃんと考えれば、元からソートされているのだから、Bを逆順にすればA_i=B_iとなるような数字は高々1種類しかないので、その時に数字の位置をずらせるかどうかだけ考えればよいっぽい。
細かいところまでは詰めてないので穴があるかもしれません。

感想

寝不足は敵

AtCoder Beginner Contest 177の解説・感想

100-200-300-400-500(1)-0で1ペナ5完1500点。

A - Don't be late

先週も同じような問題文見たな...(既視感)

2つの解法を紹介する。どちらも、「問題文で与えられたすべての変数を同時に見ない」のが特徴的。

解法1:T分後の待ち合わせ時刻に間に合うためには、どれだけの速さで移動すればいいか計算する。DメートルをT分で移動したい、つまり、1分間で\frac{D}{T}メートル移動したい。つまり、分速\frac{D}{T}メートル(以上)の速さで歩ければ待ち合わせ時刻に間に合わせることができる。ここで、高橋君は分速Sメートルで歩けるので、\frac{D}{T} \le Sなら間に合うことがわかる。

解法2:分速Sメートルで歩けるので、待ち合わせ時刻までのT分間ではS\times Tメートルまで移動することができる。ここで、待ち合わせ地点まではDメートルあるので、D \le S\times Tなら間に合うことがわかる。

どちらの解法も、最終的に同じ不等式が導出されていることがわかる。ただし解法1の不等式では整数同士の割り算が登場しており、切り捨ての処理などが発生すると正しい答えが得られない可能性があるので、「答えを小数で出す」「両辺に同じ数をかけて割り算を掛け算に直す」などの処理をした方が安心!

計算量は、O(1)

B - Substring

むずくないか?

文字列Sの長さをS.len()、文字列Tの長さをT.len()とする。

文字列Sのどこの文字をどんな文字に変更すれば最適なのかを調べたい。ここで、Sの何文字目からTと一致するのかを全探索する。1\le j\le S.len() - T.len() + 1を満たすjに対して、Sj文字目からのT.len()文字をTと一致させたい。逆に言えば、このT.len()文字以外の文字はどんな文字でも関係ない!1\le i\le T.len()を満たすiに対して、S(j+i)文字目とTi文字目が異なっている箇所が何か所あるか数えて、異なっている箇所が一番少なくなるようなjを選べばよい!(説明がむずい!)
聞かれているのは「何文字変えるか?」である。STで異なっている箇所だけ変えればよく、その個数は先ほど数えたものそのままなので、それを出力すればよい。
計算量は、O(S.len()\times T.len())

C - Sum of product of pairs

計算量について学べる良い数学問。

問題文の通りに実装すると、計算量がO(N^2)となり、実行時間制限に間に合わない(TLE)。なので、計算方法を工夫する必要がある。

i\lt jであり、A_jとかけられる数はA_1, A_2, \dots , A_{j-1}(j-1)個ある。これらの総和は、分配則を用いるとA_j(A_1 + A_2 + \dots + A_{j-1})となる。このうち、A_1 + A_2 + \dots + A_{j-1}の部分はjから(j+1)に増えるときA_jだけ増えるので、jについてのループを前から回していけば計算することができる。この場合の計算量は、O(N)となり、高速に計算できるのでACとなる!

ちなみに、Sum = (全てのA_iの合計)として、((Sum - A_i) \times A_i)の総和を2で割ることでも答えを求められる(九九の表みたいなのをイメージするとわかりやすい)。

D - Friends

すぐ解けたのでよかった(小並感)

「人」を頂点、「人と人が友達であること」を辺と見ると、グラフの構造に落とし込める。さらに、友達の友達は友達であるという条件より、友達同士の人を集めた集合がいくつかできることもわかる。このような集合がいくつかあるN人をグループに分けるとき、同じグループに友達同士の人がいないようにするには、同じ友達同士の集合から2人以上選ばないようにすると良い。つまり、最大P人の友達集合があるなら、少なくともP個のグループを作ってそこに1人ずつ振り分ける必要がある。逆に、友達ではない関係の人は同じグループに何人いても問題ないので、Pがいくつか求められれば良い!

友達同士の集合を構成するには、例えばUnionFindというデータ構造を用いると上手くいく。UnionFindでは、2頂点を連結したり、ある頂点がどの集合に属するかを調べたりするのをとても高速に行うことができる。入力を受け取る過程で集合を作り、その集合の要素数の最大数を求めればよい。計算量は、およそO(N)*1

ほかにも、幅優先探索で連結成分を調べると同様に解ける。

E - Coprime

提出前にコーナーケースを確かめず1ペナしてしまった…。

この問題は、「pairwise coprimeであるか」「setwise coprimeであるか」の2種類の判定問題を解くことができれば正解となる。

2種類のうち、「setwise coprimeであるか」は比較的簡単に求められる。3つ以上の正の整数に対して、最大公約数を求める関数をgcd()とすると、この関数は結合則が成り立つ。つまり、gcd(A_1, gcd(A_2, gcd(A_3, \dots)))という風に2組の最大公約数を順に求めていけばN個の数の最大公約数が求まる。このパートの計算量は、2数の最大公約数の計算にO(\log A_i)かかるので、全体でO(N \log A_i)となる。

残った「pairwise coprimeであるか」について。もしpairwise coprimeでないなら、共通する素因数が1つ以上存在するはずである。それぞれの数を素因数分解して素因数を調べることで、共通する素因数があるかどうかがわかる。一つの数を素因数分解するのにO(\sqrt A_i)かかるので、全体でO(N\sqrt A_i)となり、制約よりおよそ10^9回の計算が必要となるが、A_i以下の素数の個数を\pi(A_i)とすると、素数定理より\pi(A_i) \fallingdotseq \frac{A_i}{\log A_i}と表せるあるため、鳩ノ巣原理より素因数が被った時点で探索を打ち切れば計算量はおよそO(\frac{A_i\sqrt A_i}{\log A_i})となる。この計算量の式に制約の最大値を代入して計算するとおよそ5\times 10^7回の計算となり、十分高速に計算できる。

あとは問題文の通りに条件分岐させれば答えが求められる。全体の計算量は、およそO(A_i(\log A_i + \frac{\sqrt A_i}{\log A_i}))となる。(式が複雑で自信がない…)

または、素因数分解をするパートでかわりにエラトステネスの篩を用いることで「pairwise coprimeかどうか」を計算することもできる。

F - I hate Shortest Path Problem

難しい。解けなかった。

まとめ

今回のコンテストでレートが1400を突破した。この調子で青色まで行きたい!

*1:正確には、アッカーマンの逆関数がかかるが、今回の制約では無視できるほど小さい

AtCoder Beginner Contest 176の解説・感想

100-200-300-400(2)-500-0で2ペナ5完1500点。

A - Takoyaki

T分間にX個のたこ焼きを作れるので、実際に1分ずつシュミレーションしていけばよい。現在焼いたたこ焼きの個数を変数で管理して、T分経つごとにX個増やしていき、初めてN個を超えた時の時間を出力する。計算量はO(\frac{NT}{X})
と、ここまでしなくても、T分ごとにたこ焼きの個数が増える以外の出来事が起こらないので、T分ごとに見ればよいことがわかる。つまり、たこ焼き機で一回焼くごとにX個のたこ焼きが増えるとき、何回焼けばN個以上になるかをシュミレーションすればよい。計算量はO(\frac{N}{X})
さらに、T分ごとに増えるたこ焼きの量は一定なので、シュミレーションしなくても割り算で答えを求めることができる。答えを求める式は\lceil \frac{N}{X} \rceil \times Tとなる。計算量はO(1)
このように、ABCのA問題はO(1)の計算量でも解ける(for文を使わなくても解ける)ように作られていることが多い(絶対ではない!)。

B - Multiple of 9

Nの値が非常に大きく、最大ケースでは2\times 10^5桁近くにもなるため、例えばC++のlong long型などで管理することはできない。*1
なので入力を工夫して、文字列型で受け取ることにする。あとは問題文の通りにNの各桁の数字をすべて足し合わせて、9で割った余りが0ならYesを、そうでないならNoを出力する。計算量はO(\log N)

C - Step

一番前の人から順番に、「A_i\le A_{i+1}を満たしているか?」を見ていけばよい。もしA_i\gt A_{i+1}となっている箇所があれば、高さA_i-A_{i+1}の踏み台を設置してあげることで、A_i=A_{i+1}を達成できる。この時、A_{i+1}の身長をA_iと同じになるよう変更することで、計算量O(N)で解くことができる。

D - Wizard in Maze

2回TLEを出してしまった問題。
最初に試したのは、ワープ0回で行けるところをDFSで探索し、そのあとワープ魔法を1回使って到達できるところをメモし、DFSで探索、ワープ2回で行けるところを…という風にした。しかしこの場合、最悪計算量がO(H^2W^2)となり間に合わない。
そこで、BFSを用いた実装に方針を変えた。始点のマス(C_h, C_w)から探索を始めて、現在探索しているマスから
・上下左右4方向に隣り合うマス(ワープ回数そのまま)
5\times 5の範囲内にあるマス(ワープ回数+1)
をpriority_queueに挿入して、ワープ回数が少ない順に取り出すようにした。しかしこのとき、priority_queueから要素を取り出した後にそのマスにたどり着くために必要なワープ回数を更新していたので、そのマスが取り出されるまでの間複数回同じマスが挿入されてしまう場合があり、再びTLEした。なので、priority_queueに挿入されることが決まった時点でマスのワープ回数を更新することで、同じマスが複数回priority_queueに挿入されることを防いだ。計算量はO(HW)
ちなみに、dequeを用いた01-BFSでの解法もあるらしい。なかなか発想が出てこない…。

E - Bomber

D問題よりこちらの方が簡単だった。D問題はどちらかというと実装よりの典型問題という気がする。
ある行とある列を選んだとき、その行と列に含まれる爆破対象の個数が最大となるようにしたい。ここで、どの行を選んだかという情報とどの列を選んだかという情報はほぼ独立している。唯一、行と列の交点に位置するマスだけは考慮しなければならない。i行目にある爆破対象の個数をR_ij列目にある爆破対象の個数をC_jとする。R_iの最大値とC_iの最大値をそれぞれR_{max}, c_{max}として、R_i = R_{max}となるような行をすべて記憶しておく(例えば配列などにメモしておく)。列についても同様の処理を行う。
あとは、メモした行iとメモした列jの組み合わせをすべて試す。マス(i, j)に爆破対象があれば爆破できる爆破対象の個数がR_{max} + C_{max} - 1となる(行iと列jで重複してカウントしているため1を引く)。マス(i, j)に爆破対象がないなら、爆破できる爆破対象の個数がR_{max} + C_{max}となる。このとき、これ以上多く爆破することはできない*2ので、これが答えとなる。すべての行列の組み合わせについてマス(i, j)に爆破対象が存在するのなら、答えはR_{max} + C_{max} - 1となる。
計算量について、例えばマス(1, 1)、(2, 2)、...に爆破対象が存在するような場合、すべての行と列が最大値の候補となるため組み合わせがHW通りになってしまうが、その組み合わせの中で1つでも爆破対象が存在しないような行と列の組み合わせが見つかれば答えが確定するので、そこで探索を打ち切ってしまえばよい。爆破対象は高々M個しかないので、計算量はO(M)となる。(コンテスト中は嘘解法のように思えたが、ブログを書くために整理してるときに正当性を証明できた!!)

F - Brave CHAIN

軽く問題文を読んだだけ。しっかり考察すれば解けるタイプの問題だと思ったので後日チャレンジしてみます。

まとめ

D問題で2回TLEを出して挫折しかけたけどあきらめずにがんばって5完できたのでよかったです(小並感)。DFSやBFSをソラで書けるようになってて成長したなあと感じた!

*1:ちなみに、Python3では桁数の制限なく整数を保存可能なので、普通に入力を受け取って9で割るだけでACできる。

*2:これ以上多く爆破することができるのなら、R_maxかC_maxのどちらかが今より大きくないといけなくなるが、これは最大値なのでこれ以上大きくなることはない