yukicoder contest 402（線形代数コンテスト）開催記

2023/08/25

コンテストURL: https://yukicoder.me/contests/454

まずはお詫びから入らせていただきます。実は前回のコンテスト後に色々ありまして、尊敬する熟練のwriterさんから強い不快感のご表明を受け、具体的には非教育的であるというご批難に加えてyukicoderから他サイトに移住するようご提案をいただくという事態になりました。同じような不快感をお抱いきになった参加者の方々にはこの場で改めてお詫び申し上げます。

そういった事情もあり前回のコンテストから日が浅いうちにまたコンテストを開かせていただくと更なる不快感のもととなるのではないかと心配になり一旦コンテストに関わるのはやめた方が良いのではないかとも思いましたが、せっかくコンテスト予定が空いているので恥を忍んで再挑戦させていただきました。

もちろんただ開催するだけでなくいただいたご諫言をもとに色々と悩んで、どうすればより教育的になるかやどうすれば他サイトへの移住を促されずに済むかを考えました。例えば現状では典型を全く学べないという厳しいご批評をいただいたので、これまでより遥かに典型色の強い問題を混ぜていく試みを検討しました。コンテスト参加者にとって逆に新鮮さや面白みが減ってしまう危険性もありますが、その際はまたご意見をいただければちょうどいい塩梅を模索していきます。

加えて何名かの上級者の方々にご意見や改善すべき点を頂戴したので、それらを踏まえて自分なりにできることを行動に移していくつもりです。具体的には★4以下の解説は用語の大雑把な説明も追加するなどの改善を行い、更にアウトリーチ色の強い問題はできる限り以前より短い問題文を心掛けるようにいたします。ただし後者についてはあまりイメージができておらず、例えば同値な定義の中でより短いものを吟味して差し替えたり一般的な数学用語の定義を非表示（クリックして初めて開く）にしたりといった工夫であれば元々しているので、他に「こうしたらもっと簡潔になる」というアイデアをお持ちの方はぜひご教示いただけますと幸いです。

なお教育的か否かの基準は人それぞれであるなどの事情で教育的であることを諦めるべきというご提案も何人かにいただきましたが、競技プログラミングの勉強をしている一番の動機がその教育的側面であるという事情がございます。教育従事者であるため教育的であることに起因する動機が他の動機より著しく大きいため、そこを諦めてしまうとそもそも競技プログラミングの勉強を続けていく自信もなく、とりあえず教育的であることを目指すのは第一前提とさせていただきました。

もちろんこちらの動機は皆様には関係のないことだとは承知しておりますが、仮に教育的であることが様々な要因で積極的には到達不可能な目標であり諦めるべきであるという結論が共有される文脈ではそもそも非教育的であるというご批判を受けることもございませんので、少なくとも苦言を呈していただいたwriterさんの見解では改善のしようがあるものと考え、ひとまずは諦める必要がないものとして前提をご共有いただきますよう心からお願い申し上げます。

まだまだ勉強不足であり至らない点も多いかと思いますが、いただいたご意見を真摯に受け止めて改善していくつもりですのでよろしくお願いいたします。実際、ご意見をいただいてから今日に至るまで、競技プログラミングの勉強時間を大幅に削って入念に解説の見直しを行いました。口だけではなく実際に行動に移してまいりますので、ご指導ご鞭撻をいただけますと嬉しいです。

謝罪と今後のあり方ご説明は以上です。皆さんにとってはあまり面白くないだろう話を長々としてしまい申し訳ございません。

それではコンテスト内容に話題を移します。当初予定していた問題のうち２問に難易度の上方修正が必要でうち１問（F問題）は★2から★3.5への修正があったのですが、今回は事故（近いコンテストとの問題被りやtester作業中の難易度の急勾配発覚）をケアして予備問題を作成していたので１問をそれに差し替えてC問題としました。

全てのtester作業が終わって開催が決まったのもコンテスト開催2日前なのでタイミング的に全体testerを見つけるのは困難だと思ったので、１問１問丁寧にチェックをして本番に臨みます。特にいつも気がかりなのが★2.5周りの難易度勾配ですが、今回の★2.5であるC・D問題のうちC問題は上述の一件以降に一から細心の注意を払って練り上げたものでひときわ典型色が強いので、D問題との難易度反転はまず起こらないだろうと信じています。（※コンテスト本番での参加者の解き具合を参考にしてB問題の難易度を★2から★2.5に、D問題の難易度を★2.5から★3に上方修正しました。これにより最新の★2.5はB・C問題に変更となっています）

そして迎えたコンテスト当日です。問題のチェックを繰り返し、根を詰めすぎないように別の作問を進めたりして過ごしました。それでもついつい気になってしまい、結局開始直前にも再度問題のチェックをしていました。

今回も大きな事故はなく済んで良かったです。質問が１件もなかったのは大きな進歩かもしれません。参加者の皆様、testerの皆様、そして色々とご相談に乗ってくださった方々にこの場でお礼申し上げます。

今回は線形代数コンテストという趣旨でセットを組ませていただきました。線形代数の標準的なカリキュラムに沿った問題構成となっているので、線形代数に苦手意識がある人はぜひ難易度の低い問題から順に解いていって理解の確認をしてみてください。線形代数が得意な人でも満足していただけるように、背景や解説もかなり丁寧に書かせていただきました。

A問題行列累乗：行列の掛け算
B問題線形写像：行列表示
C問題特殊線形群の標準表現：逆行列計算
D問題一次変換と体積：行列式の幾何的意味づけ
E問題奇行列式：行列式の余因子展開
F問題完全列：掃き出し法と階数計算
G問題行列累乗根：対称行列の対角化
H問題一次変換と面積：総まとめ

次回は基礎論コンテストを予定しています。そちらも丁寧な解説を心がけておりますので、開催の際はぜひよろしくお願いいたします。

A: No.2441 行列累乗 ★
問題リンク：https://yukicoder.me/problems/no/2441 tester：t98sliderさん
線形代数を学ぶ時の最初の障壁が、行列の掛け算ですね。本問は競技プログラミングにおける線形代数の代名詞、行列累乗をそのまま問う問題です。 G問題の「行列累乗根」は本問と対になる問題です。「行列が与えられて、その冪乗を計算する」のは簡単なのに逆の「冪乗の計算が与えられて、元の行列を求める」のは難しいというところを実感していただけるようになっています。

A: No.2441 行列累乗 ★

問題リンク：https://yukicoder.me/problems/no/2441

tester：t98sliderさん

線形代数を学ぶ時の最初の障壁が、行列の掛け算ですね。本問は競技プログラミングにおける線形代数の代名詞、行列累乗をそのまま問う問題です。

G問題の「行列累乗根」は本問と対になる問題です。「行列が与えられて、その冪乗を計算する」のは簡単なのに逆の「冪乗の計算が与えられて、元の行列を求める」のは難しいというところを実感していただけるようになっています。

B: No.2442 線形写像 ★★☆
問題リンク：https://yukicoder.me/problems/no/2442 tester：t98sliderさん
※コンテスト本番での参加者の解き具合を参考にして難易度を★2から★2.5に上方修正しました。行列を学ぶと、行列の具体例として線形写像の行列表示を学びます。写像の管理や比較を愚直に行う際は各点での代入値（定義域が $0$ 次元でなければ無限個の数値データ）を保持しないといけませんが、線形写像に限れば行列表示という有限個の数値データの管理や比較に落とし込める、というのが行列の最も分かりやすい応用の１つですね。本問はそういった膨大なデータを行列表示という小さいデータに翻訳するありがたみを計算量の改善という形で学べるように考案した問題です。writer解以外にも色々な解法があると思いますが、特にtester解は測度論の応用という感じで面白いのでぜひ解説をお読みくださいますと嬉しいです。

B: No.2442 線形写像 ★★☆

問題リンク：https://yukicoder.me/problems/no/2442

tester：t98sliderさん

※コンテスト本番での参加者の解き具合を参考にして難易度を★2から★2.5に上方修正しました。

行列を学ぶと、行列の具体例として線形写像の行列表示を学びます。写像の管理や比較を愚直に行う際は各点での代入値（定義域が $0$ 次元でなければ無限個の数値データ）を保持しないといけませんが、線形写像に限れば行列表示という有限個の数値データの管理や比較に落とし込める、というのが行列の最も分かりやすい応用の１つですね。

本問はそういった膨大なデータを行列表示という小さいデータに翻訳するありがたみを計算量の改善という形で学べるように考案した問題です。writer解以外にも色々な解法があると思いますが、特にtester解は測度論の応用という感じで面白いのでぜひ解説をお読みくださいますと嬉しいです。

C: No.2443 特殊線形群の標準表現 ★★☆
問題リンク：https://yukicoder.me/problems/no/2443 tester：MasKoaTSさん
線形写像を行列に翻訳すると嬉しいことの１つに、全単射性の判定と逆写像の計算が簡単にできることです。写像の全単射性を愚直に判定しようと思うとやはり全ての代入値（$0$ 次元でなければ無限個の数値データ）を見なければならないわけですが、ひとたび行列表示を得てしまえば行列式や逆行列という有限個の数値データの計算に帰着することができます。一般の群では逆元計算のコストが非常に重いことが多く、実際に逆向きの計算の困難性が各種暗号の安全性を保証することになるわけですが、行列であれば逆元計算が非常に軽く処理できるわけですね。本問は競技プログラミングの典型色が強い問題で、累積和／累積積をある程度抽象化して理解できているか否かを問うものです。累積和／累積積は逆元が高速に計算できる場合に効率的なアルゴリズムであり、まさに上述した行列の逆行列の計算の軽さが活きる問題設定となっています。制約は優しめにしてあるので、セグメント木を使うことも可能です。セグメント木をある程度抽象化して理解できているかを確認したい場合もぜひverifyにご利用ください。

C: No.2443 特殊線形群の標準表現 ★★☆

問題リンク：https://yukicoder.me/problems/no/2443

tester：MasKoaTSさん

線形写像を行列に翻訳すると嬉しいことの１つに、全単射性の判定と逆写像の計算が簡単にできることです。写像の全単射性を愚直に判定しようと思うとやはり全ての代入値（$0$ 次元でなければ無限個の数値データ）を見なければならないわけですが、ひとたび行列表示を得てしまえば行列式や逆行列という有限個の数値データの計算に帰着することができます。一般の群では逆元計算のコストが非常に重いことが多く、実際に逆向きの計算の困難性が各種暗号の安全性を保証することになるわけですが、行列であれば逆元計算が非常に軽く処理できるわけですね。

本問は競技プログラミングの典型色が強い問題で、累積和／累積積をある程度抽象化して理解できているか否かを問うものです。累積和／累積積は逆元が高速に計算できる場合に効率的なアルゴリズムであり、まさに上述した行列の逆行列の計算の軽さが活きる問題設定となっています。

制約は優しめにしてあるので、セグメント木を使うことも可能です。セグメント木をある程度抽象化して理解できているかを確認したい場合もぜひverifyにご利用ください。

D: No.2444 一次変換と体積 ★★★
問題リンク：https://yukicoder.me/problems/no/2444 tester：Kazunさん
※コンテスト本番での参加者の解き具合を参考にして難易度を★2.5から★3に上方修正しました。行列式を学んだ後は、低次の場合の計算方法（サラスの公式）や幾何学的な意味を学びます。また、幾何学的な意味を学ぶことで行列式の準同型性も自然と理解できるようになりますし、線型写像の像や核の次元（特に全射性や単射性）と行列式の関係も納得しやすくなります。本問は行列式の幾何学的な理解を問うため、行列式を用いた体積計算や準同型性や像と核の次元を全て組み合わせた考察を要求させていただきました。準同型性は馴染みが薄いかもしれませんが、大きな計算を小さな計算の積み重ねに帰着させるために使えるということを学べるようにあえて符号と合同式という相性の悪い組み合わせを出題しました。幾何学的意味を問う部分の重みを大きめに意図して出題したので絶対値をつけ忘れないことも問うつもりでサンプルには行列式の符号が非負のものしか用意しなかったのですが、これが想像を遥かに上回る裏目の出方に繋がりました。絶対値をつけ忘れる提出が非常に多くE問題との間にわずかにAC数反転が・・まるで予想していなかった展開です。なおH問題の「一次変換と面積」は本問と対になる問題です。$3$ 次元から $2$ 次元に落ちるので簡単になるかと思いきや、あちらは符号と合同式の組み合わせを行列式だけでは処理できないように乗法だけでなく加法も組み合わせています。向こうは幾何学的意味を完全に既知のものとしてより複雑な数学的考察部分を問う部分の重みを大きめにしているのでtesterさんのご提案でサンプルに行列式が負のものをいれていたのですが、結果的にはD問題のサンプルにも入れたほうが良かったかもしれませんね・・。

D: No.2444 一次変換と体積 ★★★

問題リンク：https://yukicoder.me/problems/no/2444

tester：Kazunさん

※コンテスト本番での参加者の解き具合を参考にして難易度を★2.5から★3に上方修正しました。

行列式を学んだ後は、低次の場合の計算方法（サラスの公式）や幾何学的な意味を学びます。また、幾何学的な意味を学ぶことで行列式の準同型性も自然と理解できるようになりますし、線型写像の像や核の次元（特に全射性や単射性）と行列式の関係も納得しやすくなります。

本問は行列式の幾何学的な理解を問うため、行列式を用いた体積計算や準同型性や像と核の次元を全て組み合わせた考察を要求させていただきました。準同型性は馴染みが薄いかもしれませんが、大きな計算を小さな計算の積み重ねに帰着させるために使えるということを学べるようにあえて符号と合同式という相性の悪い組み合わせを出題しました。

幾何学的意味を問う部分の重みを大きめに意図して出題したので絶対値をつけ忘れないことも問うつもりでサンプルには行列式の符号が非負のものしか用意しなかったのですが、これが想像を遥かに上回る裏目の出方に繋がりました。絶対値をつけ忘れる提出が非常に多くE問題との間にわずかにAC数反転が・・まるで予想していなかった展開です。

なおH問題の「一次変換と面積」は本問と対になる問題です。$3$ 次元から $2$ 次元に落ちるので簡単になるかと思いきや、あちらは符号と合同式の組み合わせを行列式だけでは処理できないように乗法だけでなく加法も組み合わせています。向こうは幾何学的意味を完全に既知のものとしてより複雑な数学的考察部分を問う部分の重みを大きめにしているのでtesterさんのご提案でサンプルに行列式が負のものをいれていたのですが、結果的にはD問題のサンプルにも入れたほうが良かったかもしれませんね・・。

E: No.2445 奇行列式 ★★★
問題リンク：https://yukicoder.me/problems/no/2445 tester：Shirotsumeさん
行列式の有用性を学んだ後は、行列式の計算アルゴリズムを学びます。通常のカリキュラムで学ぶのは「置換の符号を用いた明示式」と「多重線形性を用いた掃き出し計算」と「余因子展開」の３つで、それぞれ置換は $3$ 次以下に使いやすく（$2$次は$ad-bc$で$3$次はサラスの公式）、多重線形性は$3$ 次以上に使いやすく、余因子展開は簡単な形の時に非常に強力、といった長所があるのでそれらを組み合わせるのが通例かと思います。一方で計算機での計算なら、単に最悪計算量や平均計算量のみを気にするのであれば一番計算量の低い多重線形性を使った計算を検討すると思います。しかし余因子展開は途中式に様々な値を得られるため、途中の値も重要な場合は余因子展開も一考の価値ありですね。本問はその途中式そのものを問うことで、余因子展開の意義を学べるように作問しました。なお解説にも書きました通り、本問はとある過去問のオマージュ問題です。オマージュ元がbitDPを学べる問題だったように、余因子展開の計算もbitDPで処理することができます。

E: No.2445 奇行列式 ★★★

問題リンク：https://yukicoder.me/problems/no/2445

tester：Shirotsumeさん

行列式の有用性を学んだ後は、行列式の計算アルゴリズムを学びます。通常のカリキュラムで学ぶのは「置換の符号を用いた明示式」と「多重線形性を用いた掃き出し計算」と「余因子展開」の３つで、それぞれ置換は $3$ 次以下に使いやすく（$2$次は$ad-bc$で$3$次はサラスの公式）、多重線形性は$3$ 次以上に使いやすく、余因子展開は簡単な形の時に非常に強力、といった長所があるのでそれらを組み合わせるのが通例かと思います。

一方で計算機での計算なら、単に最悪計算量や平均計算量のみを気にするのであれば一番計算量の低い多重線形性を使った計算を検討すると思います。しかし余因子展開は途中式に様々な値を得られるため、途中の値も重要な場合は余因子展開も一考の価値ありですね。本問はその途中式そのものを問うことで、余因子展開の意義を学べるように作問しました。

なお解説にも書きました通り、本問はとある過去問のオマージュ問題です。オマージュ元がbitDPを学べる問題だったように、余因子展開の計算もbitDPで処理することができます。

F: No.2446 完全列 ★★★★
問題リンク：https://yukicoder.me/problems/no/2446 tester：AngrySadEightさん
※コンテスト本番での参加者の解き具合を参考にして難易度を★3.5から★4に上方修正しました。行列と線形写像の基礎を学んだ後は、様々な応用が待っています。最も典型なのが、掃き出し法で連立一次方程式を解くことですね。そのためには簡約化／階数標準形や階数などの理解も問われます。もう少し発展的な内容として、幾何学ではホモロジー理論で行列と線形写像が大活躍しますね。ホモロジーは幾何学的不変量の１つで、抽象的な図形から様々な数値データを取り出すために使うことができます。２つの図形から異なる数値データが取り出された場合、それらの図形は異なるものと考えられるので、幾何学的不変量は図形の比較に使える非常に強力なツールです。例えば図形から得られた線形空間と写像の系列が完全性を満たすか否かという情報は行列を用いて数値的に処理できるため、図形から様々な系列を取り出してその完全性を調べるという手法が良く使われています。嬉しいことに、完全性の判定はひとたび行列の言葉に翻訳してしまえばどんな系列データでも全く同様に処理できますので、そこに幾何学的なケースバイケースの考察は不要です。非常に汎用性な手法というわけですね。本問はそのまさに完全性の判定部分だけを取り出した問題です。完全性の判定は簡約化／階数標準形を用いた階数計算に帰着されます。様々な計算方法が可能であるように優しめの制約にしていますので、お好きな方法で挑戦してみてください。ちなみにこの問題の難易度を最初見誤っており、計算問題としては大学１年生の線形代数の典型問題であることやけんちょんさんによる素晴らしい解説記事があることを理由に★2としてしまっていました。testerさんに★3.5に難易度修正をしていただき、その後のコンテストでも同様の知識を前提とする問題が★3.5で出題されたのを受けてとんでもない過小評価をしてしまったのだと反省しました。

F: No.2446 完全列 ★★★★

問題リンク：https://yukicoder.me/problems/no/2446

tester：AngrySadEightさん

※コンテスト本番での参加者の解き具合を参考にして難易度を★3.5から★4に上方修正しました。

行列と線形写像の基礎を学んだ後は、様々な応用が待っています。最も典型なのが、掃き出し法で連立一次方程式を解くことですね。そのためには簡約化／階数標準形や階数などの理解も問われます。もう少し発展的な内容として、幾何学ではホモロジー理論で行列と線形写像が大活躍しますね。ホモロジーは幾何学的不変量の１つで、抽象的な図形から様々な数値データを取り出すために使うことができます。２つの図形から異なる数値データが取り出された場合、それらの図形は異なるものと考えられるので、幾何学的不変量は図形の比較に使える非常に強力なツールです。

例えば図形から得られた線形空間と写像の系列が完全性を満たすか否かという情報は行列を用いて数値的に処理できるため、図形から様々な系列を取り出してその完全性を調べるという手法が良く使われています。嬉しいことに、完全性の判定はひとたび行列の言葉に翻訳してしまえばどんな系列データでも全く同様に処理できますので、そこに幾何学的なケースバイケースの考察は不要です。非常に汎用性な手法というわけですね。

本問はそのまさに完全性の判定部分だけを取り出した問題です。完全性の判定は簡約化／階数標準形を用いた階数計算に帰着されます。様々な計算方法が可能であるように優しめの制約にしていますので、お好きな方法で挑戦してみてください。

ちなみにこの問題の難易度を最初見誤っており、計算問題としては大学１年生の線形代数の典型問題であることやけんちょんさんによる素晴らしい解説記事があることを理由に★2としてしまっていました。testerさんに★3.5に難易度修正をしていただき、その後のコンテストでも同様の知識を前提とする問題が★3.5で出題されたのを受けてとんでもない過小評価をしてしまったのだと反省しました。

G: No.2447 行列累乗根 ★★★★
問題リンク：https://yukicoder.me/problems/no/2447 tester：hotman78さん
※コンテスト本番での参加者の解き具合を参考にして難易度を★3.5から★4に上方修正しました。行列式や階数を学んだら、対角化を学びます。固有値、固有ベクトル、対角化という新しい概念が行列式を介して連立一次方程式や階数の話と結びつき、ここで１つの区切りとなります。対角化の応用は非常にたくさんありますが、１つは行列の冪乗に明示式を与えることですね。競技プログラミングだと行列の累乗は繰り返し二乗法で直接処理できることが多いので明示式が必要な状況は少ないですが……冪乗以外だとどうでしょう？対角化の恩恵は何も冪乗計算に限られず、より広い関数のクラスまで届きます。つまり大雑把には、対角化を用いることで本来は実数しか代入できなかった関数に、様々な行列が代入できるようになるということです。こういった手法は汎関数計算と呼ばれ解析学でちらほら出くわすのですが、競技プログラミングではなかなかお目にかかれないみたいですね。ぜひここで学んでいただければ幸いです。

G: No.2447 行列累乗根 ★★★★

問題リンク：https://yukicoder.me/problems/no/2447

tester：hotman78さん

※コンテスト本番での参加者の解き具合を参考にして難易度を★3.5から★4に上方修正しました。

行列式や階数を学んだら、対角化を学びます。固有値、固有ベクトル、対角化という新しい概念が行列式を介して連立一次方程式や階数の話と結びつき、ここで１つの区切りとなります。対角化の応用は非常にたくさんありますが、１つは行列の冪乗に明示式を与えることですね。競技プログラミングだと行列の累乗は繰り返し二乗法で直接処理できることが多いので明示式が必要な状況は少ないですが……冪乗以外だとどうでしょう？

対角化の恩恵は何も冪乗計算に限られず、より広い関数のクラスまで届きます。つまり大雑把には、対角化を用いることで本来は実数しか代入できなかった関数に、様々な行列が代入できるようになるということです。こういった手法は汎関数計算と呼ばれ解析学でちらほら出くわすのですが、競技プログラミングではなかなかお目にかかれないみたいですね。ぜひここで学んでいただければ幸いです。

H: No.2448 一次変換と面積 ★★★★
問題リンク：https://yukicoder.me/problems/no/2448 tester：tko919さん
対角化と一緒に学ぶ特性多項式は、それ以降も大活躍します。解と係数の関係から固有値に関する様々な情報を与えたり、最小多項式からジョルダン標準形の話に繋がったり、解析学ではフレドホルム理論という無限次元の作用素の理論まで拡張されたり、代数幾何学では圏論の関手という概念に翻訳されたり。本問はD問題の「一次変換と体積」と同様に行列式の符号と剰余の計算が要求される問題です。今回のように等比数列の輪の形の剰余計算は競技プログラミング界隈でそこそこ頻繁に話題になる典型問題だと思いますが、符号の処理の方はなかなか思いつきにくいかもしれません。固有値、特性多項式、ジョルダン標準形のアイデアを総動員して行列式の符号計算をしましょう。線形代数コンテストの最終問を飾るにふさわしい問題になったと思います。

H: No.2448 一次変換と面積 ★★★★

問題リンク：https://yukicoder.me/problems/no/2448

tester：tko919さん

対角化と一緒に学ぶ特性多項式は、それ以降も大活躍します。解と係数の関係から固有値に関する様々な情報を与えたり、最小多項式からジョルダン標準形の話に繋がったり、解析学ではフレドホルム理論という無限次元の作用素の理論まで拡張されたり、代数幾何学では圏論の関手という概念に翻訳されたり。

本問はD問題の「一次変換と体積」と同様に行列式の符号と剰余の計算が要求される問題です。今回のように等比数列の輪の形の剰余計算は競技プログラミング界隈でそこそこ頻繁に話題になる典型問題だと思いますが、符号の処理の方はなかなか思いつきにくいかもしれません。固有値、特性多項式、ジョルダン標準形のアイデアを総動員して行列式の符号計算をしましょう。線形代数コンテストの最終問を飾るにふさわしい問題になったと思います。

トップページ前の開催記親記事次の開催記