Writter: slip0110 Tester: kioa341

Slides:



Advertisements
Similar presentations
Problem A : Everlasting...? 原案 : 泉 模範解答 : 黄・野田 解説 : 野田.
Advertisements

模擬国内予選2013 Problem F テトラ姫のパズル 原案:須藤 解答:大友、須藤 解説:須藤.
第1章 場合の数と確率 第1節 場合の数  2  場合の数 (第2回).
人工知能特論2011 No.4 東京工科大学大学院 担当教員:亀田弘之.
4 3 8 5 ℓのジュースと、  ℓの牛乳があります。 かさのちがいは何ℓでしょう? 1ℓ 4 3 8 5.
第1回 確率変数、確率分布 確率・統計Ⅰ ここです! 確率変数と確率分布 確率変数の同時分布、独立性 確率変数の平均 確率変数の分散
人工知能特論2007 No.4 東京工科大学大学院 担当教員:亀田弘之.
◎ 本章  化学ポテンシャルという概念の導入   ・部分モル量という種類の性質の一つ   ・混合物の物性を記述するために,化学ポテンシャルがどのように使われるか   基本原理        平衡では,ある化学種の化学ポテンシャルはどの相でも同じ ◎ 化学  互いに反応できるものも含めて,混合物を扱う.
1 正の数・負の数 2章 正の数・負の数の計算 §1 正の数・負の数の加法    ・減法  (8時間)
東邦大学理学部情報科学科 白柳研究室 小泉宏美
復習.
言語体系とコンピュータ 第5回.
Copyright © Kazuhito HAMANO 2007 all Rights Reserved.
演習00-0 “Hello,world![改行]”を表示するプログラムを作成せよ. 1 1.
I: Tokyo Olympics Center
Princess, a Strategiest
3 一次関数 1章 一次関数とグラフ §3 一次関数の式を求めること          (3時間).
Generating Functions (前半) B4 堺谷光.
Problem H ねこ鍋改造計画(仮) 秋葉 拓哉.
情報処理Ⅱ 2007年12月17日(月).
6学年 算数 ~ 式 と 計 算 ~.
本時の目標 負の数をふくむ3つ以上の数の乗法や除法の効率のいい計算のしかたに気づき、効率よく計算することができる。
中間発表用スライド 田中健太.
Mathematica入門 数学を数式処理システムで 上智大学理工学部 大槻東巳 TA: 吉本行気,清水元気 2012年6月.
共通鍵と公開鍵 暗号のしくみ 情報、数学ハイブリッド版.
最尤推定によるロジスティック回帰 対数尤度関数の最大化.
プログラミング演習Ⅰ 課題2 10進数と2進数 2回目.
データのバラツキの測度 レンジと四分位偏差 分散と標準偏差 変動係数.
13 Microsoft Word(4) 13.1数式の入力 Microsoft 数式の起動
電気回路Ⅱ 演習 特別編(数学) 三角関数 オイラーの公式 微分積分 微分方程式 付録 三角関数関連の公式
3次元での回転表示について.
論理回路 第8回
◎ 本章  化学ポテンシャルという概念の導入   ・部分モル量という種類の性質の一つ   ・混合物の物性を記述するために,化学ポテンシャルがどのように使われるか   基本原理        平衡では,ある化学種の化学ポテンシャルはどの相でも同じ ◎ 化学  互いに反応できるものも含めて,混合物を扱う.
 統計学講義 第11回     相関係数、回帰直線    決定係数.
ディジタル回路 3. 組み合わせ回路 五島 正裕 2018/11/28.
中学数学1年 1章 正の数・負の数 §3 乗法と除法 (9時間).
6. ラプラス変換.
デザイン情報学科 メディア情報設計 河原英紀
3次元での回転表示について.
ルンゲクッタ法 となる微分方程式の解を数値的に解く方法.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
中学数学1年 3章 方程式 §1 方程式とその解き方 (6時間).
情報理論2 第3回 小林 学 湘南工科大学 2011年10月25日 〒 神奈川県藤沢市辻堂西海岸1-1-25
福井工業大学 原 道寛 学籍番号____ 氏名________
情報基礎Ⅱ (第5回) 月曜4限 担当:北川 晃.
演習0 func0, func1, func2を作成せよ. main()関数の中で,func0()を呼び出しを実行せよ.
演習07-0 “Hello\n” “World!\n”と
生物情報ソフトウェア特論 (2)たたみ込みとハッシュに 基づくマッチング
Cプログラミング演習資料.
C言語 はじめに 2016年 吉田研究室.
2007/6/12(通信コース)2007/6/13(情報コース) 住井
サポートベクターマシン Support Vector Machine SVM
補講:アルゴリズムと漸近的評価.
データ構造とアルゴリズム (第5回) 静岡大学工学部 安藤和敏
東邦大学理学部情報科学科 白柳研究室 五味渕真也
PROGRAMMING IN HASKELL
~sumii/class/proenb2010/ml2/
本時の目標 正の数・負の数の加法の計算のしかたについて理解し、その計算ができるようにする。
2006/6/27(通信コース)2006/7/5(情報コース) 住井
精密工学科プログラミング基礎 第7回資料 (11/27実施)
多項式と数の乗法、除法について学ぼう。.
PROGRAMMING IN HASKELL
コンパイラ 2012年10月11日
演習00-0 “Hello\n” “World!\n”と
香川大学創造工学部 富永浩之 情報数学1 第2-2章 合同式の逆元と応用 香川大学創造工学部 富永浩之
精密工学科プログラミング基礎Ⅱ 第2回資料 今回の授業で習得してほしいこと: 配列の使い方 (今回は1次元,次回は2次元をやります.)
第3章 関係データベースの基礎 3.1 関係とは 3.2 関係代数.
コンピュータの高速化により, 即座に計算できるようになってきたが, 手法的にはコンピュータ出現以前に考え出された 方法が数多く使われている。
プログラミング演習II 2003年10月29日(第2,3回) 木村巌.
第1章 文字の表示と計算 printfと演算子をやります.
Presentation transcript:

Writter: slip0110 Tester: kioa341 Farey sequence Writter: slip0110 Tester: kioa341

問題概要 0以上1以下の既約分数の数列が与えられる 第n項は分母がn以下の数字である 第3項 ここで指定されたn項目の項数を求める {0/1 , 1/3 , 1/2 , 2/3 , 1/1} ここで指定されたn項目の項数を求める

計算量の確認 データセットの最大 10000 項番号の最大 1000000 データセットごとに、項数を求めていてはTLE データセットの最大 10000 項番号の最大 1000000 データセットごとに、項数を求めていてはTLE Fnはいつでも同じ値になるので あらかじめ1000000個、列挙できる 

アプローチ(1/2) 第3項 第4項 (第4項の項数) = (第3項の項数) + (第4項の追加項数) {0/1 , 1/3 , 1/2 , 2/3 , 1/1} 第4項 {0/1 , 1/4 , 1/3 , 1/2 , 2/3 , 3/4 , 1/1} (第4項の項数) = (第3項の項数) + (第4項の追加項数) 第4項で追加されたのは{1/4 , 3/4} 2/4 については、1/2としてすでに追加済み 追加されるものは4と4以下で互いに素の数字 追加される項数はオイラー関数を用いてφ(4)

オイラー関数とは? 正の整数nに対して、1からnまでの自然数のうち nと互いに素である個数を表す関数 1,2,3,4,5,6のうち6と互いに素なのは1と5 → φ(6) = 2 1,2,3,4,5,6,7のうち7と互いに素なのは7以外 → φ(7) = 6 構築方法は蟻本のP.243にソースコードがあります 2つ載っていますが、今回はどちらを使ってもTLEにはなりません

アプローチ(2/2) (第4項の項数) = (第3項の項数) + φ(4) (第n項の項数) = (第n-1項の項数) + φ(n)                 予めO(MAX_N)程度で構築可能                 アリ本P.243 参照 (第1項の項数) = 2 … { 0/1 , 1/1 } ↑の漸化式を用いてO(n)で予め項数の列挙ができる

ファレイ数列の性質 第5項 追加される項はその両隣の項の 分子同士の和と分母同士の和で求められる {0/1 , 1/5 , 1/4 , 1/3 , 2/5 , 1/2 , 3/5 , 2/3 , 3/4 , 4/5 , 1/1} 追加される項はその両隣の項の 分子同士の和と分母同士の和で求められる 2/5 = (1 + 1) / (3 + 2) 隣接する2項を{ a/b , c/d }とおいたとき (b * c) – (a * d) = 1である

結果 正解数:46 First Accept: ogiekako(20分)