Npc april fool2014

54 %
46 %
Information about Npc april fool2014
Humor

Published on April 1, 2014

Author: catupper

Source: slideshare.net

Description

NPC AprilFool's Contes 2014 解説
https://judge.npca.jp/contests/problem/9

NPC AprilFool's Contest 2014 A,B,C,E 解説

A.Over View Seat 2014

問題概要 ● SampleInput ● SampleOutput

問題概要 察して

答え 整数Nに対して 偶数なら2で割る 奇数なら3倍して1足す これを繰り返す 1になるまでの回数が答え

答え この処理をするとどんな自然数からはじめても いつか1になるという予想があります コラッツ予想という超有名未解決問題です 27は小さいくせに111回かかります wikipediaの27という記事でもそのことが記され ています  ググろう

結果 ● FirstAC – anta – 00:07:16 ● AC数 – 9人

B:誕生日はエイプリルフール

問題概要 ● 自然数列が与えら得れるので – A^D + B^D = C^D となるA,B,C,Dの組の個数を求めよ

部分点解1(0点) ● 愚直に全通り試す(N^4) ● N 100≦ くらいのケースなら通る – 小課題1(0点)は通る

部分点解2(0点) ● A^D + B^D = C^D ● A,BがきまればCも決まる ● A,B,Dだけ試せば良いO(N^3) ● N 300≦ くらいのケースなら通る – 小課題2(0点)まで通る

想定解3(1AC) ● A^D + B^D = C^D ● ここで、ある有名な定理を思い出す – フェルマーの最終定理 ● Dは1か2 ● A,B全通りとDをすこし調べれば良いO(N^2) ● すべて通るってACが得られる

想定解3(1AC) ● A^D + B^D = C^D ● AもしくはBが0のときがあるので別で数えな ければならない ● そちらもO(N^2)で数えられる。 ● なおD=0のとき1 + 1 = 1となるので誤って数 えないようにしなければならない。

結果 ● FirstAC – japlj – 00:28:20 ● AC数 – 11人

C:新しい苗字

問題概要 ● 男だけの自治区がN個、女だけの自治区がM個 ● 各自地区内の人数が与えられる ● あと恋人関係も与えられる ● 同じ自治区内で恋人同士以外の苗字は違うよ うにしたい ● 必要な苗字の個数の最小値を求めよ

問題概要 ● 同じ自治区内の恋人は一人と数えて問題ない – 恋人の数だけ自治区の人口を減らせば良い ● 同じ自治区内だとむりみたいなこと書いてあ るのでよくわからないけど彩色問題だと思 う。

グラフの彩色 ● とりあえずグラフを構築 ● 同じ苗字になってはいけない人同士を辺で結 ぶ。 ● 同じ苗字にならないといけない人同士は同じ 頂点とみなす。 ● 双対を取る (頂点を辺に替える) ● きれいな二部グラフの辺彩色問題ができる ● 次数の最大値を求めるだけ = 人口の最大値

結論 ● 各自治区について自治区内恋人の数だけ人口 を減らす ● 人口の最大値が答え ● やるだけ

結果 ● FirstAC – namonakiaccount – 00:39:02 ● AC数 – 13人

D:避難訓練が随分前にありました

問題概要 ● 大きさN*Mの2次元配列がある ● 1~N*Mの整数を埋める ● どの頂点もそこに入る数字の値が – 右よりも大きい – 上よりも大きい

問題概要 ● 大きさN*Mの2次元配列がある ● 1~N*Mの整数を埋める ● どの頂点もそこに入る数字の値が – 右よりも大きい – 上よりも大きい ● などとちょっとややこしいので言い換える

問題概要 ● N*Mの長方形のヤング図形から得られるヤン グ盤(標準盤)の個数を求めよ ● わかりやすい

ヤング図形とはなにか ● 正方形の集まり ● 下の行に行くにつれて数が単調非減少 ● 左上に寄った感じで三角形っぽいもの ● ここに数字を入れたものがヤング盤 ● ルールは左よりも上よりも大きい数字を入れ る – 埋めた例 →

ヤング盤の数え上げ ● ヤング盤のなかでも1~マスの個数の数字を一 個づつ入れたものを標準盤という ● それの数え上げはフック長というものを使う と一瞬でできる ● フック長というのは各マスについて求まる ● 真右にいるマスの個数 + 真下にいるマスの個数 + 1 ● →先ほどのヤング図形での例

ヤング盤の個数 ● 証明は割愛 ● ヤング版の個数は (マスの個数)! ÷ (各マスのフック長の総積) ● 例: →これの場合 – 10! ÷ (7 * 5 * 4 * 3 * 1 * 5 * 3 * 2 * 1 * 1) – = 288

長方形もヤング図形 ● この問題でも同じことをすればよい ● 愚直に計算するとO(NM)かかる – 小課題1(0点)が得られる ● いろいろ頑張ると解ける

エイプリルフールの一般テク ● MOD1,000,000,007 = 素数 で答えを出す – NMが1,000,000,007より大きければ答えは0 ● NM!はO(NM)かかる おそい – 10^7の倍数の階乗を予め求めて埋め込む ● N行目のフック長の総積とN+1行目の総積はだ いたい同じ O(1)でだせる ● 1行目だけまじめに階乗を計算, 残りはO(N)

エイプリルフールの一般テク ● 続き) ● 1行目の階乗を求めるのは先程の埋め込んだ値 を使えば良い。 ● のこりはO(N)だがNとMは入れ替えても良いの でO(min(N, M))で行う ● NM 1,000,000,007≦ なので ● min(N, M) √1,000,000,007≦ ● まにあう

逆元 ● 最後に割り算するので逆元を求めなければな らない ● MOD-2乗しましょう

結果 ● FirstAC – snuke – 01:08:59 ● AC数 – 7人

Add a comment

Related presentations

Valentine's Day Blues

Valentine's Day Blues

March 31, 2014

The big hit after Valentine's day....

Dr. mOe Anderson is a writer, dentist, humorist, and grandmother with a quick wit ...

Quadrants and you

Quadrants and you

April 3, 2014

Homestuck and South park

GORDO OU ESQUELETICO

GORDO OU ESQUELETICO

July 30, 2009

GORDO OU ESQUELETICO

Related pages

Hernandez vs Npc - Documents

Npc april fool2014 NPC AprilFool's Contes 2014 解説 https://judge.npca.jp/contests/problem/9 Afiche npc torques diesel Npc novas mídias Almanah NPC ...
Read more

Humor slides, presentations - slidesearch.net

Npc april fool2014. Humor. Tweet ...
Read more

Easy Npc Maker - Documents

Easy Npc Maker. by esopo-el-frigio. on Aug 18, 2015. Report Category: Documents. Download: 0 Comment: 0. 1. views. Comments. Description. Para NPC fáciles.
Read more

【四月馬鹿】ゲーム業界のエイプリルフールネタまとめ : ゲーハー黙示録

"お気に入りのNPCと仲良くなれるシステム" ... http://members.redsonline.jp/evecam/april_fool2014/index.asp
Read more