Ecasdqina's MEMO

-!=x=!-

ゆふふ．

ICPC 2020 Asia Yokohama Regional 参加記

参加記

3/16（前日）

ICPC のプラクティスとかがあるのを忘れていて、『シン・エヴァンゲリオン劇場版:||』の予約を入れたら被ったので、時間を早めて早朝に見に行き、即帰宅からのプラクティス参加を決行した。

3/17（当日）

9 時開始とかいう人間に優しくないスケジュールで、寝不足だったので、開始から 2 時間程度は目がしばしばして問題文も全然読めなかったし、やる気も全然出ていなかったが、時間が経ってきたらなんとなくやる気が出てきて、まともに問題が解けるようになり始めてよかった。以下は時系列的なやつ。

  • 開始
  • B を読む
  • 眠いので嘘貪欲を二種類書き 2WA を得る、頭が回っていないことを自覚しチームメイトに押し付ける
  • D を読めと言われて読んだが、明らかにヤバそうなので飛ばす
  • J の概要をチームメイトから聞いて通す
  • G の概要をチームメイトから聞いて、成立条件を考えるが、よくわからないな～と思っている間にチームメイトが思いついたので、実装だけして通す
  • eat_ice の成績を見て beet さん大噴火からのサブマリンかなぁと思う
  • K を塚本が通しているのを見て文字列ゲーか～と思う
  • I の概要をチームメイトから聞いて、自明だったので通す
  • H の概要をチームメイトから聞いて考えるが、嘘を書いて時間を消滅させる
  • 終了

結果は 5 完 25 位で、まあそこそこなんじゃないでしょうか。来年も多分参加するので、次回は 20 未満を取ります。

余談

ICPC から送られてきた「真っ向勝負」と書かれたマシュマロを Twitter に投稿してみたら、beet さんが即 RT してきて面白かった。

yukicoder No.1325 Subsequence Score 解説

yukicoder tutorial

公式解説では各添字の値についての寄与について、それより左側のものが選ばれるたびに加算するという言い換えを用いていた。それに対して、ぼくはその添字が k 番目に選ばれる場合について考え、 k についての総和を取ることで解いたので、それについて書く。

解説

いま、添字 i(0 \le i < n) について考えているとする（かんたんのため 0-indexed とする）。この寄与は以下の式で表される。

\begin{equation} \displaystyle a_i2^{n - i - 1}\sum_{k = 0}^i (k + 1)\binom{i}{k} \end{equation}

総和の中身をかんたんな式に変形したい、以下のように多項式を変形することで総和の単純な式を導出できる。

\begin{align} x(1 + x)^i &= \sum_{k = 0}^i \binom{i}{k}x^{k + 1} \\ \dfrac{dx(1 + x)^i}{dx} &= \sum_{k = 0}^i (k + 1)\binom{i}{k}x^k = (1 + x)^i + ix(1 + x)^{i - 1} \\ \sum_{k = 0}^i (k + 1)\binom{i}{k} &= 2^i + i2^{i - 1} = (2 + i)2^{i - 1} \end{align}

よって以下の値が答え。

\begin{equation} \displaystyle \sum_{i = 0}^{n - 1} a_i2^{n - 2}(2 + i) \end{equation}

エイシング プログラミング コンテスト 2020 F - Two Snuke O(1) 解法

tutorial 多項式

O(1) 解法

問題を見た瞬間多項式だと直感したので多項式で問題を表します。

{\displaystyle \begin{eqnarray} \begin{array}{l} f &= {\displaystyle \sum_{u = 0}^{\infty}\sum_{k = 1}^{\infty} kx^{2u + k}} \\ &= {\displaystyle \sum_{u = 0}^{\infty} \left(x^{2u} \sum_{k = 1}^{\infty} kx^k\right)} \\ &= {\displaystyle \sum_{u = 0}^{\infty} \left(x^{2u} \times x\dfrac{d}{dx}\left(\dfrac{1}{1 - x}\right)\right)} \\ &= {\displaystyle \sum_{u = 0}^{\infty} \left(x^{2u} \times \dfrac{x}{(1 - x)^2}\right)} \\ &= {\displaystyle \dfrac{x}{(1 - x)^2} \sum_{u = 0}^{\infty} x^{2u}} \\ &= {\displaystyle \dfrac{x}{(1 - x)^2} \dfrac{1}{1 - x^2}} \\ &= {\displaystyle \dfrac{x}{(1 - x)^3(1+x)}} \end{array} \end{eqnarray} }

上記のように f を定義すると、答えは次のように表せる。

{\displaystyle \begin{equation} [x^N]\dfrac{f^5}{1 - x} = [x^{N - 5}]\dfrac{1}{(1-x)^{16}(1+x)^5} \end{equation} }

さらに、Wolfram Alpha へこの式を突っ込んで部分分数分解すると下のように表せる（1/((1-x)^16(1+x)^5) 部分分数分解 - Wolfram|Alpha）。

\dfrac{1}{(1-x)^{16}(1+x)^5} = 1/(32 (-1 + x)^{16}) - 5/(64 (-1 + x)^{15}) + 15/(128 (-1 + x)^{14}) - 35/(256 (-1 + x)^{13}) + 35/(256 (-1 + x)^{12}) - 63/(512 (-1 + x)^{11}) + 105/(1024 (-1 + x)^{10}) - 165/(2048 (-1 + x)^9) + 495/(8192 (-1 + x)^8) - 715/(16384 (-1 + x)^7) + 1001/(32768 (-1 + x)^6) - 1365/(65536 (-1 + x)^5) + 455/(32768 (-1 + x)^4) - 595/(65536 (-1 + x)^3) + 765/(131072 (-1 + x)^2) - 969/(262144 (-1 + x)) + 1/(65536 (1 + x)^5) + 1/(8192 (1 + x)^4) + 17/(32768 (1 + x)^3) + 51/(32768 (1 + x)^2) + 969/(262144 (1 + x))

負の二項定理を用いると、各項の m 項目を次のように計算することができる。

{\displaystyle \begin{eqnarray} \begin{array}{l} [x^m]\dfrac{1}{(1 + x)^a} &= {\displaystyle (-1)^m\binom{m + a - 1}{a - 1}} \\ [x^m]\dfrac{1}{(1 - x)^a} &= {\displaystyle \binom{m + a - 1}{a - 1}} \end{array} \end{eqnarray} }

よって、部分分数分解した結果の項ごとに N - 5 項目を計算して総和を取ることでこの問題を解くことができる。項数および次数は定数なので、二項係数は定数時間で計算することができる、よって全体でも定数時間で答えることができる。

KOSEN セキュリティ・コンテスト 2020 参加記

参加記 ctf

今年も参加しました。

三位（3510）

rotten3

後輩が解いていたので口出しした（英 alphabet は 26 文字だよ）。

ECCp-20

楕円曲線上の演習問題です。 楕円曲線と点 P, Q が与えられるので 2P と dP = Q となる d を求めればフラグが得られます。 前者は単純に計算し、後者は離散対数問題を解きます（Baby-step Giant-step Algorithm で高速に解ける）。

Find2

bmp ファイルが 10000 個与えられるのでそこからフラグを探すという問題。適当にいくつか覗いてみるとノイズみたいな画像だらけなので、色数が少ないようなファイルを探すとフラグが得らます。

from PIL import Image
import glob


def count_color(file: str) -> int:
    img = Image.open(file)

    st = set()
    (w, h) = img.size
    for i in range(w):
        for j in range(h):
            color = img.getpixel((i, j))
            st.add(color)
    return len(st)


if __name__ == '__main__':
    files = glob.glob("./Find2/*")

    mi = 2 ** 30
    for file in files:
        ret = count_color(file)

        if ret < mi:
            print("{}: {}".format(file, ret))
            mi = ret

足し算しよう

1000~10000 の総和を求める問題。総和を求めます。

熱血計算塾

nc で繋いで eval で計算するやつです。

15game

1 から交互に数を順番に言っていき 15 を言ったほうが負けのゲーム（の一般化）を nc でやる問題。禁止数 b と一度に言える個数 c について常に x % (c + 1) = (b - 1) % (c + 1) となるような x を言ってから相手に渡せば勝てます。

ICPC2020 国内予選 参加記

参加記 icpc

寝れないからあんまり書くつもりのなかった参加記を書きます。

appeared

明石工業高等専門学校
ぼく（ecasdqina）、asdf1, shinchan のチーム

前日

当日に輪講があるので深夜 3 時くらいまで準備してた。

当日

15:50 くらいまで輪講をしてて、16:00 に会場入りした。そこから準備をして 16:30 に競技開始、とはならず主催側のインシデントが起きて 16:40 くらいに開始した。
ABC をチームメイトに任せて、ぼくは D をまず見ることにした。
一見すると構文解析なのでチームメイトに渡そうかと思ったが、構文解析以外が本題らしいということが分かったので考える。制約から bitDP 等が関係してくるだろうという予想を立て、bitDP をしながら構文解析を進めるというものを考えていたが、これは明らかにヤバい。二式の答えが一致するということに着目すると、結果を決め打ちするという方針を思いつく。この方針で考えてみると、結果との大小関係を決めれば式を評価することが出来ることに気づく。さて、解法が出来たので実装をしていくのだが、実はぼくは構文解析を書いたことがなかったため全く書けない。最終的にチームメイトに構文解析だけ書かせることで対応した。
1:37:59 に AC。この時点で 4 完して通過を確信していたので舐めプを始める。
E は半分にするところまでしか思いつかなかった。F はチームメイト曰く decremental connectivity が出来れば解けるらしいということだけ聞いたのでデを書いてたけど、木じゃないとか online らしいと聞いてヤババ！となって崩壊。実際は木になるし offline であるということが問題文を読んだら分かった。頑張って実装すれば通せそうということも分かったが、この時点で残り 30 分だったし、順位もそこそこ良かったため、雑談フェーズに移ることにした。

f:id:ecasd-qina:20201108051459p:plain
結果

総論

  • 手元実行という特性をうまく活かすべきだった（C, F など）。
  • ICPC の精進全くしていない上にチーム練を一度しかしていなかったのでこれは結構上振れかもしれない。
  • 横浜たのしみ～2020