AtCoder Regular Contest 111

　ABの二完で終了。

　復活してからのARCでは失敗が少なかったのに。悲しい。

コンテストへのリンク

コンテスト後のツイート

A - Simple Math 2

　かなり長いこと分からなかったのですが、

$10^N=p*M+r$

　とおき、さらに、

$p=q*M+ANS$

　とおいて、下式を上式に代入すると考えると、$M^2$での余りを考えれば良いと気付けました。

B - Reversible Cards

　既出らしいですが、気付けませんでした。

　当時は解けていなかったので、今回は解けて良かった。

C - Too Heavy

　ツイートか何かで「重い荷物の順番に交換すれば良い」というほぼ答え同然の情報を得ていても、30分程度実装にかかってしまった。

　どういう問題なのか、情報を整理するのか難しいと思う。

　頭の整理のため、

・B：荷物の番号→荷物の重さ

・P：人物の番号→持っている荷物の番号

（及び、・Pの逆関数：荷物の番号→人物の番号）

　と、それぞれがどういう関数かメモしたら多少分かりやすくなったが、それでも苦戦した。

D - Orientation

　iとjを結ぶ辺で、C[i]とC[j]が異なるなら、Cが大きい方から小さい方へ結べばよい。

　問題は、同じときにどうするか、だが、公式解説にある通り、よく考えるとDFSするだけで良い！　となる。

　確かに、よくDFSの性質を考えてみればそうなりそうで、証明はDFS木などを使えばできる。

　ただ、それが自然と感じられるためには、DFS木、lowlink、橋といったあたりに親しんでいることが必要そう。勉強不足でした。

　今調べた中では、hosさんのpdfが一番分かりやすかった。AOJにも入っている内容なので、ちゃんとやっておかねば。

E - Simple Math 3

　snukeさんの解説動画を見てAC。

　floor sumを使うと分かっても戸惑ってしまった。けど、その知識があるなら解けなきゃダメですね。図を描いて、順を追って考えればfloor sumが出てくるという問題なので。

F - Do you like query problems?

　snukeさんの解説動画を二回見てAC。

　一回解説動画を見た時点だとよく分からなかったのだけれど、もう一回見たら意外と単純だと分かりコードにできました。

　解説動画を理解する上でのポイントは、

・N=1のとき、「k回目のクエリでsumを取るときに加算される値」が$C^k*$（係数）の和

みたいに表せるので、kを1～Qで動かした和が等比数列の和の公式で求められ、大体O（１）なこと。（繰り返し二乗法を使うので本当はO（１）ではありませんが）

・N=1の場合で求めたA, X, Bが、Nが一般の場合でも求められること

　といった辺りだと思います。

　何を教訓とすべきかは難しいです。特に、一回解説動画を見た後もできなかったのは、何かが思いつかなかったのではなく、複雑な状況を理解し式に落とす力がなかった、という感じなので。

　こういう、複雑な状況を整理する力はどうすれば身に着くんでしょう。マラソンをやると効果があったりしないかな……。

TopCoder Single Round Match 797

0完ですがHack１成功でレートは若干プラス。

Div1 Easy FlightPlan

　使える高さを固定すれば、スタートからゴールまで最低何歩で行けるかはBFSで書けるので、高さを全探索すれば良い。ただ、$O(N^4)$をPythonで通すのは無理。頑張ってC++を書いたものの、システムテストで落ちてしまった。

　注意すべきは二点。

・（BFSの書き方にもよるけど）スタート地点が全探索時の高さより高いときバグる可能性がある。

・オーバーフロー。全探索する高さをintにしていたら、高さ*cupなどの計算でオーバーフローしていた。

　この二つに引っ掛かってたのでダメ。特に一点目は、Pythonで書いててもミスってた可能性がありますね……。

　以下、システムテストを通ったコード。

#include <bits/stdc++.h>
#include <bits/stdc++.h>
using namespace std;

class FlightPlan
{
public:
  long long fly(int R, int C, vector<int> H, int cup, int cdn, int clr)
  {
    set<long long> S;
    S.clear();
    vector<long long> DP(R * C);

    for (int i = 0; i < R * C; i += 1)
    {
      DP[i] = 9999;
      S.insert(H[i]);
    }
    DP[0] = 0;

    long long ANS = 1000000000000000000;

    for (auto s : S)
    {
      if (s < H[0])
      {
        continue;
      }
      if (s < H[R * C - 1])
      {
        continue;
      }
      deque<int> Q;
      Q.push_back(0);

      for (int i = 0; i < R * C; i += 1)
      {
        DP[i] = 9999;
      }
      DP[0] = 0;

      while (Q.size())
      {
        int x = Q.front();
        Q.pop_front();
        int r = x / C;
        int c = x % C;

        if (r + 1 < R && H[(r + 1) * C + c] <= s && DP[(r + 1) * C + c] > DP[r * C + c] + 1)
        {
          DP[(r + 1) * C + c] = DP[r * C + c] + 1;
          Q.push_back((r + 1) * C + c);
        }

        if (r - 1 >= 0 && H[(r - 1) * C + c] <= s && DP[(r - 1) * C + c] > DP[r * C + c] + 1)
        {
          DP[(r - 1) * C + c] = DP[r * C + c] + 1;
          Q.push_back((r - 1) * C + c);
        }

        if (c + 1 < C && H[r * C + c + 1] <= s && DP[r * C + c + 1] > DP[r * C + c] + 1)
        {
          DP[r * C + c + 1] = DP[r * C + c] + 1;
          Q.push_back(r * C + c + 1);
        }

        if (c - 1 >= 0 && H[r * C + c - 1] <= s && DP[r * C + c - 1] > DP[r * C + c] + 1)
        {
          DP[r * C + c - 1] = DP[r * C + c] + 1;
          Q.push_back(r * C + c - 1);
        }

        if (DP[(R - 1) * C + C - 1] < 9999)
        {
          long long ANSX = 0;
          ANSX += (s - H[0]) * cup;
          ANSX += (s - H[(R - 1) * C + C - 1]) * cdn;
          ANSX += DP[(R - 1) * C + C - 1] * clr;

          if (ANS > ANSX)
          {
            ANS = ANSX;
          }
        }
      }
    }
    return ANS;
  }
};

パ研合宿2020 第1日「SpeedRun」

　Dと最後三問が解けずの11完でした。

コンテストへのリンク

コンテスト後のツイート

D - 立方体を壊せ！

　立体図形は苦手なので飛ばしたが、落ち着いてやれば解けることは解ける。

　まず、$x+y+z=K$という平面は、(K,0,0),(0,K,0),(0,0,K)を通ることをイメージする。立方体の頂点から各辺（座標）の方向に、切片が1ずつ動いていくイメージ。

　それができれば、$K<N$のときが三角錐で、$K>2*N$のときが、立方体から三角錐を除いたものだということが分かる。

　問題は、$N<K<2*N$のときだけど……。

　ちゃんと図を描けば、$K<N$のときと同じように作った三角錐から、角の三角錐三つを切り取ったものだと分かった。

　あまり立体が得意でない私でも分かったのだから、他の人でも分かるはず！　と言うのは容易いけど、私より立体が苦手な人だっているはずで、そういう人にどう説明すれば良いんだろう。

　図を描くこと自体にそこそこ立体図形の能力が必要な気がするしねぇ。

　私自身、もう少し捻られたら自力で解くのが難しくなる気がする。（いや、色々断面描いて頑張るけど……）

　数学を勉強しても、あまりこういう立体をイメージする能力は伸びない気がする。厳しいね。

H - その計算、合ってますか？

　コンテスト中にWAを量産してしまった。

　各ビットごとに考えると、orが1のところでしかandやxorは1にならないことが分かる。

　あとは、「andが1のところは一斉に1を取る」ことに気付くのが重要。偶数回出現すればxorは0、奇数回ならxorは1になる。

　各ビットごとに考えていると解けない問題。

　とはいえ、各ビットごとに考えるのは基本なので、そう考えてハマってしまうのはある程度仕方ないか。

J - Output-only

「5, 12, 13」で検索したらこのページがでてきた。なるほど。

　見たときは何これ、と思ったけど、よく見れば自力でも思いつけそうな式か。

M - 貢ぎ物

　結構考えたけど分からず、解説を見てAC。

　「高速ゼータ変換」というキーワードを見たがどういうものか忘れていた。この問題のすぬけさんの解説を見たのは結構最近なのに……。名前と内容が結びつきにくいので、覚えにくいのかも。

　しかし、そのキーワードを見ても解けず。

　各$A_i$が$2^{20}$以下なので、$2^{20}$要素のDP配列を持つことは思いついた。だが、その配列を「その数を作れるか、否か」の01だけを持つものとしても上手くいかない。

　それを、DP[i]で「iに含まれる数j達で作ることができる最大の数」（つまり、DP[j]たちをorしたもの）とすると上手くいく。

　$2^{20}$要素の配列を持つというところはあってそうだけど、01だけを持つのは無駄なので、他に何か持てないかな……？　と考えたら思いつけたのかな。

N - 背の順

　コンテスト後に問題を見て、自力でできるかと思ったら苦労してしまった。

　二つ以上の区間を消す必要はない。なぜなら、$[l_0, r_0], [l_1, r_1]$を消すなら、$[l_0, r_1]$を消した方が得だから。

　$[L, R]$を消す場合を考える。

　$L$の候補は、左端$A[0]$か、左から順に調べて$A[i-1]>A[i]$が成り立つ$A[i]$のどちらかになる。そのような$i$に対して、$j>i$なる$j$を消すと消した後がソート済にならないし、$A[1]～A[i-1]$を消すなら$A[0]$や$A[i]$を消した方が得なので。

　その後、$R$も同じように、候補が二個程度に絞れる……と思ってWAを出してしまった。

　左右対称な気がしてしまったが、実際はそうではない。

　$L=0$のときは簡単。

　$A[i], A[i+1], \dots $がソートされているような最小の$A[i]$が最適なRになる。

　もう片方の場合も、

　$R$は「$A[i], A[i+1], \dots $がソートされている」ような範囲の中にある。求める$R$は、この範囲で、

・$A[L-1]<A[R+1]$

　が成り立つような最小の$R$である。

　たとえば、

・$A=4, 1, 2, 3, 5$

　の場合を考えると、$L$の候補は$A[0]$と$A[1]$だが、$L=A[0]$に対応する$R$として最適なのは$A[1]$, $L=A[1]$に対応する$R$として最適なのは$A[3]$となる。

　公式解説がDPだったのは驚き。全く考えなかった……。

O - Xor Sum Sum

　解説AC。

　最上位bitから考える……といった方法も頭をよぎるけど、A,Bの数字が小さいので、なんらかの方法で全探索するのかな、とは考えた。

　が、基底を考える方針は全く浮かばなかった。言われてみればなるほど、という感じでした。

　xorの掃き出し法は、この問題やこの問題を解いたことがあったのにね。

　なお、xorの掃き出し法は、noshi91さんの方法が簡単。これで良いと納得するのには苦労したけど、一旦分かれば忘れない方法ですね。

Codeforces Round #694 (Div. 1)

　pretestはCまでの四完だったが、システムテストでCが落ちてしまった。

コンテストへのリンク

コンテスト後のツイート

C. Strange Shuffle

　詐欺師（impostor）の周囲の値が変わっていくことに着目。右側はkより大きく、左側はkより小さくなる。「kでない箇所」は、左右一個ずつ伝搬していくので、kでない場所を探してから二分探索すれば良い。

　-1～+１、-2～+2、と伝搬範囲は広がるので、その範囲ずつ（つまり、大体2*ターン数）移動させていけば良い。

　ただし、詐欺師自身の値は変わらないこと、及び、最終的に変化しない状態になったとき、kの箇所は、詐欺師のものともう一つある可能性があることに注意しなくてはいけない。

　自分のシステムテストで落ちた実装は、n=4, k=2で、「2 3 2 1」となった最終状態でkでない箇所を探して、1と3を聞き続けるものになってしまっていた。2*ターン数ずつ移動させていたので、その二つしか聞けない！

　なので、移動する数を「1*ターン数」や「2*ターン数-1」に直したらACできました。

　なお、厳密にはこれでもHack caseがあるかもしれない。後半の二分探索パートでは、kなものを見つけたらただちにそれを答えとして出力するようにしているけど、「もう一つのk」がたまたま当たってしまうことはありそう。（本当にHack caseがあるかは分かってないです）

　多分、二分探索パートでkの箇所が見つかったとき、左右の数字も調べるようにすれば、そのケースも除外できるはず。

Codeforces Round #693 (Div. 3)

  pretestは全完でした。→システムテストも通っていました！

コンテストへのリンク

コンテスト後のツイート

　ツイートだと読みにくいと思うので、Gだけ補足。

G. Moving to the Capital

Step1　都市1から各都市が何歩でいけるか（問題文中のdを）調べる。ここではDと書く。

Step2　それぞれの都市iから逆向きに一歩進んだ都市をjとして、ANS[i]=min(D[i],D[j])とする。高々一回だけ問題文中の2の移動をして良い、というルールを使った感じです。

Step3　各都市からDが大きい方へたどってみてANSの最小値が答え。問題文の1の移動でDが大きい方へは進めるので、これで答えが求まります。

　としました。

　Step3は再帰で書くのが簡単だと思う……けれど、CodeforcesのPyPyではこの深さの再帰は無理（エラーが出る）。（なお、AtCoderならエラーなしでいけるはずですが、PyPyの再帰は遅いので、間に合うかは分かりません）

　なので、どうしようか考えたけど、Dが大きい都市から見ていけば再帰なしでいけた。

東京海上日動 プログラミングコンテスト2020のD - Knapsack Queries on a tree

 東京海上日動 プログラミングコンテスト2020のD - Knapsack Queries on a tree

　を通したのでメモ。

　PyPyでは公式解説の方法ではTLEを取ることが不可能なようだ。（他の人の提出を見たけど、通せている人はいなそうだった）

　半分全列挙をlogを使わずにやるテクニックを用いると、PyPyでも通るらしい。（多分全ての）PyPyの提出はこの方法で通している。

　……が、私が真似して書いてもなぜか通せなかった。

　ので、Kotlinで通そうと試みた。

　Kotlinだと、IntArrayなどを使って、最初から要素数を指定した配列で計算するのは速いが、mutableListOfとかで要素数を加えていこうとすると遅いようだ（良い方法があるのだろうか？）。

　なので、PyPyで速かった方法をそのままやろうとするとかえって遅くなる。

　そのため、公式解説の方法で、要素数を指定した配列のみを使ってやると通った。

　その言語での高速な書き方を理解していないと通せない問題は厳しい……。

AtCoder Beginner Contest 187

 　年も変わったし、コンテストへの参加記録を書いていきます！

　……といっても、コンテスト後、既に一日経っている。いつまで続けられるんでしょうか。

コンテストへのリンク

コンテスト後のツイート

D - Choose Me

　何もしないと全員が青木氏に投票する。

　高橋氏が演説を行うと票がどれだけ動くか、と考えると、2*A+Bでソートすれば良いと分かる。

E - Through Path

　最初、全方位木DPが必要だと思い一旦飛ばした。

　Fを解いた後、やりたくないし書き終える自信がないけど、全方位木DPを書くかー、と書き始めたら、通常の木DPでいけることに気付いた。

　自然に書けば全方位木DP、「全体にxを足して、逆側からxずつ引く」ことを思いつけば普通の木DPでいける。

　とはいえ、全方位木DPでも書けるべき問題ですよね。

F - Close Group

　Nが小さいのでbit系を色々考えたが、しばらく思いつかず苦労した。

　「まず、完全グラフになっているものを列挙」を思いつけば、$4^N$のDPにはたどりつける。

　それが実は$3^N$になるというのは、この問題のsnukeさんの解説動画で覚えていた。難しい問題を解説ACしておいたのが役に立った！　と嬉しかったのですが、Educational DP Contestのこの問題もそうだったのですね。解いたはずなのに全く覚えていなかった……。