スポンサーサイト

一定期間更新がないため広告を表示しています

スポンサードリンク | - | | - | - |

フーリエ級数で矩形波

なんてことはない、矩形をフーリエ級数展開してみた。

周期dの関数をフーリエ展開する。

 

0/1の矩形波は

となる。N=±5までの範囲とN=±50までの範囲で比べてみた。

 

#include <iostream>
#include <vector>
#include <cmath>
#include <complex>
const double PI = 3.14159265358979323846;
using namespace std;
int main(void) {

    double d = 1;
    auto a = [&](int n)
    {
        if (n == 0) return 0.5;
        else return 1. / PI / (double)n * sin(n*PI / 2.);
    };

    for (double x = -2; x<2; x += 0.01)
    {
        complex<double> val = 0;
        for (int n = -10; n<=10; n++)
        {
            val += a(n) * exp(2 * PI*n*x / d*complex<double>(0, 1));
        }
        std::cout << x << " " << val.real() << std::endl;

    }

}

ジャジャガッチ | C/C++ | 23:03 | comments(0) | trackbacks(0) |

jwcad 自動作図(2)パラメータ

自動作図の際にパラメータを渡したいことがあるだろう。例えば具体的な寸法など。

どうすればいいのかな、と思ったがバッチファイルで実行するexeファイルでパラメータを入力させればよい。

例えば次のような感じ。

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
    double a=1;
    scanf("%lf",&a);
    if (FILE *fp = fopen("JWC_TEMP.TXT", "w")) {
        fprintf(fp, "0 0 %f 0¥n",a);
        fprintf(fp, "%f 0 %f %f¥n",a,a,a);
        fprintf(fp, "%f %f 0 %f¥n",a,a,a);
        fprintf(fp, "0 %f 0 0¥n",a);
        fclose(fp);
    }
}

ジャジャガッチ | C/C++ | 22:56 | comments(0) | trackbacks(0) |

jwcad 自動作図

2次元cadソフトはjwcadを使っている。

以前から作図の自動化が出来ないかと思っていて、今日ふと少し検討してみようと思い立った。

最初はdxfファイルを直接C++で書き出せないかと考えたのだが、dxfファイルのフォーマットはかなりカオスらしくて断念。

そこでもう少し調べてみるとjwcadで外部変形というワードを発見。

jwcadではこの機能を使って作図の自動化が出来るらしい!

 

というわけでやってみた。

外部変形を実現するためには、ある形式のバッチファイルを実行し、バッチファイル内で図形情報を記録したjwc_temp.txtを書き出すプログラムを実行すればよいらしい。

 

次のような感じ。

@echo off
REM #jww
REM #h0

REM #cd
REM #e
test.exe

 

test.exeのコードは例えば次のような感じ。

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
    if (FILE *fp = fopen("JWC_TEMP.TXT", "w")) {
        fprintf(fp, "0 0 1 0¥n");
        fprintf(fp, "1 0 1 1¥n");
        fprintf(fp, "1 1 0 1¥n");
        fprintf(fp, "0 1 0 0¥n");
        fclose(fp);
    }
}

 

0 0 1 0は座標(0,0)から(1,0)まで線分を描く。

四角形を記述するコマンドはないらしい。

jwc_temp.txtで検索すればコマンド一覧が出てくるのでそれを参照して書けばok。

夢が広がる!

 

ジャジャガッチ | C/C++ | 22:08 | comments(0) | trackbacks(0) |

Qt案外使いやすいかも

ずっと敬遠していたGUIツールキットQt。

敬遠してたのは開発環境やら何やらごてごてしてるから。

もっと気軽にlibファイルだけリンクして使えるシンプルなものが好きなんだが。

でもちょっと使ってみると案外使いやすいかも。

QtCreatorも結構いい感じかも。

 

ちょっとWindows環境でGUIプログラム作る必要が生じていじっている。

QtCreator、ちょっと慣れるのに時間がかかったけど案外Visual Studioより使いやすいかも。

Linuxでも使ってみようかな。

ジャジャガッチ | C/C++ | 22:14 | comments(0) | trackbacks(0) |

codingame

paizaの配信メールでcode warriorsというブラウザゲームを知った。

コーディングしてロボット同士で戦うというもので面白そうなのでやってみた。

が、あんまりコーディングする意味を感じなくて面白くなかった。チュートリアルしかやってないので先に進めば面白いのかもしれないけど。ターン制なのでコマンド選択をコードでやってるだけという感じがしたんだけど。

それで消化不良感があったのでempire of codeというゲームを試してみた。リアルタイムストラテジか?こっちのほうが面白そうな感じはしたが、やはり何か求めてるものとは違う感があってチュートリアルだけでやめてしまった。

 

次にcodingameを試してみた。ミニゲームをクリアしていく感じで面白そう。

というわけでいっこやってみた。画面は下のような感じ。

このゲームの目的は主人公を雷マークへ導くこと。

最初は次のコードが雛形として与えられている。

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 * ---
 * Hint: You can use the debug stream to print initialTX and initialTY, if Thor seems not follow your orders.
 **/
int main()
{
    int lightX; // the X position of the light of power
    int lightY; // the Y position of the light of power
    int initialTX; // Thor's starting X position
    int initialTY; // Thor's starting Y position
    cin >> lightX >> lightY >> initialTX >> initialTY; cin.ignore();

    // game loop
    while (1) {
        int remainingTurns; // The remaining amount of turns Thor can move. Do not remove this line.
        cin >> remainingTurns; cin.ignore();

        // Write an action using cout. DON'T FORGET THE "<< endl"
        // To debug: cerr << "Debug messages..." << endl;


        // A single line providing the move to be made: N NE E SE S SW W or NW
        cout << "SE" << endl;
    }
}

 

coutで移動できる仕様となっている。これを改変して目的を達成するわけだ。

動かすと主人公が実際に移動する様子が見えてうれしい。

やってることは競技プログラミングみたいなもんなんだけど、絵があると断然うれしいな。

次のコードでクリアできた。

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 * ---
 * Hint: You can use the debug stream to print initialTX and initialTY, if Thor seems not follow your orders.
 **/
int main()
{
    int lightX; // the X position of the light of power
    int lightY; // the Y position of the light of power
    int initialTX; // Thor's starting X position
    int initialTY; // Thor's starting Y position
    cin >> lightX >> lightY >> initialTX >> initialTY; cin.ignore();
    
    int tx = initialTX;
    int ty = initialTY;
    // game loop
    while (1) {
        int remainingTurns; // The remaining amount of turns Thor can move. Do not remove this line.
        cin >> remainingTurns; cin.ignore();

        // Write an action using cout. DON'T FORGET THE "<< endl"
        // To debug: cerr << "Debug messages..." << endl;


        // A single line providing the move to be made: N NE E SE S SW W or NW
        //cout << "SE" << endl;
        if(lightY-ty > 0)
        {
            cout << "S";
            ty++;
        }
        else if(lightY!=ty)
        {
            cout <<  "N";
            ty--;
        }
        if(lightX-tx > 0)
        {
            cout << "E" << endl;
            tx++;
        }
        else if(lightX!=tx)
        {
            cout <<  "W" << endl;
            tx--;
        }
        else
        {
            cout << endl;
        }
        
    }
}

ジャジャガッチ | C/C++ | 23:19 | comments(0) | trackbacks(0) |

ABC053 4AC!

競技プログラミングコンテスト3回目。初めて全問解けた!

今回はごりごり実装というよりはじっくり考えることによって非常にシンプルなコードに落とし込めるという感じだった。

それほど新しく得たものはないけど、std::stringの扱い(検索とか)はチェックしといた方がいいなと思った。

 

問題Dをどう解いたか書いとく。

問題文

すぬけくんはカードゲームで遊ぶことにしました。 N 枚からなるカードの山があり、上から i 枚目のカードには整数 Ai が書かれています。

すぬけくんはこのカードの山に対し 0 回以上、以下の操作を行い、残ったカードに書かれた値が互いに異なるようにしたいです。最大で何枚のカードを残すことが可能か求めなさい。なお、N は奇数であり、少なくとも 1 枚のカードを残すことが可能であることが保証されます。

操作:カードの山から任意の 3 枚のカードを抜き出す。抜き出したカードのうち書かれた値が最大であるようなカード 1 枚と最小であるようなカード 1 枚の合計 2 枚を選んで食べる。その後残った 1 枚をカードの山に戻す。

制約

  • 3≦N≦105
  • N は奇数
  • 1≦Ai≦105
  • Ai は整数

最初にソートして数iの枚数niを算出する。

niが3以上の奇数ならそのカードのみ3枚選べば2枚消せる。-2, -2…を繰り返していけるので最終的に1枚に出来る。つまりniが奇数のものは1枚に出来る。

niが偶数のものも-2, -2を繰り返して2枚まで減らせる。2枚にしたら、その2枚と他の数のカード1枚を消して1枚消せる。つまりniが偶数のものが2つあれば両方を奇数に出来るので偶数ペアも1枚に出来る。

最後に偶数枚のカードがペアにならずに残っていたら1枚になっているカードを犠牲にして消さざるを得ない。

まあこういう感じの考え方。

 

ひとつ収穫があった。

数列中に含まれる各数の個数をカウントするときに数列をソートしてやったんだけど、他の人のコードをみたら

count[10001]={0}を用意して数列を走査しながらcount[n]++を繰り返してた。

なるほど、数列に現れる数の上限が小さければこういうことが出来るのか。

業務ではあんまりこういうことはしないよなー。

ジャジャガッチ | C/C++ | 23:21 | comments(0) | trackbacks(0) |

ABC052-C Factors of Factorial

ABC052も参加出来ました!

前回と同じくA, B, Cは出来たけどDは出来なかった。

これが今の実力か。

Cは勉強した剰余計算が大いに役に立った!

問題文

整数 N が与えられます。 N! の正の約数の個数を 109+7 で割った余りを求めてください。

 

次のようにすればOK。

例えば6!なら素因数分解すると2が4個、3が2個、5が1個出て来る。これらを使うか使わないかの組み合わせで5×3×2通りの約数がある。

さて、問題は素因数分解したことがないということだ。

ぐぐってみると、効率は悪いが試し割りという方法がシンプルでよさげ。Nも最大1000とさして大きくないし。

#include <iostream>
#include <vector>
const int MOD = 1000000007;

void countPN(int n, std::vector<int> &count)//nを素因数に分解し、countを更新
{
	int m = n;
	for(int i=2 ; i*i<=n ; ++i)
	{
		while(m%i == 0)
		{
			m /= i;
			count[i]++;
		}
		if(m==1) break;
	}
	if(m!=1) count[m]++;

}

int main()
{
	int N; std::cin >> N;
	std::vector<int> count(1024);
	for(auto &x : count) x = 0;
	for(int n=2; n<=N; n++) countPN(n, count);

	long long ans = 1;
	for(int n=2; n<=N; n++)
	{
		if(count[n] != 0)
		{
			ans *= count[n]+1;
			ans %= MOD;
		}
	}
	std::cout << ans << std::endl;
	return 0;
}

ほれ、剰余計算もばっちしじゃ!

素因数分解とか約数の列挙とか素数の列挙とか抑えとかないかんかな。

ジャジャガッチ | C/C++ | 23:23 | comments(0) | trackbacks(0) |

ABC046-C AtCoDeerくんと選挙速報

それほど難しくはないんだけど細かいところで詰まった。

それは切り上げ処理。

ceil((double)a/b);
a/b + (a%b==0 ? 0 : 1);

最初は前者でサブミットしたんだけど、一部でWAとなる。

誤差が生じないように後者の方法を使えばok。

ジャジャガッチ | C/C++ | 23:11 | comments(0) | trackbacks(0) |

ABC048-C Boxes and Candies

問題文

N 個の箱が横一列に並んでいます。 最初、左から i 番目の箱には ai 個のキャンディが入っています。

すぬけ君は次の操作を好きな回数だけ行うことができます。

  • キャンディが 1 個以上入っている箱をひとつ選び、その箱のキャンディを 1 個食べる。

すぬけ君の目標は次の通りです。

  • どの隣り合う 2 つの箱を見ても、それらの箱に入っているキャンディの個数の総和が x 以下である。

目標を達成するために必要な操作回数の最小値を求めてください。

 

まず、どの箱もx以下になる必要があるので、とりあえずそれをしてしまう。

その後が問題。

真ん中から考えると難しいので端から小問題を順次解く感じでできないかなと考えてみる。

左端二つに注目する。もしこれらの和がxよりも大きいならキャンディを食べる必要があるが、左を食べるよりも右を食べるほうがいい。右を食べておけばその右の箱との和が有利になるから。なので右の箱を食べて条件を満たすようにする。これを繰り返せばok。貪欲法というやつか。

#include <iostream>
#include <vector>

int main()
{
	int N; std::cin >> N;
	int x; std::cin >> x;
	std::vector<int> a(N);
	for(auto &z : a) std::cin >> z;

	long long ans = 0;
	for(auto &z : a)
	{
		if(z > x)
		{
			ans += z-x;
			z -= z-x;
		}
	}
	for(int n=0; n<N-1; n++)//n:端の番号
	{
		int sum = a[n] + a[n+1];
		if(sum > x)
		{
			ans += sum-x;
			a[n+1] -= sum-x;
		}
	}
	std::cout << ans << std::endl;

	return 0;
}

 

ジャジャガッチ | C/C++ | 12:42 | comments(0) | trackbacks(0) |

ABC049-C 白昼夢

これから解いた問題全ての解答を上げるのは面倒くさいので、お、というものだけ上げていきます。

しばらくはABCのC問題を埋めていくか。

アルゴリズムの基礎が問われるレベルらしいし、やってみた感じ今の僕にちょうどいい感じ。

ちょっと考えればそんなに難しくはないけど、どの問題も何かしら経験値が溜まる感じ。

 

問題文

英小文字からなる文字列 S が与えられます。 Tが空文字列である状態から始め、以下の操作を好きな回数繰り返すことで S=T とすることができるか判定してください。

  • T の末尾に dream dreamer erase eraser のいずれかを追加する。

 

前から探索すると、例えばdreamなのかdreamerなのか判別するのが難しいけど、後ろからやれば簡単。後ろからやれば後ろ3文字で判別できる。判別できたら文字列から除いてやればok。

#include <iostream>
#include <string>

int main()
{
	std::string str; std::cin >> str;
	std::string ans("YES");
	while(!str.empty())
	{
		if(str.size() < 5)
		{
			ans = "NO";
			break;
		}
		std::string s = str.substr(str.size()-3);
		if(s=="eam")//dream
		{
			if(str.substr(str.size()-5)=="dream") str.erase(str.size()-5, 5);
			else
			{
				ans = "NO";
				break;
			}
		}
		else if(s=="mer")//dreamer
		{
			if(str.size() < 7)
			{
				ans = "NO";
				break;
			}
			if(str.substr(str.size()-7)=="dreamer") str.erase(str.size()-7, 7);
			else
			{
				ans = "NO";
				break;
			}
		}
		else if(s=="ase")//erase
		{
			if(str.substr(str.size()-5)=="erase") str.erase(str.size()-5, 5);
			else
			{
				ans = "NO";
				break;
			}
		}
		else if(s=="ser")//eraser
		{
			if(str.size() < 6)
			{
				ans = "NO";
				break;
			}
			if(str.substr(str.size()-6)=="eraser") str.erase(str.size()-6, 6);
			else
			{
				ans = "NO";
				break;
			}
		}
		else
		{
			ans = "NO";
			break;
		}
	}
	std::cout << ans << std::endl;
	return 0;
}
前からが難しければ後ろからね。
ジャジャガッチ | C/C++ | 12:37 | comments(0) | trackbacks(0) |
1/15PAGES | >> |

08
--
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
--
>>
<<
--
PR
RECOMMEND
RECENT COMMENT
MOBILE
qrcode
OTHERS
Since 2013/09/17
LATEST ENTRY
CATEGORY
ARCHIVE
LINKS
PROFILE
SEARCH