f(x)が最小であるから少なくともf(v)<f(x)となるvについてはSとTで状況が同じであるため、xを選ぶ際の障害にはならない。f(y)が最小であることから、f(x)<f(v)<f(y)となるvは選ばれていないはずである。f(y)<f(v)かつv∈Tとなるvに関しては、dist(x,y)<X≦dist(v,y)であるはずで、「f(x)<f(y)<f(v)」「dist(x,y)<X≦dist(v,y)」からX≦dist(v,y)<dist(v,x)が言えるため、障害にならない。

で、また計算量を無視してDFSで集合S（証明内で定義したやつ）を求めてみようとしてみる。

部分木iだけみたときに選ばれる集合をS_iとする。

部分木i内の頂点vがv∈Sならばv∈S_iとなることは明らか。

S_iとS_jをマージするときは、集合に含まれる頂点を深い順に見て、選べるものだけ選ぶとよい。

S_iの性質として「根から距離X/2以下の頂点は高々1つしかない」ということが言える（もし2つ以上あるなら明らかにその2頂点の距離はX以下であるため）。そのような頂点をSa_iと呼ぶことにする。

Sa_iとSa_jの距離も明らかにX以下なので、少なくともどちらかは捨てなければならない。

また、Sa_i,Sa_j以外の頂点はマージした後も全て選ぶことが出来る事も言える。根からの距離がX/2より大きいため、それらの距離はXよりも大きくなるためである。

Sa_iとSa_jの話に戻るが、このうち深い方以外は必ず捨てることになる。f(Sa_i)<f(Sa_j)とすると、Sa_iが選べずSa_jが選べるというケースはありえないためである。

つまりマージの際行うべきことは、以下の通り。

Sa_i,Sa_j以外の頂点を全て採用する。

Sa_i,Sa_jのうち最も深いものをSaとする。

Saから距離X以内の頂点がない場合はSaを採用する。

ここで、「Saから距離X以内の頂点」となりうるものは「根から距離X/2以下の頂点」が存在しない部分木の頂点でもっとも根に近いものしかない点に注意したい。

マージすべき部分木が３つ以上の場合も上と同様の議論ができる。

上記に基いて効率的なアルゴリズムを設計する。

dfsをして、各部分木で選んだ頂点のうち最も根に近いもの（と選んだ頂点の個数）を求めていく。

ある頂点v以下の部分木に関して計算するときは、その子の部分木内で最も根に近いものを深さ順にソートし、深いものから順に選べる限り選んでいく。

選んだもののうち最も根に近いものをdfsの戻り値として返す。

かなりシンプルなアルゴリズムになった。

しかしまだソートのlogがついているので改善する。

実は、マージのときには「X/2以下のもののうちの最大値」と「X/2より大のもののうちの最小値」を求めていくだけでいい。

open all / close all

generated by indenter

以下ソースコードです。マクロ多くてごめんなさい。

#include略
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define gep(i,g,j) for(int i = g.head[j]; i != -1; i = g.e[i].next)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcount
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define df(x) int x = in()
#define dame { puts("-1"); return 0;}
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,vector<T>,greater<T> >
#define bn(x) ((1<<x)-1)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
inline void priv(vi a) { rep(i,sz(a)) printf("%d%c",a[i],i==sz(a)-1?'\n':' ');}
template<typename T>istream& operator>>(istream&i,vector<T>&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(vector<T>&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>ostream& operator<<(ostream&o,vector<T>&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>ostream& operator<<(ostream&o,pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
const int MX = 100005, INF = 1001001001;

int n, m;
vvi to, co;
int cnt;
int dfs(int v, int x, int p=-1) {
  int a = 0, b = INF;
  rep(i,sz(to[v])) {
    int u = to[v][i];
    if (u == p) continue;
    int r = dfs(u,x,v)+co[v][i];
    if (r*2 >= x) {
      mins(b,r);
    } else {
      --cnt;
      maxs(a,r);
    }
  }
  if (a+b < x) return b;
  ++cnt;
  return a;
}
int f(int x) {
  cnt = 0;
  dfs(0,x);
  return cnt;
}

int main() {
  scanf("%d%d",&n,&m);
  to = co = vvi(n);
  rep(i,n-1) {
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    --a; --b;
    to[a].pb(b); co[a].pb(c);
    to[b].pb(a); co[b].pb(c);
  }
  int l = 1, r = INF;
  while (l+1<r) {
    int c = (l+r)>>1;
    if (f(c) >= m) l = c; else r = c;
  }
  cout<<l<<endl;
  return 0;
}

2016-12-26

Xmas Contest 2016

Xmas Contest 2016 にご参加いただいた皆様、ありがとうございました＆お疲れ様でした。

難易度が高すぎて順位表が大変なことになっていましたね。。
１問をじっくり考えるのに慣れていない方には少しつらいセットだったかもしれないです。
でも、なんだかんだ出来ることはあって座るだけにはならなかった方が多く、その点は良かったかなぁと思っています。

それでは解説を...のつもりだったのですが、解説をガッツリ書く体力が残っていないため、ヒントだけで失礼いたします。

＊追記：解説情報です。 A B C F H I

ヒント

A (原案：snuke)

N=15のとき、8,4,2,1と取っていくと4回ですが、a=[0,8),b=[7,15),c=[7,8)とすると３回の質問で総和（a+b-c）が求められる。

このように引き算を駆使すると、二進数での桁数/2回くらいの質問で総和が求められる。

ちなみに10回必要になる最小のNは二進数で11010101010101011です。

B (原案：snuke)

50点を超える最も簡単な解法は、スターンブロッコット木を、分母をx分子をyとしてそのまま埋め込む解法だと思います。

70~90点はフラクタルっぽい図形を頑張って構成すれば良いです。

満点は64*64に収めなければなりません。余白は1点しか許されません。

これは図を使って説明しないと行けないので後で。

C (原案：japlj)

二分探索すると01列を切ったり捨てたりして1を残したら勝ちというゲームになります。

0,1のかわりに-1,1で考えます。

累積和をとります。

全体の累積和が0でない場合、正なら勝ち、負なら負けです。

0の場合は、累積和が0となっているような切れ目の個数が奇数個なら勝ちです。（先に切る番の場合）

戦略は上記の結果を証明しようとすると自然と導かれます。

D (原案：japlj)

簡単枠のはずでした（自明ではないですが）が昼の部ではなかなか解かれませんでした。

各サイクルに注目すると、

サイズが2なら1回でいい。

サイズが3以上なら2回必要になる。

サイクルに出てくる数たちを列としてみると、全体をreverseするのと1狭い区間をreverseするのをやると1shiftが作れます。

例えば234561→[165432]→1[23456]という感じです。reverseは複数のswapを並列に行うだけで実現できますね。

E (原案：japlj)

まずはクラスタリングしましょう。

クラスタリングは超高精度でできます。

各人に対して、その人と同じ選択肢が選ばれている回数を求めて、その順でソートして10,10,10と区切ってやればいいです。

あとは各問題について最尤値推定をすればいいです。（2/3の人で多数決をするだけでも通ります）

F (原案：snuke)

見掛け倒しです。

実は操作は対称性が高く、K次回文はreverseしてもK次回文になります。

mod2で答えればいいので、もともと回文であるようなK次回文の個数さえ求めれば良いことになります。

K=0のときは回文の個数を求めればいいです。

K>=2のときは追加、置換*K-2、削除とすればもとの文字列に戻すことが出来るので、これも回文の個数を求めればいいだけです。

K=1のときは「もとが回文」かつ「1長いものまたは1短いものも回文」でなければならず、どの文字とどの文字が同じでなければならないかを考えると、すべての文字が同じ文字列しか条件を満たさないということがわかります。

G (原案：snuke)

最大流に落としましょう。

そのグラフは平面グラフになっているので、最小カットを最短路で求めることができます。

有向グラフの場合は逆辺としてコスト0の辺を張らないといけない点に注意。

H (原案：snuke)

二分探索した後、結構シンプルな貪欲法で解けます。証明が面白いです。

証明は後で。

I (原案：snuke)

いろんな塗り分け方をして偶奇性を見ると各テトロミノ特有の性質というのが検出できます。

後で。

J (原案：japlj)

条件を満たすように数列を作ってくださいとしか解説のしようがあまりない気がする。

(1)はなんと、全部満たせます！

(2)は後のことをあまり考えずに貪欲に置ける数の中で最も大きいものを置いていくだけでいいです。変態的なパズルです。

open all / close all

generated by indenter

2016-12-26

ACC2016 24日目「色塗り２」解説

競プロ

Advent Calendar Contest 2016 24日目の問題「色塗り２」を出題させていただいたので、その解説
問題はこちら。

解説

まずは「葉が b 個根に付いた根付き木の頂点を c 色で塗り分ける場合の数」を考えてみます。

コラム

根付き木の同型性に関して扱うときの常套テクとして、各子に何らかの順序をつけてソートすることによって標準化をします。

つまり、「葉に塗る色の番号は左から見たときに昇順になっていなければならない」というルールを付けて数え上げることにすると良いです。

そうすることで、重複無く数え上げることができます。

立式をしてみましょう。

よく見るとまんま重複組み合わせですね。

${}_c H_b*c = {}_{c+b-1} C_b*c$

$_c H_b$ は葉の塗り分け方、 $*c$ は根の塗り方。

元の問題に戻って考えてみます。

「葉が b 個根に付いた根付き木の頂点を c 色で塗り分ける場合の数」を d とします。

すると、元の問題の場合の数は「葉が a 個根に付いた根付き木の葉を d 色、根を c 色で塗り分ける場合の数」と同じです。

式にするとこうなります。

${}_d H_a*c = {}_{d+a-1} C_a*c$

dを展開した式はこうなります。

${}_{({}_c H_b*c)} H_a*c$

式の計算方法を考えます。

${}_{({}_c H_b*c)} H_a*c$ の偶奇を求めたいのですが、何も考えずにmod 2で計算してしまうとおかしなことになります。

例えば、 ${}_5 C_4 \equiv 0 \ne 1 \equiv {}_1 C_0$ という具合です。

さてここで、 ${}_x C_y\ mod\ 2$ の性質について思いを馳せます。

結論から言うと、 $x\&y = y$ なら 0、そうでないなら 1 です。

パスカルの三角形の偶奇を眺めてみたりすると分かるかもしれません。

ここで重要なのが、y を超えるような2冪数を T としたとき、 $x\&y = (x\%T)\&y$ であることです。

つまり、x の正確な値が分かっていなくても、 $x\ mod\ T$ の値さえ分かっていれば ${}_x C_y\ mod\ 2$ が計算できます。

$a \lt 2^{20}$ なので、 ${}_c H_b*c\ mod\ 2^{20}$ が求められれば良いことになりました。

あとは剰余演算に慣れた人ならそれほど難しくありません。

剰余演算パート

${}_c H_b*c\ mod\ 2^{20}$ の求め方を考えます。

${}_c H_b = {}_(c+b-1) C_b = (c+b-1)!/b!/(c-1)!$ なので、階乗どうしの割り算が出来れば良いです。

階乗は前計算しておけばいいのですが、そのまま計算すると割り算で詰むので、工夫が必要です。

値を「奇数*(2冪)」という形に分解し、「奇数」と「指数の肩」の組 $(O,E)$ を計算しておきます。

すると $x/y = O_x/O_y*2^{E_x-E_y}$ という形で計算ができます。

残る問題は奇数での割り算ですが、一般にmodの値と互いに素な数には逆元が存在するため割り算が可能です。

xのmod mでの逆元は $x^{\phi(m)-1}$ と計算できます。

$\phi(m)$ はオイラー関数（mと互いに素なm以下の整数の個数）で、 $\phi(2^{20}) = 2^{19}$ です。

詳しくは蟻本を読むと良いでしょう。更に詳しくは群論とかの本を読むといいかも。

おまけ

元ネタ

KUPC2016のI問題「色塗り」で、本番でそのままmodで計算していってもいいのか考えて、mod 2だとダメだよなぁと思ったのがこの問題を作ったきっかけです。

mod 10億7だとコンビネーションの分母がmodと互いに素になるのでOKっぽい。

発展課題

この問題ではmod 2までで諦めてしまいましたが、 ${}_x C_y\ mod\ 2^z$ を高速で計算できたりしませんかね？→sigma氏からnCm mod 素べきの計算法の論文を教えてもらいました

open all / close all

generated by indenter

2016-12-04

IOIへの出題について - 解説編

JOI 競プロ

問題はこちら

judgeはここのday1の２問目

部分点１

部分点制約：N ≦ 8

並び替えを全部試せばいいです。

部分点２

部分点制約：N ≦ 16

巡回セールスマン問題に落としてbitDPでできます。

部分点３

部分点制約：答えが 0 かどうかだけを判定すれば良い

これが想定通りに解ければ満点はすぐそこです。

ただ、よく分からずに貪欲を頑張って考えるとこの部分点までは取れたりするようです。

まず、(A,B) = (INF,1) のトンネルを新たに作り、トンネルをループ状に繋げられるようにする問題だと考えたほうが少し考えやすくなります。

INFはmax(A_i)で十分です。

各トンネルは「体が A_i 以下なら入れる」ではなく、「ちょうど A_i なら入れる」＋「好きなタイミングで何回でも体を 1 大きくすることができる」と考えたほうが考えやすくなります。

A_i, B_i を数直線上にプロットし、A_i→B_iの有向辺を張ります。

このとき、以下のようなサイクルが存在すれば答えは 0 となります。

- トンネルの辺をちょうど１回ずつ通る（下図の赤辺）

- 数直線を右に進むのは自由（下図の緑辺）

例えば、1-緑->2-緑->3-赤->1-緑->2-赤->5-緑->6-赤->8-赤->1 というサイクルがあるので、このケースの答えは 0 です。

トンネルを頂点ではなく辺にしたことにより、ちょっとオイラー路っぽい問題になりました。

しかし、緑辺を通る回数がよく分からないのでまだオイラー路問題ではないです。

さて、各緑辺を通る回数は自由なのですが、実は一意に定まります。

各頂点に、赤辺の「入次数ー出次数」を書き込み、左から累積和を取れば、各緑辺を通るべき回数が求まります。

緑辺を通るべき回数が負になった場合はその時点で答えは 0 ではないと言えます。

これで完全に（有向）オイラー路問題に帰着できました。

あとはオイラー路の条件「入次数＝出次数」と「連結である」をチェックすれば良くなりました。

次数条件は緑辺を通る回数を求めた時点で自動的に満たされているので、連結性のみを判定すれば良いです。

連結性条件は無向グラフだと思って判定しても大丈夫なので、適当にやればOKです。

あらかじめ座標圧縮をしておかなければならない点だけ注意して下さい。

満点

スモールライトについて考えなければなりません。

スモールライトは下図の青辺のような、数直線を左に進む辺に対応します。

この問題は、青辺を追加する本数を最小化する問題ということになります。

青辺が必要になる状況は以下の２通り考えられます。

- 「緑辺を使う回数」が負になる箇所を相殺する

- 青辺と緑辺をセットで追加して２つの連結成分をつなげる

まずは負の箇所の相殺をします。このとき、相殺した箇所は連結になる点に注意して下さい。

次に、全体を連結にすることを考えます。

連結成分の形は下図のように結構複雑な形になることがあるので単純には行きません。

数直線上で隣接する頂点の間に青辺（＋逆向きの緑辺）を張ることにより、それらを連結に出来ます。

さてここで、連結性判定時には辺を無向だと思って良いことを思い出すと、以下のように辺を張ったグラフのMSTを求めればいいことになります。

- 赤辺と緑辺と負を相殺するための青辺（コスト＝０）

- 数直線上で隣接する頂点間を結ぶ青辺（コスト＝距離）

これで解けました。

まとめ

ハミルトン路がオイラー路になり、MSTになりました。

open all / close all

generated by indenter

2016-12-02

IOIへの出題について

JOI 競プロ

※この記事はCompetitive Programming （その2） Advent Calendar 2016 - Adventarの２日目の記事です。
IOIにあまり興味が無い方は、下の方の僕が出題した問題の方だけをお読み下さい。

IOIとは
IOIへの問題の応募
IOIに問題が採用された時の流れ
IOI 2016に採用された問題
- 問題
- 制約
- 入力例
- 部分点
IOIの大会中のコンテスト以外のイベント
IOI後
まとめ

IOIとは

IOIとは"International Olympiad in Informatics"の略で、日本語で言うと「国際情報オリンピック」のことです。

IOIの大会としての特徴は以下のとおりです。

高校生以下が対象の世界大会
1989年から開催されており、2016年に第28回が行われた
各国で国内選抜があり、日本はJOIが選抜を行っている
日本から選手団が派遣されたのは1994~1996と2005~現在
2018年に日本（つくば）で開催予定

競プロのコンテストとしての特徴は以下のとおりです。

５時間で３問程度のコンテストが２回開催され、その合計得点で順位が決まる
誤答/時間のペナルティはなく、そのかわり大量の部分点が存在する
マラソン的な問題や、リアクティブなどの変わった形式の問題も出題される
- 例：odometer, saveit, artclass
最近は完全フィードバック（ジャッジ結果がすぐに分かる）
選手はコンテスト中に順位表を見ることが出来ない

IOIへの問題の応募

毎年、その年の公式サイトに「Call for tasks」という形で問題募集の情報が公開されます。
今年のものはここです。
近年は問題の集まりがあまり良くないらしく、毎年応募期限が延長されています。
今年の期限は12/15に延びたので、まだ間に合いますよ！

IOIは時間ペナルティなどのないコンテストなので、部分点が多い問題が求められています。
簡単枠ならその限りではないかもしれません。
また、５時間３問なので、実装は重くてもOKです。
ただし、シラバスの範囲内からしか出題できないので注意してください。
IOIで求められている問題の傾向は以下のとおりです。（多分）

意味のある部分点の多い難しい問題
部分点はそれほど多くないが、面白い問題
変わった形式の面白い問題（ここ２年は出題されていない）
簡単枠の面白い問題（恐らく競争率が高い）
汎用的でかつ珍しめのテクニックを使う問題は好まれる傾向にありそう

応募する際に送る必要のある情報は以下のとおりです。
問題に自信があれば、なるべく親切にいろいろなファイルを作っておくと採用率が上がって良いのではないかと思います。

問題文（英語）
- 運営がストーリーを変えたりすることもあったりするので、原案を伝える程度のもので大丈夫だと思います。
- 過去問が公式サイトで公開されているので、構成はそれを参考にすると印象が良くなるかもしれません。
- 自分はmarkdownファイルとそれをpdfにしたものを用意しました。（txtでもなんでも良いと思います。）
解説
- 部分点を含めた解法を書いた文書を用意する
解答ソースコード
- IOIの形式は少し特殊なので、過去問のデータを取ってきてそれに合わせて書くと良いでしょう。
テストデータ
- 必須ではありませんが、あるとかなり印象が良くなると思うので用意することを推奨します。
- ジェネレータも置いておくとなお良いと思います。
プロフィール
- 作問者が何者なのかを書きます。協力者がいる場合はその人も。
- 連絡先、氏名、所属、国籍、情報オリンピックにおける立場（選手のトレーナー/委員会の役員/無関係等）を書きました。
readme
- フォルダ構成を書いておくと親切だと思います。

もし実際に応募する場合は公式サイトを読んでもらうのが良いと思います。
応募を真剣に検討している方は、僕に声をかけてもらえれば、参考として僕が送ったファイル類を渡します。

IOIに問題が採用された時の流れ

2015にも１問送ったのですが、落ちました。落ちた場合は何も連絡は来ないので少しさびしかったです。

去年秋のある日大学に向かうバスで思いついた問題が自信作で、部分点もある程度つけられそうだったのでIOIに送ってみることにしました。
この年のCall for tasksの期限は年始すぐくらいで、帰省中にも作業してたような記憶があります。
1/11に提出し、しばらく経っても音沙汰がなかったので少し落胆していると、5/31に採用通知が来てめちゃくちゃ嬉しかったです。

問題が採用されると、shortlistという9問くらい(?)の問題候補の中に入ります。
実際に使われるのはこのうちの6問くらいで、残りは予備・来年に繰り越しになります。

問題が採用されてshortlistに載ると、IOIに招待され、IOIにguestとして参加することが出来ます。
もちろん、断ることも出来ます。
現地では特に仕事がないので、日本選手団と行動するなり、guest用の観光に行くなり、自由にしていればいいです。
ただし、問題が実際に使われて公開されるまではあらゆる情報が秘密なので注意が必要です。
現地に行く場合は、現地についてから「え、なんでいるんですか？おっ、writerか〜？」となるのは仕方ないので問題なしです。

IOI 2016に採用された問題

Code Festivalの本戦の問題を作ろうと、風船釣りを元ネタとした問題を作ろうとしていたときに原型が出来ました。
結局これは風船が全く関係ない問題になり、その後風船ツリーが出来ました。
その後、少し問題設定をいじると、自作問題の中でも 1, 2 を争うくらい好きな問題になりました。

さて、送った問題ですが、ドラえもんのガリバートンネル（とスモールライト）を知っていると理解しやすいと思います。

問題

ガリバートンネルが N 個あります。
トンネル i の入口のサイズは A_i、出口のサイズは B_i です。
snuke君はこれらのトンネルを１列に並べ、順番に通り抜けていこうとしています。

トンネルの入口に入るには、体のサイズが A_i より小さくなくてはなりません。
トンネルの出口から出てくると体のサイズはちょうど B_i になります。

snuke君の体のサイズは最初 1 です。
snuke君はスモールライトを持っていて、これを 1 秒使うと体のサイズを 1 減らせます。

トンネルの並べる順番を工夫したときの、スモールライトを使う必要のある秒数の最小値を求めて下さい。

実際に出題されたときは、ジェットコースターの侵入速度制限付きのレールユニットを組み合わせる設定になりました。

制約


2 ≦ N ≦ 200,000
1 ≦ A_i,B_i ≦ 10^9

入力例

(1,7) (6,6) (4,3) (5,8) の順で並べれば、１個目→２個目で１秒、２個目→３個目で２秒使えば良くて３秒で済み、これが最小なので答えは３。
体のサイズは、1-tunnel->7-light->6-tunnel->6-light->4-tunnel->3-tunnel->8 という感じで変化していくことになります。

部分点

1. (11点): 2≦n≦8.
2. (23点): 2≦n≦16.
3. (30 点): 答えが 0 かどうかだけ判定すれば良い
4. (36点): 満点

解説は別記事で紹介します。
また、ここのday1の２問目でonline judgeが利用できます。

IOIの大会中のコンテスト以外のイベント

1. 到着日
2. register、開会式
3. コンテスト１
4. エクスカーション１
5. コンテスト２
6. エクスカーション２
7. 閉会式
8. 出発日

というスケジュールです。
１週間と長いですが、あっという間です。

毎年、JOIから問題文の翻訳等をするための随行員が派遣され、各コンテスト日の前日夜に問題文の翻訳をします。
あと、大会期間中何度か開催される全体会議にも出席したりします。
僕はIOI 2015の随行員で、カザフスタンに行っていました。
そして今年はguestであって随行員ではなかったのですが、暇なので翻訳のお手伝いをしました。

大会期間中撮りためた写真をtumblrにまとめたので、IOIの様子が気になる方や、わふれるかが見たい方はどうぞ。
JOIの写真速報もあります。

IOI後

IOI2016の優勝者jcvb氏と帰りの空港で会ったので少し話しました。
結構前なので記憶が曖昧ですが、名前の由来についての話題をきっかけにして話しかけた気がします。
"jc"は本名のイニシャルで、それだと短すぎてIDが取れなかったので適当に2文字つけたと言っていたと思います。
出題の件に関しては「ロシア人が作ったのかなと思っていたが、コーチから日本人が作ったらしいという話を聞いた」みたいなことと、問題に関する良好なフィードバックがもらえて嬉しかった憶えがあります。

その数ヶ月後、CodeFestival 2016でksun氏に「are you snuke？本戦のwriterだよね、reverseの問題良かったよ。」的な感じで話しかけられました。
ksun氏はIOI2016にもカナダ代表で来ていたのでIOIの話題を振って「IOIの問題も書いたよ。」「ま？あの問題面白かった。本番中は解けなかったけど後で解いたよ。」的な話ができて嬉しかった。

IOIへの出題は、こんな風にIOI後に海外勢と話すときに話題に出せるという特典もありますよ。

まとめ

今後のIOIの開催国は、イラン、日本、アゼルバイジャン、シンガポールです。
IOIは世界最大級の規模の大会に招待される絶好の機会です。
実は問題が不足気味で穴場だったりするのでチャンスかもしれません。
IOIに問題を送って普段行かないような国への旅行を楽しんでしまいましょう。
あるいは、IOI2018に良問を送りまくってTsukuba大会を最高のコンテストにしましょう。

Advent Calendar、明日はehaさんの「hackerrankがくれたビットコインの使い道について」とyurahunaさんの「競プロを初めて1年になるので振り返ります」です。