yukicoder No.523 LED

解法

LEDをポチポチする順番を順列にして考えてみると, 例えばN=3のとき, ①①②②③③の並べ方を数える問題になります. このとき, 同じ番号のものは区別せず, 場合の数は \frac{6!}{2^3} = 90となります. 一般のNに対して答えは次の式で表されることがわかります.
 P_N = \frac{(2N)!}{2^N}
制約から (2N)!はループを回しながら剰余をとっても間に合います. 2^Nは, まず繰り返し二乗法を用いて k = 2^N \space mod \space pとなるkを求めた後, さらに繰り返し二乗法を用いてフェルマーの小定理
 k^{-1} \space \equiv \space k^{p-2} \space mod \space p
からkの逆元を求め, k^{-1}(2N)!を計算して答えです.

その他

実は答えの式 P_N = \frac{(2N)!}{2^N}
 (2N)! = \prod_{k=1}^n (2k-1)2k
より
\frac{(2N)!}{2^N} = \prod_{k=1}^n (2k-1)k
と変形できるため, 一回のfor文で求めることもできます. スゴイ

Haskellでオートマトン

いろいろ昔作ったコードを漁っていると, 半年前に作ったオートマトンのコードがあったのでここに供養.

作成の動機

オートマトンの講義があって, その復習というのもあったと思いますが, Haskellの勉強が主だった思います. Haskellは代数構造を扱いやすいので, オートマトンのような構造と相性が良いと思ったのもあります.

作成したもの

DFA , NFA, ε-NFAを動作させることができるプログラムをそれぞれ作成し, さらにオプションとして機能を少し付け足しました. どのオートマトンHaskell内ではレコードとして保持しています. オートマトンを作成するには, それぞれの構造にあったレコード型を宣言し, 構築する必要があります.

実現した機能
DFA
NFA
ε-NFA

その他

遷移関数と呼ぶぐらいなので遷移関数は関数で実現したかったですが, 入力された文字と現状態の組の場合の数だけ場合分けする面倒な関数になるので, それをすべて入力するぐらいなら最初から表の形で持っておいたほうがシンプルになると思ったからです.
DFAの状態遷移は

基底

\overline{\delta} (q,\epsilon) = q

帰納

\overline{\delta} (q,aw) = \overline{\delta} (\delta (q,a),w)
これを書いてるだけです. NFAやε-NFAもこれがベーシックとなってます.
DFAの最小化, 何書いてあるのかちょっと今見るとわからないです.

以下コードを貼っときます.

続きを読む

オリジナル問題 加藤のお買い物

オリジナル問題です.

問題

加藤さんは10^{100}以下の素数の硬貨2円,3円,5円,7円,...をそれぞれ10^{100}枚持って買い物にきました.
加藤さんがN円の商品をお釣りがないように手持ちで支払うとき, 用いる硬貨の枚数の最小値はいくつでしょうか?

制約

2 \leq N \leq 10^7

解法

前回の三角数の問題に触発されて, この問題を思いつきました.
DPやらなんやらをやるとTLEすると思います.
こんな未解決問題があります.
ゴールドバッハの予想 - Wikipedia
4以上の偶数は2つの奇素数の和で表すことができる, という予想です. しかも未解決問題で, ミレミアム懸賞金もかかっていますが, 4 \times 10^{18}までの偶数においてこの性質が成り立つことは証明されています(http://sweet.ua.pt/tos/goldbach.html). よってその範囲内でこれを用いることができます.
問題に戻ります.
与えられたNについて場合分けします.

N素数であったとき

硬貨は1つのみで済むので1を出力します.

Nが偶数であったとき

上の予想より2つの素数の和でNを表すことができるため, 2を出力します.

N素数でない奇数であったとき

この場合が少しややこしいです. まず, 2,3,4,5,6,7,8までは①,②で尽くされているため, N \geq 9で考えます. また, N素数である場合も①で尽くされているとします.
このとき, 例えば3を支払うと決め打ちすると. N-3は必ず偶数になり, このとき上の予想が成り立つので支払う硬貨の枚数の上界は3であることがわかります.
硬貨2枚で払うときを考えます. 素数でない奇数を2数の和で表すためには, N = (奇数) + (偶数) の組み合わせとなることが必要です. 唯一持っている偶数は2のみであり, このときにN-2素数であれば, 硬貨2枚で支払いが行えます. この条件を満たさないときは3枚の硬貨が必要となります.
以上で尽くされました.

その他

制約が2 \leq N \leq 10^7となっていますが, 計算量を見積もるとO(\sqrt{N})であるため, 2 \leq N \leq 10^{14}かもうちょい高くても大丈夫そうです. そのときは制約から解法が透けそうですが...

ソースコード

#include<cstdio>
#include<queue>
#include<utility>
#include<cstring>
#include<stack>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<map>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
bool isPrime(ll num){
  ll j = (ll)(sqrt(num))+1;
  if(num == 2)
    return true;
  if((num % 2) == 0)
    return false;
  for(int i=3;i<=j;i+=2){
    if(!(num%i)){
      return false;
      
    }
  }
  return true;
}

int main()
{
  ll N;
  cin >> N;
  if(isPrime(N))
    cout << 1 << endl;
  else if(N % 2 == 0)
    cout << 2 << endl;
  else{
    if(isPrime(N-2))
      cout << 2 << endl;
    else
      cout << 3 << endl;
  }
  return 0;
}

yukicoder No.634 硬貨の枚数1

#278149 No.634 硬貨の枚数1 - yukicoder
真っ先にDPを考えるも制約から空間的にも時間的にも不可能でお手上げ.
解説を見る.

任意の自然数は高々三つの三角数の和で表すことができる. より一般には多角数定理というものがあるようです.
多角数定理 - Wikipedia
『高々3つ』であるので, 1つだけや2つだけでもいいことに注意です. 例えば三角数自体が三角数1つで表せます.
これを利用すると, 答えは一気に3か2か1に絞り込めます.
答えが1になるときは, 入力が三角数だったときです.
答えが2になるときは, 入力が2つの三角数の和だったときです.
答えが3になるときは, 入力が3つの三角数の和だったときです.
これらは排反な事象なので, 楽な1,2のときを探索してそれ以外は3を出力することにします.
あらかじめ三角数の配列を計算して持っておきます.
1のときの判別は, 入力された文字が三角数の配列内に入ってるかどうか調べればよいです. 制約から三角数は高々O(\sqrt{N})個であるので, 線形探索しても間に合います. 二分探索してもいいです.
2のときの判別は, 三角数の配列をt[]とし, 各iについて, N-t[i] = t[j]なるjが存在するかを探せばよいです. これも二分探索できます.
1,2でもないときは3を出力して終わりです.
全体の計算量はO(\sqrt{N}\log N)となります. 前処理などいろいろ考えると実質定数ですが...
#278149 No.634 硬貨の枚数1 - yukicoder

yukicoder No.673 カブトムシ

No.673 カブトムシ - yukicoder
とりあえずS年目の元旦のときのカブトムシの数S_nを漸化式で表してみると,

\begin{equation}
S_1   =  B \\
S_{n+1}  =  CS_n + B
\end{equation}
が成り立ちます. これを解くと,

\begin{equation}
S_n   =  nB (C = 1)\\
S_n  =  (B + \frac{B}{C-1})C^{n-1} - \frac{B}{C-1} (otherwise)
\end{equation}
となります. これをあるB,C,nについて,  MOD = 10^9 + 7 で割った余りを求めたい訳ですが, 上の漸化式(特に下の式)を計算してから余りを取るには, とても大きな数になり, 整数型におさまらないことが予想できます. なのでmod 10^9+7上の演算を考えます.
フェルマーの小定理から(C-1)^{-1} mod 10^9+7を繰り返し自乗法で求め, (a^{p-2} \equiv a^{-1} \space mod \space p (pは素数)を利用) , 上の漸化式をMODを取りながら慎重に積を取ります. 上の漸化式は元旦のカブトムシの数なので, それを求めた後でCと積をとると答えです.
#278116 No.673 カブトムシ - yukicoder

yukicoder No.679 不思議マーケット

No.679 不思議マーケット - yukicoder

n-m個の必ず買わせることができる商品を先に買わせ, 条件を満たしているものから貪欲に買わせることで最大値を得ることができます. 条件を満たしている商品は, 買う順番が少し後になっても条件を満たしたままであることがポイントです. 計算量はO(max(r_i)N^2)になりました.
解説をみるとグラフの強連結成分が〜とか書いてあってそのへんがわかるともっと速いコードが書けるっぽいです.

#278108 No.679 不思議マーケット - yukicoder