MathematiKa 2K10 - kozima の雑記

参加しました。9 問中 6 問解いて順位が 15/173 という，いいのかそうでもないのか分からない結果。すぐ解ける問題とさっぱり解けない問題に，わりときれいに分かれました。

A1=12345678987654321, A2=1501166737738407260760426 のとき

を満たす自然数の組 (a, b) はいくつあるか，という問題。

答えは A2/A1 の約数の個数。A2/A1 を素因数分解する必要がありますが，とりあえず bigint が使える言語でやってみればすぐできます。factor コマンドでもよかったかも。

ただの線形代数の問題。 $M_{2\times 2} \simeq R^4$ なので 4×4 の行列表示を求めて計算するだけ。

与えられた 50 枚の円板の和集合の，境界の長さを求める問題。

それぞれの円板の周について，他の円盤で覆われていない部分の長さを求めて足すだけ，と思ったのだけど結局通らず。よくわかりません。

条件

を満たす正整数から正整数への写像 f について，与えられた

などなど 46 組の関数値から

f(17483011089091266158836700144520140026096445689)

を求める問題。ちなみに素因数分解してみると

17483011089091266158836700144520140026096445689 = 211 * 211 * 3373 * 25639 * 46183 * 51973 * 53507 * 55217 * 81899 * 83077 * 94109

となります。

数値が大きいので bigint 必須ですが，実は素因数分解してみたら 10^5 以上の素因数をもつものはどこにも出てきません。

あとは f に関する条件から地道に計算していけばできます。

1 から 100 までの番号が書かれたカードをランダムな順で積んで，「一番上のカードに書かれた数字の枚数だけ上から取って順番を入れ替えて元に戻す」という操作を繰り返すとき，一番上に 1 が来るまでのステップ数の最大値はいくつか，という問題。

たぶん誰も解けてません。Knuth が同じ問題を考えてたとか。

三角柱の頂点をランダムに動く動点が指定された時間に指定された場所にいる確率は，という問題。

冷静に漸化式を立てればすぐ解けるはず。高校の教科書〜大学入試レベル？

2×10^16 のマス目を，条件を満たすように二色に塗り分ける(という表現ではないけど)方法の総数を計算する問題。ただし答えは mod 1000000009 で出す。

下の行で troops がいる一番左のマスが k 番目がである場合の配置が k の式で出せて，すべての k にわたる和も簡単な式になります (どこにも troops がいない場合も忘れないように)。k の指数関数が出てくるので modular exponentiation で処理。

問題文に間違いがあったので時間とられました。しかし修正される前に何人か正解していたのが謎。

n^n を計算するんだけど，途中で 10 桁超えたら上と下を切り落としながらやったら答えはいくつになりますか，という問題。実際にやるのは n = 1111111111 (10 桁) のとき。

コンテスト中には解けなかったんですが，後でもしやと思ってやってみたら 42 万回ぐらいで循環してるみたいです。

問題文がやたら長い上にとっつきにくいですが，よく読めば指示通りに答えを書くだけ。論理回路に慣れていれば暗算でもできそうな問題です。論理式に馴染みがない人にはハードルが高かったかもしれません。