Contest 2050 and Codeforces Round #718 (Div. 1 + Div. 2)

 　Dまで遅解き四完。実装要素の多いコンテストだったから、あまり順位が良くなくてもまあ仕方なかったかな、という気持ち。

コンテストへのリンク

コンテスト後のツイート

C. Fillomino 2

　できるだけ左に、下に～と、端から詰めていけば良かったらしい。

　「どれかの数字では三方に進めないため次に進む一方向が定まる」という状況が続くので、それを利用してDFSみたいにしてしまったけど、もっと単純な解法がないか疑うべきだったか。

D. Explorer Space

　こういう問題はn=mにして欲しい。毎回、縦と横で混乱してしまう……。

E. Group Photo

　条件全てが満たされる場合ってあんまり多くなさそうだよね、という直感に従って場合分けしていく問題。

　Cの位置で場合分けすると、

・右端に何個かC

・左端に何個かCが続いた後、一個置きにCが現れる（最後はP）

・左端に何個かCが続いた後、一個置きにCが現れ、最後もC

・一番左端はP。二個目から何個かCが続いた後、一個置きにCが現れる（最後はP）

・一番左端はP。二個目から何個かCが続いた後、一個置きにCが現れ、最後もC

　という感じになり、これは、累積和と、一個おきの累積和を持ち、尺取り法を使えば求められる。

　ただ、一個おきの累積和を使うため、この上さらに、一個起きのindexが偶数か奇数かで場合分けをしなくてはならず大変だった。

　ちょっと書き方が悪い部分はあったけど、コンテスト中に間に合わなかったのも仕方ないかなぁ。

AtCoder Beginner Contest 199（Sponsored by Panasonic）

 　久々にRatedなABCで非常に緊張した。良い出来とは言えないけど、なんとか黄色に復帰出来てほっとした。

コンテストへのリンク

コンテスト後のツイート

D - RGB Coloring 2

　全部の色を試そうとすると$3^20$必要そうに見える。

　が、連結成分ごとに見て、隣が塗られているようなノードを試していけば、二個ずつしか試さなくていいため、全探索しても計算量が減る。

　……と、そこまではコンテスト中に気付いていたが、上手い実装が思いつかなかった。

　そもそも、全探索を再帰で行う方法がピンと来ていなかったと思う。今まで塗った色の集合を持って、次のノードで何を塗るかを決めれば良い。

　「どういう順番に塗るか」は、DFSの順番で良い。そうすれば、同じ連結成分内で二個目以降に見るノードでは、隣のどこかが既に塗られている。

E - Permutation

　三十分以上悩んだ上、bit DPを思いつかず、怪しい解法（結局、時間計算量的にはそんなに悪くなかったが、Hack caseはあった）を投げてしまった。

　コンテスト中考えたのは、

・何を使うか決めたら、N-1要素の場合に帰着できる

　ということ。

　N要素の場合に対応するM個の条件たちも、N-1要素の場合へ変わる。ので、条件たちを状態と見て、DP（実装はメモ化再帰）をした。

　計算量はよく分かっていなかったが、投げたら通った。

　が、ここで何をまとめているか、というと、たとえば、

・2→4→1と使った場合

・1→2→4と使った場合

　は同じ状態に遷移することが分かる。

　つまり、使う順番は関係なく、集合として同じ要素を消費した場合は同じ状態になる、ということ。

　これはbit DPですね。

　制約からもまずbit全探索やbit DPを疑うべきなのに気付かなかった（bit全探索は考えたけどbit DPは考えなかった）のはひどい。

　でも、After_contestで落ちたとはいえ、ACできて救われた。

F - Graph Smoothing

　これはすんなり解けた。

　「平均を取る」という操作を二回行って平均を取るのは、いかにも、「平均を取る」という操作の平均を取る、というのを二回繰り返したものと同じになりそう。

　それで良いと分かったら、「一回操作して平均を取る」というのは行列で表せるので、行列累乗すればOK。

Codeforces Round #717 (Div. 2)

　ABでペナルティを重ね、Cまで三完。Dは解けなくちゃいけなかったようだが、全く思いつかなかった。

コンテストへのリンク

D. Cut

　解説AC。

　「ダブリング」というキーワードを見ても分からず、解説を読んでようやく理解した。

　ダブリングは「何歩進んだときどこへ到達するか？」を調べるときに使うイメージがあったけど、この問題のように「ある場所へ到達するまで何歩か？」を調べるときにも使えるのね。

　典型らしいので頭に入れておかねば。

　ただ、自分の実装だとlogが二つ付く気がするんだけど、これで合ってるんだろうか。

　また、その前の、全ての要素について互いの素な部分を求めるパートは、事前に約数列挙して、尺取り法によりできる。ダブリングすると分かればこのパートはできると思うけど、そんな簡単には感じないので、こちらで躓かないようにしたい。

　類題だというこの問題もACしました。

　同じ解法で解ける問題なのに、添え字などの実装でミスしてしまい良くない……。なお、解説を見ると、logは一つと書いてありますね。うーん、どうやってlog一つ落とすのだろう。

　

AtCoder Beginner Contest 198

　Eまで五完。Dで大量のペナルティを出したため、順位は悪かった。

コンテストへのリンク

コンテスト後のツイート

D - Send More Money

　まあ、全探索するしかなさそう。Pythonならitertools.permutationsを使うと良い。

　ただ、自分の場合2ケースほどTLEして困った。結局入力を文字列ではなく、listに変換したら通ったのだが、これで高速化になるというのはちょっと難しいと思う。気付けなくて仕方なかったかな……。

　PyPyでTLEにならずすぐ通していた人は、上手く枝狩りを入れていたのかな……。

　

F - Cube

　すぬけさんの解説放送と、バーンサイドの補題のWikipediaを参考にしてAC。「ポリアの数え上げ定理」を知らなかったので勉強になったし、それが分かっても難しいですね。

　立方体にどういう回転があるか自力で求めるのはかなり厳しいので、このWikipediaの図を使ったり、手元にサイコロを用意したりするのが良さそう。

　その後の数え上げも難しいけど、これはすらすらできるようになりたい。

Codeforces Round #713 (Div. 3)

 　AGCと時間が重なっていたため、遅れて参加。Gが解けずに終了。

コンテストへのリンク

コンテスト後のツイート

G. Short Task

　エラトステネスの篩風に、$10^7$以下の全ての数について、約数の和を前計算する。

　エラトステネスの篩を使って約数列挙などする問題は最近しばしば見ているのに、これを思いつかなかったのは良くなかった。

　とはいえ、ちょっと制約厳しくないですか？

　Kotlinで通したのですが、システムテストで落ちていました。うーん。

TopCoder Single Round Match 798

 　EasyをHackされて0完。

コンテスト後のツイート

Div1 Easy MarriageAndCirclingChallenge

　ツイートの通りです。

　C++を使うときはOverflowを気にするのは当然だと思っているし、コンテスト中も気にしていたのに、こんなミスをするのは酷い。

　一応、システムテストを通ったコードを貼り付けます。

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

class MarriageAndCirclingChallenge
{
public:
  long long solve(int N, int threshold, int state)
  {
    vector<vector<int>> E(N);
    long long sc=state;
    int ch=0;

    for (int i = 0; i < N; i += 1){
        for (int j = i+1; j < N; j += 1){
            sc=(sc * 1103515245 + 12345) % (1<<31);
            ch=sc%100;
            //printf("%d ",ch);

            if (ch < threshold){
                E[i].push_back(j);
            }
            else{
                E[j].push_back(i);
            }
        }
    }
    long long ANS=0;
    vector<vector<int>> X(N, vector<int>(N));

    for (int i = 0; i < N; i += 1){
        for (int j = 0; j < N; j += 1){
                X[i][j]=0;
        }
    }

    for (int i = 0; i < N; i += 1){
        for (auto j:E[i]){
            for (auto k:E[j]){
                X[i][k]+=1;
            }
        }
    }

    for (int i = 0; i < N; i += 1){
        for (int j = 0; j < N; j += 1){
            ANS+=X[i][j]*X[j][i];
        }
    }
    return ANS/4;
  }
};