2024-12-22

ICPC 2024 Asia Yokohama Regional 「Distance Sums 2」 niuez視点

AHCにのめり込んでいる間にAtCoderアカウントのAlgo部分が非アクティブなってしまいました。

チームメイトと自分視点の気持ち

niuez
- 趣味グラミングがLinux、訳ありでWindows、外出先ではMacBookと、コーディング環境のブレへの耐性がある
- using namespace std縛りをしても他の二人よりコーディングが早い/速い
- この人をどうやってうまく使うかがポイント
shama
- 単発のひらめきを必要とする問題が得意
- ある一言をしっかり解法に昇華させたい気持ち
nishinoyama
- 理詰めが得意
- 何が非自明かを話してくれるので、niuezの知識量でカバーできるかが勝負

コンテスト前に考えていたスタートダッシュ

nishinoyamaがパソコンをセットアップ
niuezがAを読んで書き始める
AをACしたタイミングで、Bをまとめたshamaがniuezに解法説明
niuezがBを実装

コンテスト中

適当に自分視点を時系列にしておきます。(-> hoge)はhogeさんに言ったことです。

A問題を見ます。英語が読めませんでした。
( -> shama ) 「すみません、A問題が読めません」(信頼性ポイント -2000000000000000)
- shama 「B問題が読めました、上からbitを決めると良さそう」
- ( -> shama ) 「A問題を読んで欲しいです」(?????)
B問題をAC
shama「A問題の解法がわかりました」(ありがとう...)
- 「はい、それはできますね」
A問題をAC
I問題が解かれているので見る。4secだしMo's Algorithmでできるなあと言って書いたがTLE
- 枝刈りで手元で4secくらいだったので祈って投げたがTLE
- あまりよくないムーブをしてしまった
Eが解けたという報告が来る。「はい実装するだけですね」AC
nishinoyama「Kはzeta変換ぽいけど、どうしたらいいかわからない」
- ( -> nishinoyama )「あ〜それはこのライブラリでこうするといいです任せてください」AC
shama「saehassがCを解いている、すごい」問題を確認しに行く
- shama「MSTっぽいMSTじゃないです」
- 「このコストって根までの距離 * 頂点の重みですよね？」(ここで解法に気づくべき)
- 「辺のコストが1だったら解けますか？」
- 「頂点のコストが1だったら、、、あ〜解けました最短路木でいいのか、ギャグだなあ」AC
Iが通ってないのがもやる。考え中...
shama「Gはこうすれば解けると思う、大変だけど書いてみます」
Iの新しい解法を思いつく、席を奪う
- 前の解法とランダムケースの結果が合ったので投げる AC
- ちなみにこの時点でMoとSegment Treeとosa kをIのためだけに写経している
あとACが多いのがDだったのでDを考える
- nishinoyama「お互いで対応している部分木の境界面が大事な気がするんですよね」
- 「僕もそう思う、、、番号の若い方から構築する気持ちになると、1を含む部分木と2を含む部分木がそれぞれ同じ方法で結ばれて欲しい気がする」
- 「任せてください」 AC
F絶対ヒューリスティックできるはずなんだけど、んあ〜(残り15分)
- 一応書いたが間に合わなかった

まとめ

全体18位、同じ大学の強いチームであるi do understandと同じ完数だったので、かなり調子が良かった気がする。こうしてみると自分がずっと実装していたわけだが、I以外はノーペナで通すことができてチームのやりとりや動き方がかなり良かった気がする。この一年で理詰めする考察力や普通でないパソコン力がAHCで得られたので、「俺に任せろ」できたのも良かったかもしれない。

5年間、コロナと被ったりしてオンサイトがなかったこともありましたが、いろんな人といろんなチームプレイや助け合いができてよかったです(otagai_tasukeai、だよな？)。ぼくとICPCで関わってくれたみなさん、ありがとうございました。またご飯誘ってください。

celeste

celesteで自分を認識している人がいてびっくりしました。celesteをプレイしていただき、ありがとうございます。

celesteをまだプレイしていない方、今575円です。買いましょう。

celesteを最近プレイしていない方、よろしくお願いします。

2024-12-07

今年遊んだおすすめのゲーム1選

Celeste

御託はいい購入しろ

2023-12-08

今年遊んだおすすめのゲーム1選

Celeste

2022-12-29

otagai_tasukeaiが助け合わなかったこと(ICPC 2022 Asia Yokohama Regional参加記)

コーチと選手2人は電車、1人逆張りバスで来た結果遅刻しかけた
リハーサルの時までライブラリの使い方を知らない
1人だけvim使った上に、set expandtabの設定を忘れていてタブ文字がすごい
英字配列の練習をしていたかったので唯一使える人がライブラリ全部写す係に
チーム紹介担当を2人が嫌がったので1人が助け出そうとしたら「そういう真面目なのはやめとこう」となって(tasukeaiとは)、虚言癖のある人に一任した
1日目のホテル着後、1人はベッドに溶け、1人はいつの間にかイルミネーションを一人で見にいった結果、夜ご飯は別々に(メロンパン、炒飯、食べ放題、全員一人で食べた)
朝ご飯前に部屋前で起床チェックが入る予定だったのに、先に食べ始めていた
「追加のライブラリ印刷代は俺が奢るから」→ もらっていません
「チームの2人の仲が悪くなっても、もう1人と不可侵条約を結んでるから大丈夫」という虚言
3人がそれぞれD, E, Gを担当することになって、全員プログラムをバグり散らかしてパソコンの所有権をぐるぐる、デバッグはお互いが関与せずにAC
JOI17/18の話は、やめよう(歳をとった　たすけてくれ)
(追記)
チーム紹介スライド僕が出した渾身の一作がrejectされた
コンテスト本番に嘘の問題概要を伝えて「サンプルと違くないか？」「すまん虚言だった」をやりました
追記2
考察を聞いたものの理解できず、自分には分からない解法だと思ってなあなあにしていたが誤読が後から判明
ライブラリの印刷をしておくと言いながら直前までせず、前々日の昼にPDFを要求されるも17:00まで寝ていたため印刷が前日に
2人が当日失敗したらチーム解散どころか絶縁の危機だった(結局2人とも失敗したので回避)
otagai_nonoshiriaiというエイリアスが誕生した

「お互い助け合い」だよな？

2020-11-09

ICPC2020 国内予選参加記

niu_mogu_moguでugisとplayrollerで組んで参加しました. うにもぐもぐ.

コンテスト前

library-checker-porblemsをクローンしてきた. 16:30まで授業だったので, 授業を途中でブッチしました. 教員から「結果残してね♡」と言われる.

コンテスト

なんかアクセスできなくて焦る, 電話するけど繋がらなかったのでそういうことかと安心する. ぬるっとスタート.

ugisにA, playrollerにBを任せて, 僕はC, D, E, Fあたりを一通り見る.

Cは解けそうなのでヒントだけ二人に託した, Dが構文解析がメインではないこと, EがbitDPできそう, Fはできるけどバグらせそうと思ったあたりで, ABが通っている. 焦るなあ

Eは絶対bitDPだと思っていたけどどうするか悩む. 4*4に分割するのかともおもった. 連結成分が4つに分かれるしグラフが15*30に圧縮できそう → 書く.

書いてバグらせている間にCが通されている. 実行に1分くらいかかったらしいけど通ったのでよし！

Eのバグは圧縮したグラフを勘違いしていたことだった. これをちゃんと書き直してAC. playrollerにお茶を奢ってもらう.

Fは絶対に通せると思っていたのでDを託す. おもむろにOnlineDynamicConnectivityを貼る. 実装は20分くらいで終わったしData No.1は通ったけど, Data No.2が通らない. なんやこれ...

Dわからんとちょくちょく連絡が来る, 僕もわからない. まあF通せればいいやと思っていた.

Fのバグに気がついたのが終了30分前. けどこのバグで治らなくて非常に焦る, なぜNo.1が通ったのか全くわからない.

う〜と唸って残り2分. 辺を切った連結成分を見るときに, 切っていない連結成分も含めていることに気がつく. if文を追加して, サンプルテストせずにNo.2とNo.3を通す. ここで残り20秒. 危なかった.......

最終成績25位 ABCEF5完

しめ

教員もかなりびっくりしていた. かなり胸を張れる結果が出せたかなあと思う.

一番良かったのは, 高専での長い付き合いだった同級生と一緒にICPCで良い結果が出せて本当に良かった. 二人に感謝...

横浜に旅行に行きたいです. よろしくおねがいします.

2020-02-06

hatena blogからGithub Pages + Hugo に移しました

はてなグループが消えてしまって, 競技プログラミングの記事が消えていくのをみて
僕も何か対策をしないとなあと思ってこうなりました

toptreeとか消えるのいやだからね...

How

github.com

これを使いました

画像が何故かダウンロードされなかったのでそれを直した
chart.apisをtex記法($$で囲む)ようにした

これでコマンド実行だけで移植できました

移植先はここです. このブログは残しておこうと思います.

niuez.github.io

これからもにうをよろしく！

2020-01-25

約数畳み込みを使って最大公約数と集合をうまく扱うメモ

書いて置かないと頭に置いておけない気がしたのでメモを残す. 間違ってたらごめん

これについて気になったので

メビウス関数とかを導入するとより形式的に約数とかを扱えるようになるのかなあ
— Niuez (@xiuez) 2020年1月22日

概要

約数畳み込み
メビウス関数
メビウスの反転公式(約数畳み込みの逆操作)
約数畳み込みと逆約数畳み込みのアルゴリズム $O(A \log{\log A})$
最大公約数の扱い
集合の扱い
AGC038C LCMsの解き方

ネタバレあるので気をつけてください

約数畳み込み

関数 $f(n)$ に対する約数畳み込みとは,

$\begin{eqnarray} g(n) = \sum_{ d | n } f(d) \end{eqnarray}$

あとで解説しますが, 方針としてはこの畳み込んだ後の $g(n)$ を問題を解けるように定義してやることでGCDを綺麗に扱うことができます.

メビウス関数

実際に $g(n)$ を定義してみます. 一番有名なのは $g(n) = \delta(n, 1)$ です. $\delta(n, 1)$ はクロネッカーのデルタです. このとき,

$\begin{eqnarray} g(n) = \delta(n, 1) = \sum_{ d | n } f(d) \end{eqnarray}$

を満たす $f(n)$ はメビウス関数と呼ばれ, $\mu(n)$ と書きます.(メビウス関数 - Wikipedia)

メビウスの反転公式(約数畳み込みの逆操作)

上の式のままだと, $f(n)$ を導くのは困難です. ここで登場するのがメビウスの反転公式です. これは, 約数畳み込みの逆操作に当たります.

$$ \begin{eqnarray} g(n) &=& \sum_{ d | n } f(d) \\ f(n) &=& \sum_{ d | n } g(d) \mu(\frac{n}{d}) \end{eqnarray} $$

これで $g(n)$ を定義してから反転公式を適用することで $f(n)$ を導くことができます.

約数畳み込みと逆約数畳み込みのアルゴリズム

約数畳み込みとその逆はnoshi91さんが計算量 $O(A \log{\log A})$ で計算するアルゴリズムの記事を紹介しています.

noshi91.hatenablog.com

逆約数畳み込みの実装例

template <class T>
void inverse_divisor_transform(vector<T> &a) {
    int n = a.size();
    vector<bool> sieve(n, true);
    for (int p = 2; p < n; ++p) {
        if (sieve[p]) {
            for (int k = (n - 1) / p; k > 0; --k) {
                sieve[k * p] = false;
                a[k * p] -= a[k];
            }
        }
    }
}

最大公約数の扱い

自然数 $n, m$ に対して,

$\begin{eqnarray} \sum_{d | n, d | m} f(d) \end{eqnarray}$

を考えると,

$$ \begin{eqnarray} \sum_{d | n, d | m} f(d) &=& \sum_{d | \gcd(n, m)} f(d) \\ &=& g(\gcd(n, m)) \end{eqnarray} $$

となり, $\gcd(n, m)$ に対する操作ができます. 例えば, $f(n) = \mu(n), g(n) = \delta(n, 1)$ とすると, $g(\gcd(n, m))$ は,「 $n, m$ が互いに素であれば $1$ , そうでなければ $0$ 」となり, 互いに素かどうかの判定ができます.

集合の扱い

例えば, $c_m(d) = [d | m$ ]という関数( $d$ が $m$ を割り切るなら $1$ , そうでなければ $0$ )を考えると,

$$ \sum_{d | n, d | m} f(d) = \sum_{ d | n } f(d) c_m(d) $$

と変形できます.

これを応用します. 自然数の集合 $S$ を考え, $c(d) = \sum_{m \in S} c_m(d)$ とすると,

$$ \begin{eqnarray} \sum_{d | n} f(d) c(d) &=& \sum_{m \in S}\sum_{d | n} f(d) c_m(d) \\ &=& \sum_{m \in S} g(\gcd(n, m)) \end{eqnarray} $$

となります.

$f(n) = \mu(n), g(n) = \delta(n, 1)$ を考えてみると, 「集合 $S$ の中に $n$ と互いに素な要素の数」を計算しています.

AGC038C LCMsを解く

atcoder.jp

ネタバレ回避用

$lcm(x, y) = x (\frac{y}{\gcd(x, y)})$ と変形します. 約数畳み込みを使う方針でやると, この $(\frac{y}{\gcd(x, y)})$ が最後に来てほしい気持ちになります. $g(n) = \frac{1}{n}$ と置くと,

$$ \begin{eqnarray} \frac{y}{\gcd(x, y)} &=& y \cdot g(\gcd(x, y)) \\ &=& \sum_{d | gcd(x, y)} f(d) y \\ &=& \sum_{d | x, d | y} f(d) y \\ &=& \sum_{d | x} f(d) s_y(d) \end{eqnarray} $$

ここで $s_y(d)$ を「 $d$ が $y$ を割り切るなら $y$ , そうでなければ $0$ 」としました.
応用して, 自然数の集合 $S$ を考え, $s(d) = \sum_{m \in S} s_m(d)$ とすると,

$$ \begin{eqnarray} \sum_{d | x} f(d) s(d) &=& \sum_{y \in S}\sum_{d | x} f(d) s_y(d) \\ &=& \sum_{y \in S} y \cdot g(\gcd(x, y)) \end{eqnarray} $$

と計算できて, これに $x$ を掛けると「集合 $S$ の中の各要素と $x$ の最大公約数の和」を計算できました.
計算量は, $O(A \log{\log A} + N \sqrt A)$ です.

atcoder.jp

ソースコード

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)

/* modint */
/* IO(niu::fin, niu::fout) */

const i64 MOD = 998244353;
using fp = modint<MOD>;


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

template <class T>
void inverse_divisor_transform(vector<T> &a) {
    int n = a.size();
    vector<bool> sieve(n, true);
    for (int p = 2; p < n; ++p) {
        if (sieve[p]) {
            for (int k = (n - 1) / p; k > 0; --k) {
                sieve[k * p] = false;
                a[k * p] -= a[k];
            }
        }
    }
}

constexpr i64 A = 1e6 + 1;

int main() {
  std::vector<fp> f(A);
  rep(d,1,A) {
    f[d] = fp(d).pow(MOD - 2);
  }
  inverse_divisor_transform(f);

  i64 N;
  niu::fin >> N;
  vector<fp> sum(A);
  fp ans = 0;
  rep(i,0,N) {
    int x;
    niu::fin >> x;
    fp res = 0;
    for(int d = 1; d * d <= x; d++) {
      if(x % d == 0) {
        res += f[d] * sum[d];
        sum[d] += fp(x);
        if(x / d != d) {
          res += f[x / d] * sum[x / d];
          sum[x / d] += fp(x);
        }
      }
    }
    ans += res * fp(x);
  }
  niu::fout << ans.value() << "\n";
}