SP_memo (stackprobe7s_memo) (original) (raw)
分数のクラスとかあったら便利じゃねと考えて、標準にあるだろうと思ったら無かった。
演算子をオーバーライドしたので構造体
分子・分母共に BigInteger を使う。
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Numerics;
namespace Charlotte.Tools { public struct Fraction { public BigInteger Numer; public BigInteger Denom;
public Fraction(BigInteger numer, BigInteger denom)
{
this.Numer = numer;
this.Denom = denom;
}
public static implicit operator Fraction(long value)
{
return new Fraction(value, 1);
}
public static Fraction operator ++(Fraction instance)
{
return instance + new Fraction(1, 1);
}
public static Fraction operator --(Fraction instance)
{
return instance - new Fraction(1, 1);
}
public static Fraction operator +(Fraction a, Fraction b)
{
Reduction(ref a, ref b);
return new Fraction(a.Numer + b.Numer, b.Denom);
}
public static Fraction operator -(Fraction a, Fraction b)
{
Reduction(ref a, ref b);
return new Fraction(a.Numer - b.Numer, b.Denom);
}
public static Fraction operator *(Fraction a, Fraction b)
{
return new Fraction(a.Numer * b.Numer, a.Denom * b.Denom);
}
public static Fraction operator /(Fraction a, Fraction b)
{
return new Fraction(a.Numer * b.Denom, a.Denom * b.Numer);
}
public static bool operator ==(Fraction a, Fraction b)
{
Reduction(ref a, ref b);
return a.Numer == b.Numer;
}
public static bool operator !=(Fraction a, Fraction b)
{
Reduction(ref a, ref b);
return a.Numer != b.Numer;
}
public override bool Equals(object another)
{
return another is Fraction && this == (Fraction)another;
}
public override int GetHashCode()
{
return (this.Numer.GetHashCode() + ":" + this.Denom.GetHashCode()).GetHashCode();
}
public static bool operator <(Fraction a, Fraction b)
{
Reduction(ref a, ref b);
return a.Numer < b.Numer;
}
public static bool operator >(Fraction a, Fraction b)
{
Reduction(ref a, ref b);
return a.Numer > b.Numer;
}
public static bool operator <=(Fraction a, Fraction b)
{
Reduction(ref a, ref b);
return a.Numer <= b.Numer;
}
public static bool operator >=(Fraction a, Fraction b)
{
Reduction(ref a, ref b);
return a.Numer >= b.Numer;
}
public static void Reduction(ref Fraction a, ref Fraction b)
{
BigInteger d = a.Denom * b.Denom;
a.Numer *= b.Denom;
b.Numer *= a.Denom;
a.Denom = d;
b.Denom = d;
}
public void Simplify()
{
if (this.Denom == 0)
throw new Exception("Bad fraction");
if (this.Numer == 0)
{
this.Denom = 1;
return;
}
if (this.Numer < 0)
{
this.Numer *= -1;
this.Denom *= -1;
}
int sign = 1;
if (this.Denom < 0)
{
sign = -1;
this.Denom = BigInteger.Abs(this.Denom);
}
if (this.Numer == this.Denom)
{
this.Numer = sign;
this.Denom = 1;
return;
}
BigInteger d = GetGCD(this.Numer, this.Denom);
this.Numer /= d;
this.Denom /= d;
this.Numer *= sign;
}
private static BigInteger GetGCD(BigInteger a, BigInteger b)
{
if (a < b)
{
BigInteger t = a;
a = b;
b = t;
}
while (b != 0)
{
BigInteger r = a % b;
a = b;
b = r;
}
return a;
}
}}
で、これを使って...
www.youtube.com
...この問題を解いてみる。
source:
public void Test01()
{
const int MURABITO_NUM = 100;
List<Murabito_t> murabitoList = new List<Murabito_t>();
Fraction rem = 1;
for (int n = 1; n <= MURABITO_NUM; n++)
{
Fraction area = rem * new Fraction(n, MURABITO_NUM);
rem -= area;
area.Simplify();
rem.Simplify();
murabitoList.Add(new Murabito_t()
{
No = n,
Area = area,
});
}
murabitoList.Sort((a, b) => a.Area < b.Area ? 1 : (a.Area > b.Area ? -1 : 0));
Console.WriteLine("最も広い土地を貰ったのは " + murabitoList[0].No + " 番目の村人です。");
}
private class Murabito_t
{
public int No;
public Fraction Area;
}output:
最も広い土地を貰ったのは 10 番目の村人です。
それぞれの村人が貰った土地の面積を出力してみる。
source:
public void Test01()
{
const int MURABITO_NUM = 100;
List<Murabito_t> murabitoList = new List<Murabito_t>();
Fraction rem = 1;
for (int n = 1; n <= MURABITO_NUM; n++)
{
Fraction area = rem * new Fraction(n, MURABITO_NUM);
rem -= area;
area.Simplify();
rem.Simplify();
murabitoList.Add(new Murabito_t()
{
No = n,
Area = area,
});
}
murabitoList.Sort((a, b) => a.Area < b.Area ? 1 : (a.Area > b.Area ? -1 : 0));
foreach (Murabito_t x in murabitoList)
Console.WriteLine(string.Join("\t", x.No, x.Area.Numer, x.Area.Denom));
}
private class Murabito_t
{
public int No;
public Fraction Area;
}output:
面積の広い順
各行：村人番号 \t 面積の分子 \t 面積の分母
10 245373636545037 3906250000000000 11 24291990017958663 390625000000000000 9 24267722295663 390625000000000 12 589632848617723911 9765625000000000000 8 117235373409 1953125000000 13 28105832450778173091 488281250000000000000 7 8824167891 156250000000 14 1316650150963377493263 24414062500000000000000 6 80463537 1562500000 15 24263981353467956661561 488281250000000000000000 5 1411641 31250000 16 137495894336318421082179 3051757812500000000000000 17 49086034278065676326337903 1220703125000000000000000000 4 470547 12500000 18 2156898094453827071516141973 61035156250000000000000000000 19 186691512842170143190119399663 6103515625000000000000000000000 3 14553 500000 20 795895396853462189389456388037 30517578125000000000000000000000 21 16713803333922705977178584148777 762939453125000000000000000000000 2 99 5000 22 691633099865658642579437601204153 38146972656250000000000000000000000 23 56399535507226891126705048025465931 3814697265625000000000000000000000000 24 566447508789974428272559395386201307 47683715820312500000000000000000000000 1 1 100 25 3587500889003171379059542837445941611 381469726562500000000000000000000000000 26 139912534671123683783322170660391722829 19073486328125000000000000000000000000000 27 10751740164342504623041449883825487008167 1907348632812500000000000000000000000000000 28 203486637925148883791636329282771254117531 47683715820312500000000000000000000000000000 29 7587144642637694095659583134686185332096513 2384185791015625000000000000000000000000000000 30 55726269271787201461223834747867499163329561 23841857910156250000000000000000000000000000000 31 4030866810659274239028524046762415772814171579 2384185791015625000000000000000000000000000000000 32 8971929352757739435257037394406667365296059321 7450580596923828125000000000000000000000000000000 33 5033252366897091823179197978262140391931089279081 5960464477539062500000000000000000000000000000000000 34 173723468057448108684882015067896300194227596632523 298023223876953125000000000000000000000000000000000000 35 2360595360074736065071043851804943843815680871888989 5960464477539062500000000000000000000000000000000000000 36 39455665304106302801901732951596918532347808858715959 149011611938476562500000000000000000000000000000000000000 37 162206624027992578185596013245453998410763214196943387 931322574615478515625000000000000000000000000000000000000 38 5247603485446138272652930482562390164802258578209222547 46566128730773925781250000000000000000000000000000000000000 39 333913295468651640612494365969364721539259506371313161017 4656612873077392578125000000000000000000000000000000000000000 40 522274641630455130188773239080288410612687945862823149283 11641532182693481445312500000000000000000000000000000000000000 41 64239780920545981013219108406875474505360617341127247361809 2328306436538696289062500000000000000000000000000000000000000000 42 1941294842940401718911670129661432022247361094772113645884911 116415321826934814453125000000000000000000000000000000000000000000 43 115275936626032425880135840556562177702021870722896462686594477 11641532182693481445312500000000000000000000000000000000000000000000 44 1680884006151682116903376093696848498120179370773397258244063653 291038304567337036132812500000000000000000000000000000000000000000000 45 9626881126141452124082972172991041398324663668974911569943273649 2910383045673370361328125000000000000000000000000000000000000000000000 46 270622324990420820821443551085192608197348878694516958577294248133 145519152283668518066406250000000000000000000000000000000000000000000000 47 14931292626645392244452689840309105208801553350580087844982017429599 14551915228366851806640625000000000000000000000000000000000000000000000000 48 50512245268864199295063354991683994217009510271111361007492356836303 90949470177292823791503906250000000000000000000000000000000000000000000000 49 10725433412088831650318452376567568105411686014232645653924210434908337 36379788070917129516601562500000000000000000000000000000000000000000000000000 50 11163206204418988044209001453162162721959101769915610782655810860822963 72759576141834259033203125000000000000000000000000000000000000000000000000000 51 569323516425368390254659074111270298819914190265696149915446353901971113 7275957614183425903320312500000000000000000000000000000000000000000000000000000 52 7110962352214895384161133925664297653887947827436244068551751518344227431 181898940354585647583007812500000000000000000000000000000000000000000000000000000 53 86972539538628335852432330321586409766783361889412523607671422416671704733 4547473508864641189575195312500000000000000000000000000000000000000000000000000000 54 2082417974990931286730879758077229320642416721465367782228962925410497986909 227373675443232059478759765625000000000000000000000000000000000000000000000000000000 55 19513027691581689464552317733094037708241904834471779589034356301068740395851 4547473508864641189575195312500000000000000000000000000000000000000000000000000000000 56 111756431324513312387890547016811306874476364051974737646287676997030058630783 56843418860808014869689941406250000000000000000000000000000000000000000000000000000000 57 10010183205781406695315338997077241344328097180084022929174624782448263823071563 11368683772161602973937988281250000000000000000000000000000000000000000000000000000000000 58 218994709782621300860670661918514385199598897957276782327732580766894473462635773 568434188608080148696899414062500000000000000000000000000000000000000000000000000000000000 59 9356360186919579026426584486794459422838035674795377010484850605868353538627783543 56843418860808014869689941406250000000000000000000000000000000000000000000000000000000000000 60 19505632254086580004245252404673195067950481152539514784570112280030635343240972471 284217094304040074348449707031250000000000000000000000000000000000000000000000000000000000000 61 396614522499760460086320132228354966381659783434970133952925616360622918645899773577 14210854715202003717422485351562500000000000000000000000000000000000000000000000000000000000000 62 7860769798396891741710836719083297612384043904473424458181755248852346043326111905813 710542735760100185871124267578125000000000000000000000000000000000000000000000000000000000000000 63 303527143505841271446060372669119588452377437214667389562695517189556716576172772621231 71054273576010018587112426757812500000000000000000000000000000000000000000000000000000000000000000 64 178261973170097254658797361726308329725999447253058625616186256127199976401879247412469 111022302462515654042363166809082031250000000000000000000000000000000000000000000000000000000000000 65 20856650860901378795079291321978074577941935328607859197093791966882397239019871947258873 35527136788005009293556213378906250000000000000000000000000000000000000000000000000000000000000000000 66 370606642220632192435639715028995017500352850839108882656051226488448750939506955370523051 1776356839400250464677810668945312500000000000000000000000000000000000000000000000000000000000000000000 67 12791544408766668702551322285394706816148542336537727798340677180919488706669649156576538033 177635683940025046467781066894531250000000000000000000000000000000000000000000000000000000000000000000000 68 107105319601762703613899877643379560057601973892502467087598804455161689021517510102081161739 4440892098500626161694526672363281250000000000000000000000000000000000000000000000000000000000000000000000 69 434721591324801561727005385729011155527913894034274719355548088670950384852041658649623538823 55511151231257827021181583404541015625000000000000000000000000000000000000000000000000000000000000000000000 70 1367167903151912157895074908741962619558801666745472668118172974515887442215841158361859535139 555111512312578270211815834045410156250000000000000000000000000000000000000000000000000000000000000000000000 71 41600966195908184233092993651719719709432107859540811187024406224554860741710595247296582997801 55511151231257827021181583404541015625000000000000000000000000000000000000000000000000000000000000000000000000 72 152927495452563888518834807649279533016363100723100728448075634149419981036429089571048002287691 693889390390722837764769792556762695312500000000000000000000000000000000000000000000000000000000000000000000000 73 8682883352917794114791620745420204596817949385500496915218516561150401145512807196756169907667789 138777878078144567552953958511352539062500000000000000000000000000000000000000000000000000000000000000000000000000 74 118824663966642141379134645543490197153714129261849266004154767734099325265305402596704297777535907 6938893903907228377647697925567626953125000000000000000000000000000000000000000000000000000000000000000000000000000 75 125247618775649824696925707464759937540401379492219496598973944368374964468835424358688313873618929 27755575615628913510590791702270507812500000000000000000000000000000000000000000000000000000000000000000000000000000 76 793234918912448889747196147276812937755875403450723478460168314333041441635957687605025987866253217 693889390390722837764769792556762695312500000000000000000000000000000000000000000000000000000000000000000000000000000 77 9644066645725036501663279474786515190610906220900901238120993716364872264100327675619000168268657533 34694469519536141888238489627838134765625000000000000000000000000000000000000000000000000000000000000000000000000000000 78 112347114041757892753142359595889663973740037404520888449279628098432343128545375649743417544636179313 1734723475976807094411924481391906738281250000000000000000000000000000000000000000000000000000000000000000000000000000000 79 2503324156468913046217454115098156871620002371910991078523692226090710414838613626657103329392021533923 173472347597680709441192448139190673828125000000000000000000000000000000000000000000000000000000000000000000000000000000000 80 665440598555027518614766283760269548152152529242162185430348566429176186222922609617711011610537369777 216840434497100886801490560173988342285156250000000000000000000000000000000000000000000000000000000000000000000000000000000 81 53900688482957229007796068984581833400324354868615137019858233880763271084056731379034591940453526951937 86736173798840354720596224069595336914062500000000000000000000000000000000000000000000000000000000000000000000000000000000000 82 518378226274366437000902935049249978010526820279644342450241533248328249067656712892196878044608611056283 4336808689942017736029811203479766845703125000000000000000000000000000000000000000000000000000000000000000000000000000000000000 83 9444598415291505571699377865409505696923500847534007897812937203329297611061940598304172387788356889244961 433680868994201773602981120347976684570312500000000000000000000000000000000000000000000000000000000000000000000000000000000000000 84 40623152219988764928875637324713175106044455452646274933966488934801918640350756549332404125788474812776519 10842021724855044340074528008699417114257812500000000000000000000000000000000000000000000000000000000000000000000000000000000000000 85 32885408939990904942423134977148760800131225842618413041782395804363457946950612444697660482781146277009563 54210108624275221700372640043497085571289062500000000000000000000000000000000000000000000000000000000000000000000000000000000000000 86 249542220779930984563093200708952361365701654923398546022937003456640357362154647374470482486986345278484331 2710505431213761085018632002174854278564453125000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 87 3534214243139022548812180447250046234225867624380225919255084537327766921710515819791919158943597308711557153 271050543121376108501863200217485427856445312500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 88 5809110767458393384829216137433984040164357129728417315557207917676674365570158186554533789987751898227042217 3388131789017201356273290002718567848205566406250000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 89 141002961355581003068127337154079430793080304876135220295797683092697459600657475982732774720611796075147297449 677626357803440271254658000543713569641113281250000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 90 156845990721376621390388835710717569084437642502667267520044613777270207870394271036972412329669301252130139859 6776263578034402712546580005437135696411132812500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 91 1585887239516141394058376005519477642964869496415857927147117761525732101800653184929387724666656268215982525241 677626357803440271254658000543713569641113281250000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 92 3607457786591662291978943221346504088942065777561347152961026116877214781019068233850365483582393928798993216757 16940658945086006781366450013592839241027832031250000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 93 14586677137088025789306161721096733924852700752748055879364149081286129331946667206438434346659245016448103006887 847032947254300339068322500679641962051391601562500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 94 51602330947332908437437926948826080228779984383377531014094677932721898389359715171163923656461200111950816013611 42351647362715016953416125033982098102569580078125000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 95 62581550297829271934765145448576310064690619358564239740497800897130812940287314143751992519538051199599925803741 847032947254300339068322500679641962051391601562500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 96 9881297415446727147594496649775206852319571477668037853762810667968023095834839075329261976769165978884198811117 2646977960169688559588507814623881131410598754882812500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 97 319495283099444177772222058342731688224999477777933223938330878264299413431993130102312803915536366650589094892783 2117582368135750847670806251699104905128479003906250000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 98 484183573356889630232130335838985135763659002405733854834377722730433131695907114691133836861689132965325741744733 105879118406787542383540312584955245256423950195312500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 99 978248444129225987611855168327745478379637576289135747522518256128834286487649068457596935700147431909535682300583 10587911840678754238354031258495524525642395019531250000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 100 9881297415446727147594496649775206852319571477668037853762810667968023095834839075329261976769165978884198811117 10587911840678754238354031258495524525642395019531250000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
グラフにしてみる。
しゃらくせえのでエクセルで、、、
貰った土地の面積(割合) / 村人番号
↑の source:
public void Test01()
{
const int MURABITO_NUM = 100;
List<Murabito_t> murabitoList = new List<Murabito_t>();
Fraction rem = 1;
for (int n = 1; n <= MURABITO_NUM; n++)
{
Fraction area = rem * new Fraction(n, MURABITO_NUM);
rem -= area;
area.Simplify();
rem.Simplify();
murabitoList.Add(new Murabito_t()
{
No = n,
Area = area,
});
}
using (CsvFileWriter writer = new CsvFileWriter(SCommon.NextOutputPath() + ".csv"))
{
foreach (Murabito_t x in murabitoList)
{
const int GAISANCHI_SEIDO = 1000000000;
double gaisanchi = (double)((x.Area.Numer * GAISANCHI_SEIDO) / x.Area.Denom) / GAISANCHI_SEIDO;
writer.WriteCell(x.No.ToString());
writer.WriteCell(gaisanchi.ToString("F9"));
writer.EndRow();
}
}
}
private class Murabito_t
{
public int No;
public Fraction Area;
}数列 int[] arr が与えられるので、n 種類の値を含む最短の範囲を返せ
複数ある場合は arr の先頭に近い方を返すこと。
見つからない場合は null を返すこと。
制約：
1 ≦ arr.Length
1 ≦ n
という問題を愚直に実装するとこうなる……
private Range_t Test01_e1(int[] arr, int n)
{
for (int w = n; w <= arr.Length; w++)
{
for (int s = 0; s + w <= arr.Length; s++)
{
HashSet<int> h = new HashSet<int>();
for (int i = s; i < s + w; i++)
h.Add(arr[i]);
if (n <= h.Count)
return new Range_t() { Start = s, End = s + w };
}
}
return null;
}
private class Range_t
{
<summary>
</summary>
public int Start;
<summary>
</summary>
public int End;
<summary>
</summary>
public int Count
{
get
{
return this.End - this.Start;
}
}
}……のですが、arr の長さが 1,000,000 とかやたら長い場合はスライディングウィンドウで何とかする。
↓こんなん
private Range_t Test01_e2(int[] arr, int n)
{
Dictionary<int, int> d = new Dictionary<int, int>();
Range_t range = null;
int l = 0;
int r = 0;
for (; ; )
{
for (; ; )
{
if (arr.Length <= r)
return range;
int k = arr[r++];
if (d.ContainsKey(k))
d[k]++;
else
d.Add(k, 1);
if (n <= d.Count)
break;
}
for (; ; )
{
int k = arr[l++];
if (--d[k] == 0)
{
d.Remove(k);
break;
}
}
Range_t currRange = new Range_t() { Start = l - 1, End = r };
if (range == null || range.Count > currRange.Count)
range = currRange;
}
}また似たようなやつで、
数列 int[] arr が与えられるので、値が重複しない最長の範囲を返せ
複数ある場合は arr の先頭に近い方を返すこと。
制約：
1 ≦ arr.Length
今度は最短じゃなくて最長。
これを愚直に実装すると、
private Range_t Test02_e1(int[] arr)
{
for (int w = arr.Length; 2 <= w; w--)
{
for (int s = 0; s + w <= arr.Length; s++)
{
HashSet<int> h = new HashSet<int>();
bool dupl = false;
for (int i = s; i < s + w; i++)
{
int k = arr[i];
if (h.Contains(k))
{
dupl = true;
break;
}
h.Add(k);
}
if (!dupl)
return new Range_t() { Start = s, End = s + w };
}
}
return new Range_t() { Start = 0, End = 1 };
}これも長い arr の場合、同様にスライディングウィンドウで何とかする。
↓こんなん
private Range_t Test02_e2(int[] arr)
{
Dictionary<int, int> d = new Dictionary<int, int>();
Range_t range = null;
int l = 0;
int r = -1;
for (; ; )
{
for (; ; )
{
if (arr.Length <= ++r)
break;
int k = arr[r];
if (d.ContainsKey(k))
{
if (++d[k] == 2)
break;
}
else
{
d.Add(k, 1);
}
}
Range_t currRange = new Range_t() { Start = l, End = r };
if (range == null || range.Count < currRange.Count)
range = currRange;
if (arr.Length <= r)
return range;
while (d[arr[l++]]-- != 2) ;
}
}以下検証用
using System; using System.Collections.Generic; using System.Linq; using System.Text; using Charlotte.Commons;
namespace Charlotte.Tests { public class Test0009 { private TimeSpan TotalTm1 = new TimeSpan(0L); private TimeSpan TotalTm2 = new TimeSpan(0L);
public void Test01()
{
for (int c = 0; c < 10000; c++)
{
if (c % 100 == 0) ProcMain.WriteLog(string.Join(" / ", c, TotalTm1, TotalTm2));
Test01_a();
}
ProcMain.WriteLog("OK! (TEST-0009-01)");
}
private void Test01_a()
{
Test01_b(10);
Test01_b(30);
Test01_b(100);
Test01_b(300);
}
private void Test01_b(int arrScale)
{
Test01_c(arrScale, 10);
Test01_c(arrScale, 20);
Test01_c(arrScale, 100);
Test01_c(arrScale, 300);
}
private void Test01_c(int arrScale, int elementKindScale)
{
Test01_d(arrScale, elementKindScale, 10);
Test01_d(arrScale, elementKindScale, 30);
Test01_d(arrScale, elementKindScale, 100);
Test01_d(arrScale, elementKindScale, 300);
}
private void Test01_d(int arrScale, int elementKindScale, int requiredKindScale)
{
int arrLen = SCommon.CRandom.GetRange(1, arrScale);
int elementKind = SCommon.CRandom.GetRange(1, elementKindScale);
int requiredKind = SCommon.CRandom.GetRange(1, requiredKindScale);
int elementMin = SCommon.CRandom.GetRange(-SCommon.IMAX / 2, SCommon.IMAX / 2);
int[] arr = SCommon
.Generate(arrLen, () => elementMin + SCommon.CRandom.GetInt(elementKind))
.ToArray();
DateTime stTm = DateTime.Now;
Range_t ans1 = Test01_e1(arr, requiredKind);
DateTime mdTm = DateTime.Now;
Range_t ans2 = Test01_e2(arr, requiredKind);
DateTime edTm = DateTime.Now;
TimeSpan tm1 = mdTm - stTm;
TimeSpan tm2 = edTm - mdTm;
TotalTm1 += tm1;
TotalTm2 += tm2;
if (ans1 == null)
{
if (ans2 != null)
throw null;
}
else
{
if (
ans2 == null ||
ans1.Start != ans2.Start ||
ans1.End != ans2.End
)
throw null;
}
}
private class Range_t
{
<summary>
</summary>
public int Start;
<summary>
</summary>
public int End;
<summary>
</summary>
public int Count
{
get
{
return this.End - this.Start;
}
}
}
private Range_t Test01_e1(int[] arr, int n)
{
for (int w = n; w <= arr.Length; w++)
{
for (int s = 0; s + w <= arr.Length; s++)
{
HashSet<int> h = new HashSet<int>();
for (int i = s; i < s + w; i++)
h.Add(arr[i]);
if (n <= h.Count)
return new Range_t() { Start = s, End = s + w };
}
}
return null;
}
private Range_t Test01_e2(int[] arr, int n)
{
Dictionary<int, int> d = new Dictionary<int, int>();
Range_t range = null;
int l = 0;
int r = 0;
for (; ; )
{
for (; ; )
{
if (arr.Length <= r)
return range;
int k = arr[r++];
if (d.ContainsKey(k))
d[k]++;
else
d.Add(k, 1);
if (n <= d.Count)
break;
}
for (; ; )
{
int k = arr[l++];
if (--d[k] == 0)
{
d.Remove(k);
break;
}
}
Range_t currRange = new Range_t() { Start = l - 1, End = r };
if (range == null || range.Count > currRange.Count)
range = currRange;
}
}
public void Test02()
{
for (int c = 0; c < 10000; c++)
{
if (c % 100 == 0) ProcMain.WriteLog(string.Join(" / ", c, TotalTm1, TotalTm2));
Test02_a();
}
ProcMain.WriteLog("OK! (TEST-0009-02)");
}
private void Test02_a()
{
Test02_b(10);
Test02_b(30);
Test02_b(100);
Test02_b(300);
}
private void Test02_b(int arrScale)
{
Test02_c(arrScale, 10);
Test02_c(arrScale, 20);
Test02_c(arrScale, 100);
Test02_c(arrScale, 300);
}
private void Test02_c(int arrScale, int elementKindScale)
{
int arrLen = SCommon.CRandom.GetRange(1, arrScale);
int elementKind = SCommon.CRandom.GetRange(1, elementKindScale);
int elementMin = SCommon.CRandom.GetRange(-SCommon.IMAX / 2, SCommon.IMAX / 2);
int[] arr = SCommon
.Generate(arrLen, () => elementMin + SCommon.CRandom.GetInt(elementKind))
.ToArray();
DateTime stTm = DateTime.Now;
Range_t ans1 = Test02_e1(arr);
DateTime mdTm = DateTime.Now;
Range_t ans2 = Test02_e2(arr);
DateTime edTm = DateTime.Now;
TimeSpan tm1 = mdTm - stTm;
TimeSpan tm2 = edTm - mdTm;
TotalTm1 += tm1;
TotalTm2 += tm2;
if (
ans1 == null ||
ans2 == null ||
ans1.Start != ans2.Start ||
ans1.End != ans2.End
)
throw null;
}
private Range_t Test02_e1(int[] arr)
{
for (int w = arr.Length; 2 <= w; w--)
{
for (int s = 0; s + w <= arr.Length; s++)
{
HashSet<int> h = new HashSet<int>();
bool dupl = false;
for (int i = s; i < s + w; i++)
{
int k = arr[i];
if (h.Contains(k))
{
dupl = true;
break;
}
h.Add(k);
}
if (!dupl)
return new Range_t() { Start = s, End = s + w };
}
}
return new Range_t() { Start = 0, End = 1 };
}
private Range_t Test02_e2(int[] arr)
{
Dictionary<int, int> d = new Dictionary<int, int>();
Range_t range = null;
int l = 0;
int r = -1;
for (; ; )
{
for (; ; )
{
if (arr.Length <= ++r)
break;
int k = arr[r];
if (d.ContainsKey(k))
{
if (++d[k] == 2)
break;
}
else
{
d.Add(k, 1);
}
}
Range_t currRange = new Range_t() { Start = l, End = r };
if (range == null || range.Count < currRange.Count)
range = currRange;
if (arr.Length <= r)
return range;
while (d[arr[l++]]-- != 2) ;
}
}
}}
2024.9.24 訂正：ウィンドウスライディング ⇒ スライディングウィンドウ
ほにゃ
using System; using System.Collections.Generic; using System.Linq; using System.Text;
namespace Charlotte.Tests { public class Test0011 { public void Test01() { Test01_a(0.3); Test01_a(0.1); Test01_a(0.03); Test01_a(0.01); Test01_a(0.003); Test01_a(0.001); Test01_a(0.0003); Test01_a(0.0001); Test01_a(0.00003); Test01_a(0.00001); Test01_a(0.000003); Test01_a(0.000001); Test01_a(0.0000003); Test01_a(0.0000001); }
private void Test01_a(double gravity)
{
double s1 = GetFallDownSpeed(gravity);
double s2 = GetFreeFallSpeed(gravity);
Console.WriteLine(string.Format("FD: {0:F9} , FF: {1:F9} , FD / FF: {2:F9} , FDT / FFT: {3:F9} , FDT: {4} , FFT {5}"
, s1
, s2
, s1 / s2
, FDTime * 1.0 / FFTime
, FDTime
, FFTime
));
}
private const double BASE_HI = 100.0;
private int FDTime;
private int FFTime;
private double GetFallDownSpeed(double gravity)
{
const double BAR_LENGTH = BASE_HI;
const double INIT_ROT = 0.0000001;
double rot = INIT_ROT;
double speed = 0.0;
const double 円周の長さ = BAR_LENGTH * 2.0 * Math.PI;
const double 壱周の角度 = Math.PI * 2.0;
for (int t = 0; ; t++)
{
double lastRot = rot;
double lastSpeed = speed;
double kasokudo = gravity * Math.Sin(rot);
speed += kasokudo;
double 移動した角度 = speed * 壱周の角度 / 円周の長さ;
rot += 移動した角度;
if (Math.PI / 2.0 <= rot)
{
FDTime = t;
double secchiSpeed = GetSecchiSpeed(lastRot, rot, Math.PI / 2.0, lastSpeed, speed);
return secchiSpeed;
}
}
}
private double GetFreeFallSpeed(double gravity)
{
const double INIT_HI = BASE_HI;
double hi = INIT_HI;
double speed = 0.0;
for (int t = 0; ; t++)
{
double lastHi = hi;
double lastSpeed = speed;
speed += gravity;
hi -= speed;
if (hi <= 0.0)
{
FFTime = t;
double secchiSpeed = GetSecchiSpeed(lastHi, hi, 0.0, lastSpeed, speed);
return secchiSpeed;
}
}
}
private double GetSecchiSpeed(double lastPos, double currPos, double targetPos, double lastSpeed, double currSpeed)
{
double diffPos = currPos - lastPos;
double diffSpeed = currSpeed - lastSpeed;
double targetDiffPos = targetPos - lastPos;
double targetDiffSpeed = diffSpeed * targetDiffPos / diffPos;
double targetSpeed = lastSpeed + targetDiffSpeed;
return targetSpeed;
}
}}
出力
FD: 7.595323533 , FF: 7.596153846 , FD / FF: 0.999890693 , FDT / FFT: 12.600000000 , FDT: 315 , FFT 25 FD: 4.422122333 , FF: 4.422222222 , FD / FF: 0.999977412 , FDT / FFT: 12.431818182 , FDT: 547 , FFT 44 FD: 2.434470125 , FF: 2.434512195 , FD / FF: 0.999982719 , FDT / FFT: 12.333333333 , FDT: 999 , FFT 81 FD: 1.409212693 , FF: 1.409219858 , FD / FF: 0.999994916 , FDT / FFT: 12.364285714 , FDT: 1731 , FFT 140 FD: 0.773097090 , FF: 0.773096899 , FD / FF: 1.000000247 , FDT / FFT: 12.295719844 , FDT: 3160 , FFT 257 FD: 0.446713434 , FF: 0.446713647 , FD / FF: 0.999999524 , FDT / FFT: 12.275784753 , FDT: 5475 , FFT 446 FD: 0.244798988 , FF: 0.244799020 , FD / FF: 0.999999872 , FDT / FFT: 12.265030675 , FDT: 9996 , FFT 815 FD: 0.141371351 , FF: 0.141371358 , FD / FF: 0.999999954 , FDT / FFT: 12.254069356 , FDT: 17315 , FFT 1413 FD: 0.077444666 , FF: 0.077444667 , FD / FF: 0.999999989 , FDT / FFT: 12.248740798 , FDT: 31614 , FFT 2581 FD: 0.044716360 , FF: 0.044716360 , FD / FF: 1.000000001 , FDT / FFT: 12.247371953 , FDT: 54758 , FFT 4471 FD: 0.024493397 , FF: 0.024493397 , FD / FF: 0.999999999 , FDT / FFT: 12.245712886 , FDT: 99974 , FFT 8164 FD: 0.014141636 , FF: 0.014141636 , FD / FF: 1.000000000 , FDT / FFT: 12.245315041 , FDT: 173161 , FFT 14141 FD: 0.007745817 , FF: 0.007745817 , FD / FF: 1.000000000 , FDT / FFT: 12.244742244 , FDT: 316147 , FFT 25819 FD: 0.004472086 , FF: 0.004472086 , FD / FF: 1.000000000 , FDT / FFT: 12.244722719 , FDT: 547584 , FFT 44720
ふぬん
using System; using System.Collections.Generic; using System.Linq; using System.Text;
namespace Charlotte.Tests { public class Test0012 { public void Test01() {
Test01_a(0.1);
Test01_a(0.2);
Test01_a(0.25);
Test01_a(0.3);
Test01_a(0.333333333);
Test01_a(0.4);
Test01_a(0.5);
Test01_a(0.6);
Test01_a(0.666666666);
Test01_a(0.7);
Test01_a(0.75);
Test01_a(0.8);
Test01_a(0.9);
Test01_a(1.0);
}
private void Test01_a(double barGravCntr)
{
const double DEGREE_TO_RADIAN = Math.PI / 180.0;
Test01_b(barGravCntr, DEGREE_TO_RADIAN * 66.6666666);
Test01_b(barGravCntr, DEGREE_TO_RADIAN * 60.0);
Test01_b(barGravCntr, DEGREE_TO_RADIAN * 50.0);
Test01_b(barGravCntr, DEGREE_TO_RADIAN * 45.0);
Test01_b(barGravCntr, DEGREE_TO_RADIAN * 40.0);
Test01_b(barGravCntr, DEGREE_TO_RADIAN * 33.3333333);
Test01_b(barGravCntr, DEGREE_TO_RADIAN * 30.0);
Test01_b(barGravCntr, DEGREE_TO_RADIAN * 25.758);
Test01_b(barGravCntr, DEGREE_TO_RADIAN * 20.0);
Test01_b(barGravCntr, DEGREE_TO_RADIAN * 10.0);
Test01_b(barGravCntr, DEGREE_TO_RADIAN * 5.0);
Test01_b(barGravCntr, DEGREE_TO_RADIAN * 1.0);
Test01_b(barGravCntr, 0.0000001);
}
private void Test01_b(double barGravCntr, double barInitRot)
{
Test01_c(barGravCntr, barInitRot, 0.0000001);
}
private void Test01_c(double barGravCntr, double barInitRot, double gravity)
{
double s1 = GetFallDownSpeed(gravity, barGravCntr, barInitRot);
double s2 = GetFreeFallSpeed(gravity);
Console.WriteLine(string.Format("FD: {0:F9} , FF: {1:F9} , FD / FF: {2:F9} , FDT / FFT: {3:F9} , FDT: {4} , FFT: {5} , BGC: {6:F3} , BIR: {7:F7} ({8:F3})"
, s1
, s2
, s1 / s2
, FDTime * 1.0 / FFTime
, FDTime
, FFTime
, barGravCntr
, barInitRot
, barInitRot / Math.PI * 180.0
));
}
private const double BASE_HI = 300.0;
private int FDTime;
private int FFTime;
private double GetFallDownSpeed(double gravity, double barGravCntr, double barInitRot)
{
const double BAR_LENGTH = BASE_HI;
double 重りまでの長さ = BAR_LENGTH * barGravCntr;
double rot = barInitRot;
double speed = 0.0;
double 円周の長さ = 重りまでの長さ * 2.0 * Math.PI;
double 壱周の角度 = Math.PI * 2.0;
for (int t = 0; ; t++)
{
double lastRot = rot;
double lastSpeed = speed;
double kasokudo = gravity * Math.Sin(rot);
speed += kasokudo;
double 移動した角度 = speed * 壱周の角度 / 円周の長さ;
rot += 移動した角度;
if (Math.PI / 2.0 <= rot)
{
FDTime = t;
double secchiSpeed = GetSecchiSpeed(lastRot, rot, Math.PI / 2.0, lastSpeed, speed);
secchiSpeed /= barGravCntr;
return secchiSpeed;
}
}
}
private double GetFreeFallSpeed(double gravity)
{
const double INIT_HI = BASE_HI;
double hi = INIT_HI;
double speed = 0.0;
for (int t = 0; ; t++)
{
double lastHi = hi;
double lastSpeed = speed;
speed += gravity;
hi -= speed;
if (hi <= 0.0)
{
FFTime = t;
double secchiSpeed = GetSecchiSpeed(lastHi, hi, 0.0, lastSpeed, speed);
return secchiSpeed;
}
}
}
private double GetSecchiSpeed(double lastPos, double currPos, double targetPos, double lastSpeed, double currSpeed)
{
double diffPos = currPos - lastPos;
double diffSpeed = currSpeed - lastSpeed;
double targetDiffPos = targetPos - lastPos;
double targetDiffSpeed = diffSpeed * targetDiffPos / diffPos;
double targetSpeed = lastSpeed + targetDiffSpeed;
return targetSpeed;
}
}}
出力
FD: 0.015415331 , FF: 0.007745917 , FD / FF: 1.990123583 , FDT / FFT: 0.208174647 , FDT: 16125 , FFT: 77459 , BGC: 0.100 , BIR: 1.1635528 (66.667) FD: 0.017320008 , FF: 0.007745917 , FD / FF: 2.236017861 , FDT / FFT: 0.241095289 , FDT: 18675 , FFT: 77459 , BGC: 0.100 , BIR: 1.0471976 (60.000) FD: 0.019638048 , FF: 0.007745917 , FD / FF: 2.535277454 , FDT / FFT: 0.290876464 , FDT: 22531 , FFT: 77459 , BGC: 0.100 , BIR: 0.8726646 (50.000) FD: 0.020597171 , FF: 0.007745917 , FD / FF: 2.659100563 , FDT / FFT: 0.317354988 , FDT: 24582 , FFT: 77459 , BGC: 0.100 , BIR: 0.7853982 (45.000) FD: 0.021438405 , FF: 0.007745917 , FD / FF: 2.767704105 , FDT / FFT: 0.345834571 , FDT: 26788 , FFT: 77459 , BGC: 0.100 , BIR: 0.6981317 (40.000) FD: 0.022389066 , FF: 0.007745917 , FD / FF: 2.890434711 , FDT / FFT: 0.388476484 , FDT: 30091 , FFT: 77459 , BGC: 0.100 , BIR: 0.5817764 (33.333) FD: 0.022794571 , FF: 0.007745917 , FD / FF: 2.942785402 , FDT / FFT: 0.412631198 , FDT: 31962 , FFT: 77459 , BGC: 0.100 , BIR: 0.5235988 (30.000) FD: 0.023245630 , FF: 0.007745917 , FD / FF: 3.001017251 , FDT / FFT: 0.447204327 , FDT: 34640 , FFT: 77459 , BGC: 0.100 , BIR: 0.4495619 (25.758) FD: 0.023744301 , FF: 0.007745917 , FD / FF: 3.065395859 , FDT / FFT: 0.504034392 , FDT: 39042 , FFT: 77459 , BGC: 0.100 , BIR: 0.3490659 (20.000) FD: 0.024307619 , FF: 0.007745917 , FD / FF: 3.138120382 , FDT / FFT: 0.658735589 , FDT: 51025 , FFT: 77459 , BGC: 0.100 , BIR: 0.1745329 (10.000) FD: 0.024447748 , FF: 0.007745917 , FD / FF: 3.156211038 , FDT / FFT: 0.813423876 , FDT: 63007 , FFT: 77459 , BGC: 0.100 , BIR: 0.0872665 (5.000) FD: 0.024492532 , FF: 0.007745917 , FD / FF: 3.161992697 , FDT / FFT: 1.173123846 , FDT: 90869 , FFT: 77459 , BGC: 0.100 , BIR: 0.0174533 (1.000) FD: 0.024494397 , FF: 0.007745917 , FD / FF: 3.162233522 , FDT / FFT: 3.872035528 , FDT: 299924 , FFT: 77459 , BGC: 0.100 , BIR: 0.0000001 (0.000) FD: 0.010900389 , FF: 0.007745917 , FD / FF: 1.407243250 , FDT / FFT: 0.294400909 , FDT: 22804 , FFT: 77459 , BGC: 0.200 , BIR: 1.1635528 (66.667) FD: 0.012247199 , FF: 0.007745917 , FD / FF: 1.581116761 , FDT / FFT: 0.340967480 , FDT: 26411 , FFT: 77459 , BGC: 0.200 , BIR: 1.0471976 (60.000) FD: 0.013886300 , FF: 0.007745917 , FD / FF: 1.792725249 , FDT / FFT: 0.411366013 , FDT: 31864 , FFT: 77459 , BGC: 0.200 , BIR: 0.8726646 (50.000) FD: 0.014564503 , FF: 0.007745917 , FD / FF: 1.880281409 , FDT / FFT: 0.448818084 , FDT: 34765 , FFT: 77459 , BGC: 0.200 , BIR: 0.7853982 (45.000) FD: 0.015159345 , FF: 0.007745917 , FD / FF: 1.957075710 , FDT / FFT: 0.489084548 , FDT: 37884 , FFT: 77459 , BGC: 0.200 , BIR: 0.6981317 (40.000) FD: 0.015831564 , FF: 0.007745917 , FD / FF: 2.043859354 , FDT / FFT: 0.549387418 , FDT: 42555 , FFT: 77459 , BGC: 0.200 , BIR: 0.5817764 (33.333) FD: 0.016118299 , FF: 0.007745917 , FD / FF: 2.080876882 , FDT / FFT: 0.583547425 , FDT: 45201 , FFT: 77459 , BGC: 0.200 , BIR: 0.5235988 (30.000) FD: 0.016437246 , FF: 0.007745917 , FD / FF: 2.122053018 , FDT / FFT: 0.632450716 , FDT: 48989 , FFT: 77459 , BGC: 0.200 , BIR: 0.4495619 (25.758) FD: 0.016789860 , FF: 0.007745917 , FD / FF: 2.167575568 , FDT / FFT: 0.712815812 , FDT: 55214 , FFT: 77459 , BGC: 0.200 , BIR: 0.3490659 (20.000) FD: 0.017188186 , FF: 0.007745917 , FD / FF: 2.218999571 , FDT / FFT: 0.931589615 , FDT: 72160 , FFT: 77459 , BGC: 0.200 , BIR: 0.1745329 (10.000) FD: 0.017287272 , FF: 0.007745917 , FD / FF: 2.231791597 , FDT / FFT: 1.150350508 , FDT: 89105 , FFT: 77459 , BGC: 0.200 , BIR: 0.0872665 (5.000) FD: 0.017318939 , FF: 0.007745917 , FD / FF: 2.235879847 , FDT / FFT: 1.659045430 , FDT: 128508 , FFT: 77459 , BGC: 0.200 , BIR: 0.0174533 (1.000) FD: 0.017320258 , FF: 0.007745917 , FD / FF: 2.236050136 , FDT / FFT: 5.475890471 , FDT: 424157 , FFT: 77459 , BGC: 0.200 , BIR: 0.0000001 (0.000) FD: 0.009749628 , FF: 0.007745917 , FD / FF: 1.258679674 , FDT / FFT: 0.329154779 , FDT: 25496 , FFT: 77459 , BGC: 0.250 , BIR: 1.1635528 (66.667) FD: 0.010954251 , FF: 0.007745917 , FD / FF: 1.414196871 , FDT / FFT: 0.381208123 , FDT: 29528 , FFT: 77459 , BGC: 0.250 , BIR: 1.0471976 (60.000) FD: 0.012420308 , FF: 0.007745917 , FD / FF: 1.603465256 , FDT / FFT: 0.459920732 , FDT: 35625 , FFT: 77459 , BGC: 0.250 , BIR: 0.8726646 (50.000) FD: 0.013026911 , FF: 0.007745917 , FD / FF: 1.681777866 , FDT / FFT: 0.501800953 , FDT: 38869 , FFT: 77459 , BGC: 0.250 , BIR: 0.7853982 (45.000) FD: 0.013558954 , FF: 0.007745917 , FD / FF: 1.750464777 , FDT / FFT: 0.546818317 , FDT: 42356 , FFT: 77459 , BGC: 0.250 , BIR: 0.6981317 (40.000) FD: 0.014160205 , FF: 0.007745917 , FD / FF: 1.828086428 , FDT / FFT: 0.614247537 , FDT: 47579 , FFT: 77459 , BGC: 0.250 , BIR: 0.5817764 (33.333) FD: 0.014416668 , FF: 0.007745917 , FD / FF: 1.861195912 , FDT / FFT: 0.652435482 , FDT: 50537 , FFT: 77459 , BGC: 0.250 , BIR: 0.5235988 (30.000) FD: 0.014701943 , FF: 0.007745917 , FD / FF: 1.898024967 , FDT / FFT: 0.707096658 , FDT: 54771 , FFT: 77459 , BGC: 0.250 , BIR: 0.4495619 (25.758) FD: 0.015017331 , FF: 0.007745917 , FD / FF: 1.938741574 , FDT / FFT: 0.796950645 , FDT: 61731 , FFT: 77459 , BGC: 0.250 , BIR: 0.3490659 (20.000) FD: 0.015373604 , FF: 0.007745917 , FD / FF: 1.984736601 , FDT / FFT: 1.041557469 , FDT: 80678 , FFT: 77459 , BGC: 0.250 , BIR: 0.1745329 (10.000) FD: 0.015462230 , FF: 0.007745917 , FD / FF: 1.996178136 , FDT / FFT: 1.286138473 , FDT: 99623 , FFT: 77459 , BGC: 0.250 , BIR: 0.0872665 (5.000) FD: 0.015490554 , FF: 0.007745917 , FD / FF: 1.999834778 , FDT / FFT: 1.854878065 , FDT: 143677 , FFT: 77459 , BGC: 0.250 , BIR: 0.0174533 (1.000) FD: 0.015491733 , FF: 0.007745917 , FD / FF: 1.999987090 , FDT / FFT: 6.122232407 , FDT: 474222 , FFT: 77459 , BGC: 0.250 , BIR: 0.0000001 (0.000) FD: 0.008900168 , FF: 0.007745917 , FD / FF: 1.149014138 , FDT / FFT: 0.360577854 , FDT: 27930 , FFT: 77459 , BGC: 0.300 , BIR: 1.1635528 (66.667) FD: 0.009999833 , FF: 0.007745917 , FD / FF: 1.290981265 , FDT / FFT: 0.417601570 , FDT: 32347 , FFT: 77459 , BGC: 0.300 , BIR: 1.0471976 (60.000) FD: 0.011338154 , FF: 0.007745917 , FD / FF: 1.463758872 , FDT / FFT: 0.503814921 , FDT: 39025 , FFT: 77459 , BGC: 0.300 , BIR: 0.8726646 (50.000) FD: 0.011891904 , FF: 0.007745917 , FD / FF: 1.535248177 , FDT / FFT: 0.549697259 , FDT: 42579 , FFT: 77459 , BGC: 0.300 , BIR: 0.7853982 (45.000) FD: 0.012377591 , FF: 0.007745917 , FD / FF: 1.597950461 , FDT / FFT: 0.599013672 , FDT: 46399 , FFT: 77459 , BGC: 0.300 , BIR: 0.6981317 (40.000) FD: 0.012926456 , FF: 0.007745917 , FD / FF: 1.668809010 , FDT / FFT: 0.672872100 , FDT: 52120 , FFT: 77459 , BGC: 0.300 , BIR: 0.5817764 (33.333) FD: 0.013160573 , FF: 0.007745917 , FD / FF: 1.699033695 , FDT / FFT: 0.714700680 , FDT: 55360 , FFT: 77459 , BGC: 0.300 , BIR: 0.5235988 (30.000) FD: 0.013420993 , FF: 0.007745917 , FD / FF: 1.732653869 , FDT / FFT: 0.774590428 , FDT: 59999 , FFT: 77459 , BGC: 0.300 , BIR: 0.4495619 (25.758) FD: 0.013708901 , FF: 0.007745917 , FD / FF: 1.769822876 , FDT / FFT: 0.873029603 , FDT: 67624 , FFT: 77459 , BGC: 0.300 , BIR: 0.3490659 (20.000) FD: 0.014034132 , FF: 0.007745917 , FD / FF: 1.811810399 , FDT / FFT: 1.140964898 , FDT: 88378 , FFT: 77459 , BGC: 0.300 , BIR: 0.1745329 (10.000) FD: 0.014115036 , FF: 0.007745917 , FD / FF: 1.822255044 , FDT / FFT: 1.408900192 , FDT: 109132 , FFT: 77459 , BGC: 0.300 , BIR: 0.0872665 (5.000) FD: 0.014140892 , FF: 0.007745917 , FD / FF: 1.825593086 , FDT / FFT: 2.031913658 , FDT: 157390 , FFT: 77459 , BGC: 0.300 , BIR: 0.0174533 (1.000) FD: 0.014141969 , FF: 0.007745917 , FD / FF: 1.825732127 , FDT / FFT: 6.706567345 , FDT: 519484 , FFT: 77459 , BGC: 0.300 , BIR: 0.0000001 (0.000) FD: 0.008443449 , FF: 0.007745917 , FD / FF: 1.090051570 , FDT / FFT: 0.380084948 , FDT: 29441 , FFT: 77459 , BGC: 0.333 , BIR: 1.1635528 (66.667) FD: 0.009486683 , FF: 0.007745917 , FD / FF: 1.224733413 , FDT / FFT: 0.440194167 , FDT: 34097 , FFT: 77459 , BGC: 0.333 , BIR: 1.0471976 (60.000) FD: 0.010756326 , FF: 0.007745917 , FD / FF: 1.388644643 , FDT / FFT: 0.531080959 , FDT: 41137 , FFT: 77459 , BGC: 0.333 , BIR: 0.8726646 (50.000) FD: 0.011281659 , FF: 0.007745917 , FD / FF: 1.456465352 , FDT / FFT: 0.579429117 , FDT: 44882 , FFT: 77459 , BGC: 0.333 , BIR: 0.7853982 (45.000) FD: 0.011742422 , FF: 0.007745917 , FD / FF: 1.515949962 , FDT / FFT: 0.631417911 , FDT: 48909 , FFT: 77459 , BGC: 0.333 , BIR: 0.6981317 (40.000) FD: 0.012263121 , FF: 0.007745917 , FD / FF: 1.583172284 , FDT / FFT: 0.709265547 , FDT: 54939 , FFT: 77459 , BGC: 0.333 , BIR: 0.5817764 (33.333) FD: 0.012485224 , FF: 0.007745917 , FD / FF: 1.611845938 , FDT / FFT: 0.753366297 , FDT: 58355 , FFT: 77459 , BGC: 0.333 , BIR: 0.5235988 (30.000) FD: 0.012732280 , FF: 0.007745917 , FD / FF: 1.643740835 , FDT / FFT: 0.816483559 , FDT: 63244 , FFT: 77459 , BGC: 0.333 , BIR: 0.4495619 (25.758) FD: 0.013005413 , FF: 0.007745917 , FD / FF: 1.679002451 , FDT / FFT: 0.920254586 , FDT: 71282 , FFT: 77459 , BGC: 0.333 , BIR: 0.3490659 (20.000) FD: 0.013313955 , FF: 0.007745917 , FD / FF: 1.718835313 , FDT / FFT: 1.202687874 , FDT: 93159 , FFT: 77459 , BGC: 0.333 , BIR: 0.1745329 (10.000) FD: 0.013390707 , FF: 0.007745917 , FD / FF: 1.728743973 , FDT / FFT: 1.485108251 , FDT: 115035 , FFT: 77459 , BGC: 0.333 , BIR: 0.0872665 (5.000) FD: 0.013415236 , FF: 0.007745917 , FD / FF: 1.731910718 , FDT / FFT: 2.141829871 , FDT: 165904 , FFT: 77459 , BGC: 0.333 , BIR: 0.0174533 (1.000) FD: 0.013416258 , FF: 0.007745917 , FD / FF: 1.732042624 , FDT / FFT: 7.069339909 , FDT: 547584 , FFT: 77459 , BGC: 0.333 , BIR: 0.0000001 (0.000) FD: 0.007707791 , FF: 0.007745917 , FD / FF: 0.995077929 , FDT / FFT: 0.416362205 , FDT: 32251 , FFT: 77459 , BGC: 0.400 , BIR: 1.1635528 (66.667) FD: 0.008660129 , FF: 0.007745917 , FD / FF: 1.118025068 , FDT / FFT: 0.482203488 , FDT: 37351 , FFT: 77459 , BGC: 0.400 , BIR: 1.0471976 (60.000) FD: 0.009819149 , FF: 0.007745917 , FD / FF: 1.267654865 , FDT / FFT: 0.581765837 , FDT: 45063 , FFT: 77459 , BGC: 0.400 , BIR: 0.8726646 (50.000) FD: 0.010298711 , FF: 0.007745917 , FD / FF: 1.329566419 , FDT / FFT: 0.634735796 , FDT: 49166 , FFT: 77459 , BGC: 0.400 , BIR: 0.7853982 (45.000) FD: 0.010719328 , FF: 0.007745917 , FD / FF: 1.383868190 , FDT / FFT: 0.691682051 , FDT: 53577 , FFT: 77459 , BGC: 0.400 , BIR: 0.6981317 (40.000) FD: 0.011194658 , FF: 0.007745917 , FD / FF: 1.445233493 , FDT / FFT: 0.776965879 , FDT: 60183 , FFT: 77459 , BGC: 0.400 , BIR: 0.5817764 (33.333) FD: 0.011397410 , FF: 0.007745917 , FD / FF: 1.471408839 , FDT / FFT: 0.825275307 , FDT: 63925 , FFT: 77459 , BGC: 0.400 , BIR: 0.5235988 (30.000) FD: 0.011622940 , FF: 0.007745917 , FD / FF: 1.500524763 , FDT / FFT: 0.894421565 , FDT: 69281 , FFT: 77459 , BGC: 0.400 , BIR: 0.4495619 (25.758) FD: 0.011872275 , FF: 0.007745917 , FD / FF: 1.532714067 , FDT / FFT: 1.008081695 , FDT: 78085 , FFT: 77459 , BGC: 0.400 , BIR: 0.3490659 (20.000) FD: 0.012153935 , FF: 0.007745917 , FD / FF: 1.569076329 , FDT / FFT: 1.317484088 , FDT: 102051 , FFT: 77459 , BGC: 0.400 , BIR: 0.1745329 (10.000) FD: 0.012223999 , FF: 0.007745917 , FD / FF: 1.578121657 , FDT / FFT: 1.626860662 , FDT: 126015 , FFT: 77459 , BGC: 0.400 , BIR: 0.0872665 (5.000) FD: 0.012246391 , FF: 0.007745917 , FD / FF: 1.581012486 , FDT / FFT: 2.346247692 , FDT: 181738 , FFT: 77459 , BGC: 0.400 , BIR: 0.0174533 (1.000) FD: 0.012247324 , FF: 0.007745917 , FD / FF: 1.581132899 , FDT / FFT: 7.744083967 , FDT: 599849 , FFT: 77459 , BGC: 0.400 , BIR: 0.0000001 (0.000) FD: 0.006894069 , FF: 0.007745917 , FD / FF: 0.890026281 , FDT / FFT: 0.465497876 , FDT: 36057 , FFT: 77459 , BGC: 0.500 , BIR: 1.1635528 (66.667) FD: 0.007745867 , FF: 0.007745917 , FD / FF: 0.999993545 , FDT / FFT: 0.539123924 , FDT: 41760 , FFT: 77459 , BGC: 0.500 , BIR: 1.0471976 (60.000) FD: 0.008782526 , FF: 0.007745917 , FD / FF: 1.133826504 , FDT / FFT: 0.650434423 , FDT: 50382 , FFT: 77459 , BGC: 0.500 , BIR: 0.8726646 (50.000) FD: 0.009211459 , FF: 0.007745917 , FD / FF: 1.189201881 , FDT / FFT: 0.709652849 , FDT: 54969 , FFT: 77459 , BGC: 0.500 , BIR: 0.7853982 (45.000) FD: 0.009587670 , FF: 0.007745917 , FD / FF: 1.237770862 , FDT / FFT: 0.773325243 , FDT: 59901 , FFT: 77459 , BGC: 0.500 , BIR: 0.6981317 (40.000) FD: 0.010012819 , FF: 0.007745917 , FD / FF: 1.292657657 , FDT / FFT: 0.868678914 , FDT: 67287 , FFT: 77459 , BGC: 0.500 , BIR: 0.5817764 (33.333) FD: 0.010194165 , FF: 0.007745917 , FD / FF: 1.316069598 , FDT / FFT: 0.922681677 , FDT: 71470 , FFT: 77459 , BGC: 0.500 , BIR: 0.5235988 (30.000) FD: 0.010395885 , FF: 0.007745917 , FD / FF: 1.342111673 , FDT / FFT: 0.999987090 , FDT: 77458 , FFT: 77459 , BGC: 0.500 , BIR: 0.4495619 (25.758) FD: 0.010618898 , FF: 0.007745917 , FD / FF: 1.370902662 , FDT / FFT: 1.127073678 , FDT: 87302 , FFT: 77459 , BGC: 0.500 , BIR: 0.3490659 (20.000) FD: 0.010870821 , FF: 0.007745917 , FD / FF: 1.403426057 , FDT / FFT: 1.472985709 , FDT: 114096 , FFT: 77459 , BGC: 0.500 , BIR: 0.1745329 (10.000) FD: 0.010933489 , FF: 0.007745917 , FD / FF: 1.411516444 , FDT / FFT: 1.818884829 , FDT: 140889 , FFT: 77459 , BGC: 0.500 , BIR: 0.0872665 (5.000) FD: 0.010953517 , FF: 0.007745917 , FD / FF: 1.414102080 , FDT / FFT: 2.623194206 , FDT: 203190 , FFT: 77459 , BGC: 0.500 , BIR: 0.0174533 (1.000) FD: 0.010954351 , FF: 0.007745917 , FD / FF: 1.414209781 , FDT / FFT: 8.658141727 , FDT: 670651 , FFT: 77459 , BGC: 0.500 , BIR: 0.0000001 (0.000) FD: 0.006293404 , FF: 0.007745917 , FD / FF: 0.812480145 , FDT / FFT: 0.509934288 , FDT: 39499 , FFT: 77459 , BGC: 0.600 , BIR: 1.1635528 (66.667) FD: 0.007070984 , FF: 0.007745917 , FD / FF: 0.912866063 , FDT / FFT: 0.590583405 , FDT: 45746 , FFT: 77459 , BGC: 0.600 , BIR: 1.0471976 (60.000) FD: 0.008017320 , FF: 0.007745917 , FD / FF: 1.035038281 , FDT / FFT: 0.712518881 , FDT: 55191 , FFT: 77459 , BGC: 0.600 , BIR: 0.8726646 (50.000) FD: 0.008408881 , FF: 0.007745917 , FD / FF: 1.085588853 , FDT / FFT: 0.777391911 , FDT: 60216 , FFT: 77459 , BGC: 0.600 , BIR: 0.7853982 (45.000) FD: 0.008752313 , FF: 0.007745917 , FD / FF: 1.129926063 , FDT / FFT: 0.847132031 , FDT: 65618 , FFT: 77459 , BGC: 0.600 , BIR: 0.6981317 (40.000) FD: 0.009140419 , FF: 0.007745917 , FD / FF: 1.180030624 , FDT / FFT: 0.951587291 , FDT: 73709 , FFT: 77459 , BGC: 0.600 , BIR: 0.5817764 (33.333) FD: 0.009305965 , FF: 0.007745917 , FD / FF: 1.201402704 , FDT / FFT: 1.010754076 , FDT: 78292 , FFT: 77459 , BGC: 0.600 , BIR: 0.5235988 (30.000) FD: 0.009490109 , FF: 0.007745917 , FD / FF: 1.225175757 , FDT / FFT: 1.095431131 , FDT: 84851 , FFT: 77459 , BGC: 0.600 , BIR: 0.4495619 (25.758) FD: 0.009693691 , FF: 0.007745917 , FD / FF: 1.251458213 , FDT / FFT: 1.234653171 , FDT: 95635 , FFT: 77459 , BGC: 0.600 , BIR: 0.3490659 (20.000) FD: 0.009923665 , FF: 0.007745917 , FD / FF: 1.281147875 , FDT / FFT: 1.613576215 , FDT: 124986 , FFT: 77459 , BGC: 0.600 , BIR: 0.1745329 (10.000) FD: 0.009980872 , FF: 0.007745917 , FD / FF: 1.288533355 , FDT / FFT: 1.992486348 , FDT: 154336 , FFT: 77459 , BGC: 0.600 , BIR: 0.0872665 (5.000) FD: 0.009999155 , FF: 0.007745917 , FD / FF: 1.290893707 , FDT / FFT: 2.873558915 , FDT: 222583 , FFT: 77459 , BGC: 0.600 , BIR: 0.0174533 (1.000) FD: 0.009999917 , FF: 0.007745917 , FD / FF: 1.290992024 , FDT / FFT: 9.484527298 , FDT: 734662 , FFT: 77459 , BGC: 0.600 , BIR: 0.0000001 (0.000) FD: 0.005970451 , FF: 0.007745917 , FD / FF: 0.770786867 , FDT / FFT: 0.537523077 , FDT: 41636 , FFT: 77459 , BGC: 0.667 , BIR: 1.1635528 (66.667) FD: 0.006708129 , FF: 0.007745917 , FD / FF: 0.866021312 , FDT / FFT: 0.622522883 , FDT: 48220 , FFT: 77459 , BGC: 0.667 , BIR: 1.0471976 (60.000) FD: 0.007605902 , FF: 0.007745917 , FD / FF: 0.981924054 , FDT / FFT: 0.751055397 , FDT: 58176 , FFT: 77459 , BGC: 0.667 , BIR: 0.8726646 (50.000) FD: 0.007977369 , FF: 0.007745917 , FD / FF: 1.029880538 , FDT / FFT: 0.819439962 , FDT: 63473 , FFT: 77459 , BGC: 0.667 , BIR: 0.7853982 (45.000) FD: 0.008303177 , FF: 0.007745917 , FD / FF: 1.071942509 , FDT / FFT: 0.892962729 , FDT: 69168 , FFT: 77459 , BGC: 0.667 , BIR: 0.6981317 (40.000) FD: 0.008671367 , FF: 0.007745917 , FD / FF: 1.119475868 , FDT / FFT: 1.003059683 , FDT: 77696 , FFT: 77459 , BGC: 0.667 , BIR: 0.5817764 (33.333) FD: 0.008828418 , FF: 0.007745917 , FD / FF: 1.139751204 , FDT / FFT: 1.065428162 , FDT: 82527 , FFT: 77459 , BGC: 0.667 , BIR: 0.5235988 (30.000) FD: 0.009003112 , FF: 0.007745917 , FD / FF: 1.162304302 , FDT / FFT: 1.154688287 , FDT: 89441 , FFT: 77459 , BGC: 0.667 , BIR: 0.4495619 (25.758) FD: 0.009196247 , FF: 0.007745917 , FD / FF: 1.187238030 , FDT / FFT: 1.301436889 , FDT: 100808 , FFT: 77459 , BGC: 0.667 , BIR: 0.3490659 (20.000) FD: 0.009414419 , FF: 0.007745917 , FD / FF: 1.215404116 , FDT / FFT: 1.700861101 , FDT: 131747 , FFT: 77459 , BGC: 0.667 , BIR: 0.1745329 (10.000) FD: 0.009468691 , FF: 0.007745917 , FD / FF: 1.222410597 , FDT / FFT: 2.100259492 , FDT: 162684 , FFT: 77459 , BGC: 0.667 , BIR: 0.0872665 (5.000) FD: 0.009486036 , FF: 0.007745917 , FD / FF: 1.224649824 , FDT / FFT: 3.028995985 , FDT: 234623 , FFT: 77459 , BGC: 0.667 , BIR: 0.0174533 (1.000) FD: 0.009486758 , FF: 0.007745917 , FD / FF: 1.224743095 , FDT / FFT: 9.997559999 , FDT: 774401 , FFT: 77459 , BGC: 0.667 , BIR: 0.0000001 (0.000) FD: 0.005826565 , FF: 0.007745917 , FD / FF: 0.752211187 , FDT / FFT: 0.550794614 , FDT: 42664 , FFT: 77459 , BGC: 0.700 , BIR: 1.1635528 (66.667) FD: 0.006546465 , FF: 0.007745917 , FD / FF: 0.845150489 , FDT / FFT: 0.637898759 , FDT: 49411 , FFT: 77459 , BGC: 0.700 , BIR: 1.0471976 (60.000) FD: 0.007422602 , FF: 0.007745917 , FD / FF: 0.958259983 , FDT / FFT: 0.769607147 , FDT: 59613 , FFT: 77459 , BGC: 0.700 , BIR: 0.8726646 (50.000) FD: 0.007785117 , FF: 0.007745917 , FD / FF: 1.005060719 , FDT / FFT: 0.839670019 , FDT: 65040 , FFT: 77459 , BGC: 0.700 , BIR: 0.7853982 (45.000) FD: 0.008103073 , FF: 0.007745917 , FD / FF: 1.046109000 , FDT / FFT: 0.915013104 , FDT: 70876 , FFT: 77459 , BGC: 0.700 , BIR: 0.6981317 (40.000) FD: 0.008462389 , FF: 0.007745917 , FD / FF: 1.092496809 , FDT / FFT: 1.027834080 , FDT: 79615 , FFT: 77459 , BGC: 0.700 , BIR: 0.5817764 (33.333) FD: 0.008615655 , FF: 0.007745917 , FD / FF: 1.112283510 , FDT / FFT: 1.091738855 , FDT: 84565 , FFT: 77459 , BGC: 0.700 , BIR: 0.5235988 (30.000) FD: 0.008786140 , FF: 0.007745917 , FD / FF: 1.134293080 , FDT / FFT: 1.183206600 , FDT: 91650 , FFT: 77459 , BGC: 0.700 , BIR: 0.4495619 (25.758) FD: 0.008974620 , FF: 0.007745917 , FD / FF: 1.158625907 , FDT / FFT: 1.333570018 , FDT: 103297 , FFT: 77459 , BGC: 0.700 , BIR: 0.3490659 (20.000) FD: 0.009187534 , FF: 0.007745917 , FD / FF: 1.186113193 , FDT / FFT: 1.742870422 , FDT: 135001 , FFT: 77459 , BGC: 0.700 , BIR: 0.1745329 (10.000) FD: 0.009240498 , FF: 0.007745917 , FD / FF: 1.192950818 , FDT / FFT: 2.152132096 , FDT: 166702 , FFT: 77459 , BGC: 0.700 , BIR: 0.0872665 (5.000) FD: 0.009257425 , FF: 0.007745917 , FD / FF: 1.195136079 , FDT / FFT: 3.103796847 , FDT: 240417 , FFT: 77459 , BGC: 0.700 , BIR: 0.0174533 (1.000) FD: 0.009258130 , FF: 0.007745917 , FD / FF: 1.195227103 , FDT / FFT: 10.244451904 , FDT: 793525 , FFT: 77459 , BGC: 0.700 , BIR: 0.0000001 (0.000) FD: 0.005628999 , FF: 0.007745917 , FD / FF: 0.726705349 , FDT / FFT: 0.570120967 , FDT: 44161 , FFT: 77459 , BGC: 0.750 , BIR: 1.1635528 (66.667) FD: 0.006324489 , FF: 0.007745917 , FD / FF: 0.816493245 , FDT / FFT: 0.660284796 , FDT: 51145 , FFT: 77459 , BGC: 0.750 , BIR: 1.0471976 (60.000) FD: 0.007170917 , FF: 0.007745917 , FD / FF: 0.925767398 , FDT / FFT: 0.796614983 , FDT: 61705 , FFT: 77459 , BGC: 0.750 , BIR: 0.8726646 (50.000) FD: 0.007521140 , FF: 0.007745917 , FD / FF: 0.970981204 , FDT / FFT: 0.869143676 , FDT: 67323 , FFT: 77459 , BGC: 0.750 , BIR: 0.7853982 (45.000) FD: 0.007828315 , FF: 0.007745917 , FD / FF: 1.010637611 , FDT / FFT: 0.947133322 , FDT: 73364 , FFT: 77459 , BGC: 0.750 , BIR: 0.6981317 (40.000) FD: 0.008175447 , FF: 0.007745917 , FD / FF: 1.055452492 , FDT / FFT: 1.063904775 , FDT: 82409 , FFT: 77459 , BGC: 0.750 , BIR: 0.5817764 (33.333) FD: 0.008323516 , FF: 0.007745917 , FD / FF: 1.074568261 , FDT / FFT: 1.130055901 , FDT: 87533 , FFT: 77459 , BGC: 0.750 , BIR: 0.5235988 (30.000) FD: 0.008488220 , FF: 0.007745917 , FD / FF: 1.095831526 , FDT / FFT: 1.224738249 , FDT: 94867 , FFT: 77459 , BGC: 0.750 , BIR: 0.4495619 (25.758) FD: 0.008670309 , FF: 0.007745917 , FD / FF: 1.119339270 , FDT / FFT: 1.380381879 , FDT: 106923 , FFT: 77459 , BGC: 0.750 , BIR: 0.3490659 (20.000) FD: 0.008876003 , FF: 0.007745917 , FD / FF: 1.145894511 , FDT / FFT: 1.804038265 , FDT: 139739 , FFT: 77459 , BGC: 0.750 , BIR: 0.1745329 (10.000) FD: 0.008927171 , FF: 0.007745917 , FD / FF: 1.152500285 , FDT / FFT: 2.227668831 , FDT: 172553 , FFT: 77459 , BGC: 0.750 , BIR: 0.0872665 (5.000) FD: 0.008943524 , FF: 0.007745917 , FD / FF: 1.154611448 , FDT / FFT: 3.212744807 , FDT: 248856 , FFT: 77459 , BGC: 0.750 , BIR: 0.0174533 (1.000) FD: 0.008944205 , FF: 0.007745917 , FD / FF: 1.154699385 , FDT / FFT: 10.604022773 , FDT: 821377 , FFT: 77459 , BGC: 0.750 , BIR: 0.0000001 (0.000) FD: 0.005450257 , FF: 0.007745917 , FD / FF: 0.703629694 , FDT / FFT: 0.588827638 , FDT: 45610 , FFT: 77459 , BGC: 0.800 , BIR: 1.1635528 (66.667) FD: 0.006123662 , FF: 0.007745917 , FD / FF: 0.790566449 , FDT / FFT: 0.681947869 , FDT: 52823 , FFT: 77459 , BGC: 0.800 , BIR: 1.0471976 (60.000) FD: 0.006943213 , FF: 0.007745917 , FD / FF: 0.896370693 , FDT / FFT: 0.822744936 , FDT: 63729 , FFT: 77459 , BGC: 0.800 , BIR: 0.8726646 (50.000) FD: 0.007282314 , FF: 0.007745917 , FD / FF: 0.940148773 , FDT / FFT: 0.897649079 , FDT: 69531 , FFT: 77459 , BGC: 0.800 , BIR: 0.7853982 (45.000) FD: 0.007579735 , FF: 0.007745917 , FD / FF: 0.978545924 , FDT / FFT: 0.978194916 , FDT: 75770 , FFT: 77459 , BGC: 0.800 , BIR: 0.6981317 (40.000) FD: 0.007915845 , FF: 0.007745917 , FD / FF: 1.021937746 , FDT / FFT: 1.098800656 , FDT: 85112 , FFT: 77459 , BGC: 0.800 , BIR: 0.5817764 (33.333) FD: 0.008059212 , FF: 0.007745917 , FD / FF: 1.040446510 , FDT / FFT: 1.167120670 , FDT: 90404 , FFT: 77459 , BGC: 0.800 , BIR: 0.5235988 (30.000) FD: 0.008218685 , FF: 0.007745917 , FD / FF: 1.061034578 , FDT / FFT: 1.264901432 , FDT: 97978 , FFT: 77459 , BGC: 0.800 , BIR: 0.4495619 (25.758) FD: 0.008394992 , FF: 0.007745917 , FD / FF: 1.083795853 , FDT / FFT: 1.425644535 , FDT: 110429 , FFT: 77459 , BGC: 0.800 , BIR: 0.3490659 (20.000) FD: 0.008594155 , FF: 0.007745917 , FD / FF: 1.109507854 , FDT / FFT: 1.863205050 , FDT: 144322 , FFT: 77459 , BGC: 0.800 , BIR: 0.1745329 (10.000) FD: 0.008643698 , FF: 0.007745917 , FD / FF: 1.115903867 , FDT / FFT: 2.300726836 , FDT: 178212 , FFT: 77459 , BGC: 0.800 , BIR: 0.0872665 (5.000) FD: 0.008659532 , FF: 0.007745917 , FD / FF: 1.117947992 , FDT / FFT: 3.318103771 , FDT: 257017 , FFT: 77459 , BGC: 0.800 , BIR: 0.0174533 (1.000) FD: 0.008660192 , FF: 0.007745917 , FD / FF: 1.118033137 , FDT / FFT: 10.951780942 , FDT: 848314 , FFT: 77459 , BGC: 0.800 , BIR: 0.0000001 (0.000) FD: 0.005138555 , FF: 0.007745917 , FD / FF: 0.663388872 , FDT / FFT: 0.624536852 , FDT: 48376 , FFT: 77459 , BGC: 0.900 , BIR: 1.1635528 (66.667) FD: 0.005773447 , FF: 0.007745917 , FD / FF: 0.745353632 , FDT / FFT: 0.723311687 , FDT: 56027 , FFT: 77459 , BGC: 0.900 , BIR: 1.0471976 (60.000) FD: 0.006546127 , FF: 0.007745917 , FD / FF: 0.845106829 , FDT / FFT: 0.872655211 , FDT: 67595 , FFT: 77459 , BGC: 0.900 , BIR: 0.8726646 (50.000) FD: 0.006865835 , FF: 0.007745917 , FD / FF: 0.886381199 , FDT / FFT: 0.952103694 , FDT: 73749 , FFT: 77459 , BGC: 0.900 , BIR: 0.7853982 (45.000) FD: 0.007146246 , FF: 0.007745917 , FD / FF: 0.922582379 , FDT / FFT: 1.037529532 , FDT: 80366 , FFT: 77459 , BGC: 0.900 , BIR: 0.6981317 (40.000) FD: 0.007463133 , FF: 0.007745917 , FD / FF: 0.963492581 , FDT / FFT: 1.165455273 , FDT: 90275 , FFT: 77459 , BGC: 0.900 , BIR: 0.5817764 (33.333) FD: 0.007598301 , FF: 0.007745917 , FD / FF: 0.980942812 , FDT / FFT: 1.237919415 , FDT: 95888 , FFT: 77459 , BGC: 0.900 , BIR: 0.5235988 (30.000) FD: 0.007748654 , FF: 0.007745917 , FD / FF: 1.000353428 , FDT / FFT: 1.341625892 , FDT: 103921 , FFT: 77459 , BGC: 0.900 , BIR: 0.4495619 (25.758) FD: 0.007914878 , FF: 0.007745917 , FD / FF: 1.021812964 , FDT / FFT: 1.512128997 , FDT: 117128 , FFT: 77459 , BGC: 0.900 , BIR: 0.3490659 (20.000) FD: 0.008102651 , FF: 0.007745917 , FD / FF: 1.046054472 , FDT / FFT: 1.976219678 , FDT: 153076 , FFT: 77459 , BGC: 0.900 , BIR: 0.1745329 (10.000) FD: 0.008149360 , FF: 0.007745917 , FD / FF: 1.052084691 , FDT / FFT: 2.440284538 , FDT: 189022 , FFT: 77459 , BGC: 0.900 , BIR: 0.0872665 (5.000) FD: 0.008164288 , FF: 0.007745917 , FD / FF: 1.054011910 , FDT / FFT: 3.519384449 , FDT: 272608 , FFT: 77459 , BGC: 0.900 , BIR: 0.0174533 (1.000) FD: 0.008164910 , FF: 0.007745917 , FD / FF: 1.054092185 , FDT / FFT: 11.616119495 , FDT: 899773 , FFT: 77459 , BGC: 0.900 , BIR: 0.0000001 (0.000) FD: 0.004874864 , FF: 0.007745917 , FD / FF: 0.629346292 , FDT / FFT: 0.658322467 , FDT: 50993 , FFT: 77459 , BGC: 1.000 , BIR: 1.1635528 (66.667) FD: 0.005477176 , FF: 0.007745917 , FD / FF: 0.707104891 , FDT / FFT: 0.762442066 , FDT: 59058 , FFT: 77459 , BGC: 1.000 , BIR: 1.0471976 (60.000) FD: 0.006210204 , FF: 0.007745917 , FD / FF: 0.801739083 , FDT / FFT: 0.919854375 , FDT: 71251 , FFT: 77459 , BGC: 1.000 , BIR: 0.8726646 (50.000) FD: 0.006513506 , FF: 0.007745917 , FD / FF: 0.840895388 , FDT / FFT: 1.003601906 , FDT: 77738 , FFT: 77459 , BGC: 1.000 , BIR: 0.7853982 (45.000) FD: 0.006779527 , FF: 0.007745917 , FD / FF: 0.875238844 , FDT / FFT: 1.093649544 , FDT: 84713 , FFT: 77459 , BGC: 1.000 , BIR: 0.6981317 (40.000) FD: 0.007080153 , FF: 0.007745917 , FD / FF: 0.914049669 , FDT / FFT: 1.228495075 , FDT: 95158 , FFT: 77459 , BGC: 1.000 , BIR: 0.5817764 (33.333) FD: 0.007208384 , FF: 0.007745917 , FD / FF: 0.930604411 , FDT / FFT: 1.304870964 , FDT: 101074 , FFT: 77459 , BGC: 1.000 , BIR: 0.5235988 (30.000) FD: 0.007351022 , FF: 0.007745917 , FD / FF: 0.949018939 , FDT / FFT: 1.414206225 , FDT: 109543 , FFT: 77459 , BGC: 1.000 , BIR: 0.4495619 (25.758) FD: 0.007508715 , FF: 0.007745917 , FD / FF: 0.969377242 , FDT / FFT: 1.593927110 , FDT: 123464 , FFT: 77459 , BGC: 1.000 , BIR: 0.3490659 (20.000) FD: 0.007686852 , FF: 0.007745917 , FD / FF: 0.992374755 , FDT / FFT: 2.083127848 , FDT: 161357 , FFT: 77459 , BGC: 1.000 , BIR: 0.1745329 (10.000) FD: 0.007731165 , FF: 0.007745917 , FD / FF: 0.998095523 , FDT / FFT: 2.572289857 , FDT: 199247 , FFT: 77459 , BGC: 1.000 , BIR: 0.0872665 (5.000) FD: 0.007745327 , FF: 0.007745917 , FD / FF: 0.999923844 , FDT / FFT: 3.709756129 , FDT: 287354 , FFT: 77459 , BGC: 1.000 , BIR: 0.0174533 (1.000) FD: 0.007745917 , FF: 0.007745917 , FD / FF: 1.000000000 , FDT / FFT: 12.244464814 , FDT: 948444 , FFT: 77459 , BGC: 1.000 , BIR: 0.0000001 (0.000)
2024.7.4 慣性モーメントを考慮していないので？意図した答えと違っている。しれっと「倒れる質量ゼロの棒の上にしがみつくか飛び降りるか」という話にしておく。コメント訂正。変数名も変更
しりとりで最長を得るアルゴリズムなんて研究しつくされてるんだろうけど、まぁ思いつかんので、力業。
ちょっと雑。間違ってるかも... (間違ってたので修正した)
public void Test02() { Node_t[] nodes = Directory.GetFiles(@"C:\home\画像\HPキャラ立ち絵\ウマ娘") .Select(file => Path.GetFileNameWithoutExtension(file)) .Select(name => name.Substring(name.IndexOf('_') + 1)) .DistinctOrderBy(SCommon.Comp) .Select(name => new Node_t() { Word = name }) .ToArray();
foreach (Node_t node in nodes)
node.EndPtn = GetEndPtn(node.Word);
LongestNodeArray = new Node_t[0];
foreach (Node_t node in nodes)
Search(nodes, node);
foreach (Node_t node in LongestNodeArray)
Console.WriteLine(node.Word);}
private Node_t[] LongestNodeArray;
private class Node_t { public string Word; public string EndPtn; public bool Reached; }
private string GetEndPtn(string name) { int p = name.Length - 1; int q = name.Length;
if (name[p] == 'ー')
{
p--;
q--;
}
if ("ッャュョァィゥェォ".Contains(name[p]))
p--;
return name.Substring(p, q - p);}
private void Search(Node_t[] nodes, Node_t startNode) { foreach (Node_t node in nodes) node.Reached = false;
S_Nodes = nodes;
S_Route = new List<Node_t>();
S_Route.Add(startNode);
startNode.Reached = true;
S_Next();
S_Nodes = null;
S_Route = null;}
private Node_t[] S_Nodes; private List S_Route;
private void S_Next() { if (LongestNodeArray.Length < S_Route.Count) LongestNodeArray = S_Route.ToArray();
Node_t lastNode = S_Route[S_Route.Count - 1];
foreach (Node_t node in S_Nodes)
{
if (!node.Reached && node.Word.StartsWith(lastNode.EndPtn))
{
node.Reached = true;
S_Route.Add(node);
S_Next();
node.Reached = false;
S_Route.RemoveAt(S_Route.Count - 1);
}
}}
出力
ホッコータルマエ エルコンドルパサー サムソンビッグ グラスワンダー ダイイチルビー ビターグラッセ セイウンスカイ イクノディクタス スイープトウショウ ウイニングチケット トランセンド ドゥラメンテ テイエムオペラオー オグリキャップ
2024.6.15 バグがあったので修正
2024.6.25 追記ここから
なんか増えたので少し長くなった。
ホッコータルマエ エルコンドルパサー サムソンビッグ グラスワンダー ダイイチルビー ビリーヴ ヴィルシーナ ナカヤマフェスタ タマモクロス スイープトウショウ ウオッカ カツラギエース スティルインラブ ブエナビスタ タニノギムレット トランセンド ドリームジャーニー ニシノフラワー ワンダーアキュート トウカイテイオー オグリキャップ
2024.6.25 追記ここまで
モブも追加して総勢801人でやってみようと思ったんだけど、こんな総当たり処理が終わるはずもないので
貪欲法でやってみようと思う。(注意：アルゴリズムは精査してないし、実装も雑也)
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.IO; using Charlotte.Commons;
namespace Charlotte.Tests { public class Test0008 { #region RES_NAMES
<summary>
</summary>
private string RES_NAMES = @"アイネスフウジン アグネスタキオン アグネスデジタル " +----------------+ | 長いので途中省略 | +----------------+ @" ヴィブロス ヴィルシーナ ヴェニュスパーク ; 佐岳メイ ; 秋川やよい ; 駿川たづな
; ここから追加
; ノーザンテースト ; トキノミノル ; ディクタス モンジュー ; ブロワイエ
; サ【佐岳メイ】イ ; ア【秋川やよい】イ ; ハ【駿川たづな】ナ ; オ【乙名史悦子】コ ; キ【桐生院葵】イ ; ア【安心沢刺々美】ミ ; カ【樫本理子】コ ; ツ【都留岐涼花】カ ; ア【赤坂美里】ト ; ホ【細江順子】コ
; オッチャホイ
";
#endregion
#region RES_MOB_NAMES
<summary>
</summary>
private string RES_MOB_NAMES = @"アーケードチャンプ アートルムグリモア アーリースプラウト " +----------------+ | 長いので途中省略 | +----------------+ @" ワクワクリボン ワルツステップ ワンインチオブラブ
";
#endregion
#region RES_KAIGAI_MOB_NAMES
<summary>
</summary>
string RES_KAIGAI_MOB_NAMES = @"アジーザ アルトピャーノ アルビコッコ " +----------------+ | 長いので途中省略 | +----------------+ @" プロムス ボールス レイナーディン
";
#endregion
public void Test01()
{
string[] names = SCommon.TextToLines(RES_NAMES)
.Where(line => !line.StartsWith(";"))
.Select(line => line.Trim())
.Where(line => line != "")
.ToArray();
{
string[] mobNames = SCommon.TextToLines(RES_MOB_NAMES)
.Concat(SCommon.TextToLines(RES_KAIGAI_MOB_NAMES))
.Where(line => !line.StartsWith(";"))
.Select(line => line.Trim())
.Where(line => line != "")
.ToArray();
names = names.Concat(mobNames).ToArray();
}
EndlessSearch(names);
}
private void EndlessSearch(string[] names)
{
#if true { string ZEN_KATAKANA = "ァアィイゥウェエォオカガキギクグケゲコゴサザシジスズセゼソゾタダチヂッツヅテデトドナニヌネノハバパヒビピフブプヘベペホボポマミムメモャヤュユョヨラリルレロワヰヱヲンヴ" + "ー" ;
foreach (string name in names)
{
if (name.Length < 3)
throw null;
foreach (char name_chr in name)
if (!ZEN_KATAKANA.Contains(name_chr))
throw null;
}
if (SCommon.HasSame(names, (a, b) => a == b))
throw null;
}#endif
Array.Sort(names, SCommon.Comp);
string[] longest = new string[0];
for (; ; )
{
string[] ret = new ShiritoriDONYOKU_Md().GetLongest(names);#if true { for (int index = 1; index < ret.Length; index++) { string name1 = ret[index - 1]; string name2 = ret[index]; string name1EndPtn = Shiritori_Md.GetEndPtn(name1);
if (!name2.StartsWith(name1EndPtn))
throw null;
}
if (SCommon.HasSame(ret, (a, b) => a == b))
throw null;
}#endif
ProcMain.WriteLog("しりとりの長さ：" + ret.Length);
if (longest.Length <= ret.Length)
{
ProcMain.WriteLog("★記録更新またはトップタイ！");
string outFile = string.Format(@"C:\temp\Shiritori_{0:D4}_{1}.txt", ret.Length, SimpleDateTime.Now().ToTimeStamp());
outFile = SCommon.ToCreatablePath(outFile);
File.WriteAllLines(outFile, ret, SCommon.ENCODING_SJIS);
longest = ret;
}
}
}
private class ShiritoriDONYOKU_Md
{
private const int JISHO_MAX = 100;
private const int JOINT_NUM = 20;
public string[] GetLongest(string[] names)
{
string[] longest = GetLongest_NEST(new string[0], names);
{
for (; ; )
{
names = names
.Where(name => !longest.Contains(name))
.ToArray();
string lastName = longest[longest.Length - 1];
string lastNameEndPtn = Shiritori_Md.GetEndPtn(lastName);
List<string> ikeruNames = new List<string>();
foreach (string name in names)
if (name.StartsWith(lastNameEndPtn))
ikeruNames.Add(name);
if (ikeruNames.Count == 0)
break;
string ikeruNextName = SCommon.CRandom.ChooseOne(ikeruNames);
longest = longest
.Concat(new string[] { ikeruNextName })
.ToArray();
}
}
{
for (; ; )
{
names = names
.Where(name => !longest.Contains(name))
.ToArray();
List<string> ikeruNames = new List<string>();
foreach (string name in names)
if (longest[0].StartsWith(Shiritori_Md.GetEndPtn(name)))
ikeruNames.Add(name);
if (ikeruNames.Count == 0)
break;
string ikeruNextName = SCommon.CRandom.ChooseOne(ikeruNames);
longest = new string[] { ikeruNextName }
.Concat(longest)
.ToArray();
}
}
return longest;
}
private string[] GetLongest_NEST(string[] route, string[] names)
{
string lastName = route.Length == 0 ? null : route[route.Length - 1];
string[] longest;
if (JISHO_MAX < names.Length)
{
longest = new string[0];
for (int c = 1; ; c++)
{
string[] ret = GetLongest_PART(lastName, names);
if (longest.Length < ret.Length)
longest = ret;
if (5 <= c && longest.Length != 0)
break;
if (30 <= c)
{
names = names.ToArray();
SCommon.CRandom.Shuffle(names);
names = names.Take(JISHO_MAX).ToArray();
goto finalPart;
}
}
route = route
.Concat(longest)
.ToArray();
names = names
.Where(name => !route.Contains(name))
.ToArray();
return GetLongest_NEST(route, names);
}
finalPart:
longest = new Shiritori_Md().GetLongest(names, lastName, 0);
route = route
.Concat(longest)
.ToArray();
return route;
}
private string[] GetLongest_PART(string lastName, string[] wholeNames)
{
List<string> names = new List<string>();
for (int c = 0; c < JISHO_MAX; c++)
{
names.Add(SCommon.CRandom.ChooseOne(wholeNames));
wholeNames = wholeNames
.Where(name => !names.Contains(name))
.ToArray();
}
return new Shiritori_Md().GetLongest(names.ToArray(), lastName, JOINT_NUM);
}
}
private class Shiritori_Md
{
public string[] GetLongest(string[] names, string lastName, int numOfJoint)
{
Node_t[] nodes = names
.Select(name => new Node_t() { Word = name })
.ToArray();
foreach (Node_t node in nodes)
node.EndPtn = GetEndPtn(node.Word);
foreach (Node_t node in nodes)
node.NextNodes = nodes
.Where(v => v.Word.StartsWith(node.EndPtn))
.ToArray();
SCommon.CRandom.Shuffle(nodes);
for (int index = 0; index < nodes.Length; index++)
nodes[index].JointFlag = index < numOfJoint;
LongestNodeArray = new Node_t[0];
JointSeigenNASHIFlag = numOfJoint == 0;
string startPtn = lastName == null ? null : GetEndPtn(lastName);
foreach (Node_t node in nodes)
if (startPtn == null || node.Word.StartsWith(startPtn))
Search(nodes, node);
string[] ret = LongestNodeArray
.Select(node => node.Word)
.ToArray();#if false { for (int index = 1; index < ret.Length; index++) { string name1 = ret[index - 1]; string name2 = ret[index]; string name1EndPtn = Shiritori_Md.GetEndPtn(name1);
if (!name2.StartsWith(name1EndPtn))
throw null;
}
if (SCommon.HasSame(ret, (a, b) => a == b))
throw null;
}#endif
return ret;
}
private Node_t[] LongestNodeArray;
private bool JointSeigenNASHIFlag;
private class Node_t
{
public string Word;
public string EndPtn;
public Node_t[] NextNodes;
public bool Reached;
public bool JointFlag;
}
public static string GetEndPtn(string name)
{
int p = name.Length - 1;
int q = name.Length;
if (name[p] == 'ー')
{
p--;
q--;
}
if ("ッャュョァィゥェォ".Contains(name[p]))
p--;
return name.Substring(p, q - p);
}
private void Search(Node_t[] nodes, Node_t startNode)
{
foreach (Node_t node in nodes)
node.Reached = false;
S_Nodes = nodes;
S_Route = new List<Node_t>();
S_Route.Add(startNode);
startNode.Reached = true;
S_Next();
S_Nodes = null;
S_Route = null;
}
private Node_t[] S_Nodes;
private List<Node_t> S_Route;
private void S_Next()
{
Node_t lastNode = S_Route[S_Route.Count - 1];
if (LongestNodeArray.Length < S_Route.Count && (JointSeigenNASHIFlag || lastNode.JointFlag))
LongestNodeArray = S_Route.ToArray();
foreach (Node_t node in lastNode.NextNodes)
{
if (!node.Reached)
{
node.Reached = true;
S_Route.Add(node);
S_Next();
node.Reached = false;
S_Route.RemoveAt(S_Route.Count - 1);
}
}
}
}
}}
結果
実行時間：6時間くらい
最長の長さ：133 (貪欲法なので真の最長とは限らない)
ヒッグススプレイ イツツバクローバー バイトアルヒクマ マラルメ メジロパーマー マリタイムシッパー パンパグランデ デザートベイビー ビワハヤヒデ デュオペルテ テイエムオペラオー オグリキャップ プチフォークロア アンコールワンモア アンロックザキー キンダーシャッツ ツウカア アップツリー リードエスエフ フライフィールド ドカドカ カワカミプリンセス スカンダ ダイタクヘリオス スリヴァッサ サムソンビッグ グリードホロウ ウィストクラフト トコトコ コスモスクレイパー パンパシフィック クリエイトセンド ドラグーンスピア アートルムグリモア アテーメ メジロブライト トゥージュール ルンバステップ プリメーラチーカ カツラギエース ステンツ ツーリングバイク クレセントエース スターリープライド ドミツィアーナ ナイスネイチャ チャタリングチーク クスタウィ ウィズカスパール ルーラルレジャー ジャーマンケーキ キュラキュラ ライスシャワー ワガハドウ ウィキッドレディ ディアレストギフト トゥトゥヌイ インディアンブレス スピーチレスハック クンバカルナ ナジュワー ワークフェイスフル ルミナスエスクード ドルジェ ジェンティルドンナ ナビゲートライト トーチアンドブック クレイジーインラブ ブラングリモア アルトピャーノ ノワールグリモア アクアレイク クピドズシュート トウカイテイオー オボロイブニング グーテンベルク クラースナヤ ヤマニンゼファー ファイネストデイ イズカリ リトルトラットリア アクアリバー バイタルダイナモ モンジュー ジュエルルビー ビアンコグリモア アルケカンジュ ジュエルオニキス スノーフロスト トラフィックライツ ツルマルツヨシ シナモンミルク クラシックコメディ ディスティネイト トランセンド ドミナントパワー ワンインチオブラブ ブリーズチョッパー パイケア アングータ タイドアンドフロウ ウイニングチケット トランペットリズム ムルジャーナ ナリタトップロード ドリコスランナー ナカヤマフェスタ タヴァティムサ サラサーテオペラ ラピッドビルダー ダイイチルビー ビーティングパルス スペインジェラート トラッドパルフェ フェアリーズエコー コードオブハート トロピカルスカイ イッツコーリング グリンタンニ ニシノフラワー ワンダーアキュート トンネリングボイス スティルインラブ ブリテンプライム ムーンポップ プレザントクラーク クリッカー カウリラリス スクイーズアウト トゥプシマティ ティッピングタップ プカプカ カラフルパステル
2024.9.23 追記
なんとなしにアルゴリズムをシンプルにしてみたら記録が伸びた。
モブ含め総勢 807 名
using System; using System.Collections.Generic; using System.Linq; using System.Text; using Charlotte.Commons;
namespace Charlotte.Tests { public class Test0012 { #region RES_NAMES
<summary>
</summary>
private string RES_NAMES = @"アイネスフウジン アグネスタキオン アグネスデジタル " +----------------+ | 長いので途中省略 | +----------------+ @" ヴィブロス ヴィルシーナ ヴェニュスパーク
; ここから追加
モンジュー
; ---- ; 2024.6.25 公式に追加されたウマ娘
カルストンライトオ デュランダル ドリームジャーニー ビリーヴ ブエナビスタ
; ---- ; 更に公式に追加されたウマ娘 (2024.9.22 現在)
バブルガムフェロー
; ----
";
#endregion
#region RES_MOB_NAMES
<summary>
</summary>
private string RES_MOB_NAMES = @"アーケードチャンプ アートルムグリモア アーリースプラウト " +----------------+ | 長いので途中省略 | +----------------+ @" ワクワクリボン ワルツステップ ワンインチオブラブ
";
#endregion
#region RES_KAIGAI_MOB_NAMES
<summary>
</summary>
string RES_KAIGAI_MOB_NAMES = @"アジーザ アルトピャーノ アルビコッコ " +----------------+ | 長いので途中省略 | +----------------+ @" プロムス ボールス レイナーディン
";
#endregion
private class Word_t
{
public string Word;
public string EndPtn;
public Word_t(string word)
{
this.Word = word;
this.EndPtn = GetEndPtn(word);
}
private static string GetEndPtn(string word)
{
int i = word.Length - 1;
if (word[i] == 'ー')
i--;
int s = i;
int e = i + 1;
if ("ァィゥェォッャュョヮヵヶ".Contains(word[i]))
s--;
return word.Substring(s, e - s);
}
public bool Reached;
public Word_t[] ConnectableWords;
}
public void Test01()
{
Word_t[] words = SCommon.TextToLines(RES_NAMES
+ "\r\n"
+ RES_MOB_NAMES
+ "\r\n"
+ RES_KAIGAI_MOB_NAMES
)
.Select(line => line.Trim())
.Where(line => line != "" && line[0] != ';')
.Select(line => new Word_t(line))
.ToArray();
foreach (Word_t word in words)
{
word.ConnectableWords = words
.Where(w => w.Word.StartsWith(word.EndPtn))
.ToArray();
}
Word_t[] best = new Word_t[0];
for (; ; )
{
Word_t[] curr = TryShiritori(words);
if (best.Length < curr.Length)
{
best = curr;
curr = null;
foreach (Word_t word in best)
Console.WriteLine(word.Word);
Console.WriteLine(best.Length);
}
}
}
private const int MAGIC_NUMBER_01 = 4;
private const int MAGIC_NUMBER_02 = 4;
private Word_t[] TryShiritori(Word_t[] words)
{
Word_t[] best = new Word_t[] { SCommon.CRandom.ChooseOne(words) };
for (int depth = 1; ; depth++)
{
Word_t[] aFewBack = best.Take(Math.Max(1, best.Length - MAGIC_NUMBER_01)).ToArray();
Word_t[] aFewBackBest = null;
for (int trycnt = 0; trycnt < depth * MAGIC_NUMBER_02; trycnt++)
{
Word_t[] curr = Search(words, aFewBack);
if (aFewBackBest == null || aFewBackBest.Length < curr.Length)
aFewBackBest = curr;
}
if (aFewBackBest.Length <= best.Length)
break;
best = aFewBackBest;
}
return best;
}
private Word_t[] Search(Word_t[] words, Word_t[] destLead)
{
foreach (Word_t word in words)
word.Reached = false;
foreach (Word_t word in destLead)
word.Reached = true;
List<Word_t> dest = destLead.ToList();
for (; ; )
{
Word_t lastWord = dest[dest.Count - 1];
Word_t[] nextWords = lastWord.ConnectableWords.Where(w => !w.Reached).ToArray();
if (nextWords.Length == 0)
break;
Word_t nextWord = SCommon.CRandom.ChooseOne(nextWords);
nextWord.Reached = true;
dest.Add(nextWord);
}
return dest.ToArray();
}
}}
結果
実行時間：8時間くらい
最長の長さ：216 (貪欲法なので真の最長とは限らない)
ゴールドシュシュ シュヴィークザーム ムシャムシャ シャープアトラクト トーチアンドブック クラシックコメディ ディヴィニティー ティッピングタップ プリスティンソング グリーンシュシュ シュプールムーバー バシレイオンタッチ チルウェイヴ ヴァッサゴ ゴドルフィンバルブ ブラボーツヴァイ イマジンサクセス スノーフロスト トランセンド ドミナントパワー ワークフェイスフル ルンバステップ プニプニ ニシノフラワー ワイスマネージャー ジャドプラーテ テトラビブロス スプリングハッピー ピンクシュシュ シュガーニンフェ フェニキアディール ルーラルレジャー ジャッジョーロ ロイスアンドロイス ステンツ ツーリングバイク クンバカルナ ナルキッソス スプーキーナイト トランペットリズム ムルーガ ガーリースマイル ルミナスエスクード ドゥラメンテ テンダーステップ プロペライザー ザオバアー アメティースタ タップステップ プレダトリス スリヴァッサ サイレンススズカ カジュアルスナップ プチフォークロア アクアガイザー ザンバーハ ハープアルファ ファイネストデイ イースタンダイナー ナリタトップロード ドルジェ ジェンティルドンナ ナイスネイチャ チャタリングチーク クピドズシュート トンネリングボイス スターリープライド ドロッピングリンク クリッカー カウリラリス スクイーズアウト トコトコ コインシデンス スーペリアブルーム ムルジャーナ ナーイリズム ムーンポップ プリメーラチーカ カワカミプリンセス スーパークリーク クレセントエース スウィートパルフェ フェアリーズエコー コロッセオファイト トゥトゥヌイ インディアンブレス スピーチレスハック クスタウィ ウィキッドレディ ディスティネイト トラフィックライツ ツインターボ ボウアンドシールド ドミツィアーナ ナジュワー ワンインチオブラブ ブラボーセカンド ドリコスランナー ナカヤマフェスタ タイドアンドフロウ ウカルディ ディアレストギフト トロピカルスカイ インテンスリマーク クロニクルオース スカンダ ダディーズブーツ ツウカア アンチェンジング グラスワンダー ダイイチルビー ビワハヤヒデ デュオバックラー ラピッドビルダー ダブルサラウンド ドラグーンスピア アンコールワンモア アイスホッパー パワフルトルク クラヴァット トンボロ ロディーナ ナターレノッテ テルパンダー ダークグリモア アウトオブブラック クラースナヤ ヤッピーラッキー キタサンブラック クレイジーインラブ ブリッジコンプ プロムス スティルインラブ ブリーズエアシップ プレザントクラーク クリシュマルド ドカドカ カツラギエース スイープトウショウ ウミディタ タヴァティムサ サムソンビッグ グリードホロウ ウォーキートーキー キララウス ストレートバレット トウカイテイオー オジュルデュイ イズカリ リボンヴィルレー レアキンスリー リードポエトリー リフレクター タイムティッキング グレイトハウス スペシャルウィーク クライネキステ テイエムオペラオー オレッキーノ ノワールグリモア アクアリバー バイタルダイナモ モンジュー ジュエルサファイア アップツリー リボンララバイ イラッパ パスタイムジョイ インサラータ ターボデトネーター タマシチ チーフパーサー サンフィッシュレイ イツツバクローバー バードアンドクリフ フィールフロイデ デュオジャヌイヤ ヤエノムテキ キュラキュラ ライスシャワー ワルツステップ プカプカ カルストンライトオ オグレッセ セイウンスカイ インサイトキャッチ チョコチョコ コパノリッキー キンダーシャッツ ツルマルツヨシ シャンソンジェンヌ ヌュアージュ ジュエルルビー ビヨンドレブリミ ミスターシービー ビームオブラブ ブリーズチョッパー パイケア アルビコッコ コスモスクレイパー パンパグランデ デュアリングステラ ラトウィゥジ ジャリアー アイタンリ リーフリーフ フリルドチェリー リードエスエフ フリルドベリー リボンエレジー ジャーマンケーキ キングヘイロー ローズブーケトス スペインジェラート トゥプシマティ ティップオブタン
RDBを使わずにCSVでなんとかしてみた結果できた副産物。
特筆するようなところはないと思う。
概ね自分用。
CsvFileDBTable.cs
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.IO; using Charlotte.Commons; using Charlotte.Utilities;
namespace Charlotte.Tools { public class CsvFileDBTable {
private static int BUFFER_SIZE_MAX = 1000;
private static int MEMORY_LOAD_MAX = 50000000;
public static void DEBUG_SetBufferSizeMax(int value)
{
BUFFER_SIZE_MAX = value;
}
public static void DEBUG_SetMemoryLoadMax(int value)
{
MEMORY_LOAD_MAX = value;
}
private static int RowsToMemoryLoad(string[][] rows)
{
return rows.Length * 100 + rows.Sum(row => row.Length * 100 + row.Sum(v => v.Length * 2));
}
private static int RowToMemoryLoad(string[] row)
{
return RowsToMemoryLoad(new string[][] { row });
}
private string FilePath;
<summary>
</summary>
private string DeleteBufferFilePath
{
get
{
return this.FilePath + "_DeleteBuffer.csv";
}
}
<summary>
</summary>
private string UpdateBufferFilePath
{
get
{
return this.FilePath + "_UpdateBuffer.csv";
}
}
private int DeleteBufferSize;
private int DeleteMemoryLoad;
private int UpdateBufferSize;
private int UpdateMemoryLoad;
public CsvFileDBTable(string file)
{
this.FilePath = SCommon.MakeFullPath(file);
if (!File.Exists(this.FilePath))
File.WriteAllBytes(this.FilePath, SCommon.EMPTY_BYTES);
if (!File.Exists(this.DeleteBufferFilePath))
File.WriteAllBytes(this.DeleteBufferFilePath, SCommon.EMPTY_BYTES);
if (!File.Exists(this.UpdateBufferFilePath))
File.WriteAllBytes(this.UpdateBufferFilePath, SCommon.EMPTY_BYTES);
using (CsvFileReader reader = new CsvFileReader(this.DeleteBufferFilePath))
{
string[][] rows = reader.ReadToEnd();
this.DeleteBufferSize = rows.Length;
this.DeleteMemoryLoad = RowsToMemoryLoad(reader.ReadToEnd());
}
using (CsvFileReader reader = new CsvFileReader(this.UpdateBufferFilePath))
{
string[][] rows = reader.ReadToEnd();
this.UpdateBufferSize = rows.Length;
this.UpdateMemoryLoad = RowsToMemoryLoad(reader.ReadToEnd());
}
}
<summary>
</summary>
<param name="reaction"></param>
public void ForEach(Predicate<string[]> reaction)
{
if (reaction == null)
throw new Exception("Bad reaction");
HashSet<string> deletedOrKnownIDs = new HashSet<string>();
string[][] addedOrUpdatedRows;
using (CsvFileReader reader = new CsvFileReader(this.DeleteBufferFilePath))
{
foreach (string id in reader.ReadToEnd().Select(row => row[0]))
{
deletedOrKnownIDs.Add(id);
}
}
using (CsvFileReader reader = new CsvFileReader(this.UpdateBufferFilePath))
{
addedOrUpdatedRows = reader.ReadToEnd();
}
foreach (string[] row in addedOrUpdatedRows.Reverse())
{
if (deletedOrKnownIDs.Contains(row[0]))
continue;
if (!reaction(row))
return;
deletedOrKnownIDs.Add(row[0]);
}
using (CsvFileReader reader = new CsvFileReader(this.FilePath))
{
for (; ; )
{
string[] row = reader.ReadRow();
if (row == null)
break;
if (deletedOrKnownIDs.Contains(row[0]))
continue;
if (!reaction(row))
break;
}
}
}
<summary>
==
==
==
</summary>
<param name="filter"></param>
public void FilterAll(Func<string[], string[]> filter)
{
if (filter == null)
throw new Exception("Bad filter");
using (WorkingDir wd = new WorkingDir())
{
string midFile = wd.MakePath();
using (CsvFileWriter writer = new CsvFileWriter(midFile))
{
this.ForEach(row =>
{
string[] newRow = filter(row);
if (newRow != null)
{
if (
newRow.Length < 1 ||
newRow.Any(v => v == null) ||
newRow[0] != row[0]
)
throw new Exception("Bad newRow");
writer.WriteRow(newRow);
}
return true;
});
}
SCommon.DeletePath(this.FilePath);
File.Move(midFile, this.FilePath);
}
File.WriteAllBytes(this.DeleteBufferFilePath, SCommon.EMPTY_BYTES);
File.WriteAllBytes(this.UpdateBufferFilePath, SCommon.EMPTY_BYTES);
this.DeleteBufferSize = 0;
this.DeleteMemoryLoad = 0;
this.UpdateBufferSize = 0;
this.UpdateMemoryLoad = 0;
}
public List<string[]> Search(Predicate<string[]> match, int limit, out bool overflow)
{
if (
match == null ||
limit < 1 || SCommon.IMAX < limit
)
throw new Exception("Bad params");
List<string[]> dest = new List<string[]>();
bool wOverflow = false;
this.ForEach(row =>
{
if (match(row))
{
if (limit <= dest.Count)
{
wOverflow = true;
return false;
}
dest.Add(row);
}
return true;
});
overflow = wOverflow;
return dest;
}
public List<string[]> Search(Predicate<string[]> match, Comparison<string[]> comp, int limit, out int count)
{
if (
match == null ||
comp == null ||
limit < 1 || SCommon.IMAX < limit
)
throw new Exception("Bad params");
int DEST_MAX = Math.Max(limit + limit / 2, 100);
List<string[]> dest = new List<string[]>();
int wCount = 0;
this.ForEach(row =>
{
if (match(row))
{
if (DEST_MAX < dest.Count)
{
dest.Sort(comp);
dest.RemoveRange(limit, dest.Count - limit);
}
dest.Add(row);
wCount++;
}
return true;
});
dest.Sort(comp);
if (limit < dest.Count)
dest.RemoveRange(limit, dest.Count - limit);
count = wCount;
return dest;
}
public List<string[]> Search(Predicate<string[]> match, Comparison<string[]> comp, int offset, int limit, out int count)
{
if (
match == null ||
comp == null ||
offset < 0 || SCommon.IMAX < offset ||
limit < 1 || SCommon.IMAX - offset < limit
)
throw new Exception("Bad params");
List<string[]> dest = new List<string[]>();
int wCount = 0;
using (WorkingDir wd = new WorkingDir())
{
string midFile = wd.MakePath();
using (CsvFileWriter writer = new CsvFileWriter(midFile))
{
this.ForEach(row =>
{
if (match(row))
{
writer.WriteRow(row);
wCount++;
}
return true;
});
}
CsvFileSorter.Sort(midFile, comp);
using (CsvFileReader reader = new CsvFileReader(midFile))
{
for (int index = 0; index < wCount; index++)
{
string[] row = reader.ReadRow();
if (row == null)
throw null;
if (index < offset)
continue;
dest.Add(row);
if (limit <= dest.Count)
break;
}
}
}
count = wCount;
return dest;
}
public void Search(Predicate<string[]> match, Comparison<string[]> comp, Predicate<string[]> reaction)
{
if (
match == null ||
comp == null ||
reaction == null
)
throw new Exception("Bad params");
using (WorkingDir wd = new WorkingDir())
{
string midFile = wd.MakePath();
using (CsvFileWriter writer = new CsvFileWriter(midFile))
{
this.ForEach(row =>
{
if (match(row))
writer.WriteRow(row);
return true;
});
}
CsvFileSorter.Sort(midFile, comp);
using (CsvFileReader reader = new CsvFileReader(midFile))
{
for (; ; )
{
string[] row = reader.ReadRow();
if (row == null)
break;
if (!reaction(row))
break;
}
}
}
}
<summary>
</summary>
<param name="id"></param>
public void Delete(string id)
{
if (string.IsNullOrEmpty(id))
throw new Exception("Bad id");
using (CsvFileWriter writer = new CsvFileWriter(this.DeleteBufferFilePath, true))
{
writer.WriteCell(id);
writer.EndRow();
}
this.DeleteBufferSize += 1;
this.DeleteMemoryLoad += RowToMemoryLoad(new string[] { id });
if (
BUFFER_SIZE_MAX < this.DeleteBufferSize ||
MEMORY_LOAD_MAX < this.DeleteMemoryLoad
)
this.Flush();
}
<summary>
</summary>
<param name="row"></param>
public void AddOrUpdate(string[] row)
{
if (
row == null ||
row.Length < 1 ||
row.Any(v => v == null) ||
row[0] == ""
)
throw new Exception("Bad row");
if (1 <= this.DeleteBufferSize)
this.Flush();
using (CsvFileWriter writer = new CsvFileWriter(this.UpdateBufferFilePath, true))
{
writer.WriteRow(row);
}
this.UpdateBufferSize += 1;
this.UpdateMemoryLoad += RowToMemoryLoad(row);
if (
BUFFER_SIZE_MAX < this.UpdateBufferSize ||
MEMORY_LOAD_MAX < this.UpdateMemoryLoad
)
this.Flush();
}
private void Flush()
{
if (
this.DeleteBufferSize == 0 &&
this.UpdateBufferSize == 0
)
return;
using (WorkingDir wd = new WorkingDir())
{
string midFile = wd.MakePath();
using (CsvFileWriter writer = new CsvFileWriter(midFile))
{
this.ForEach(row =>
{
writer.WriteRow(row);
return true;
});
}
SCommon.DeletePath(this.FilePath);
File.Move(midFile, this.FilePath);
}
File.WriteAllBytes(this.DeleteBufferFilePath, SCommon.EMPTY_BYTES);
File.WriteAllBytes(this.UpdateBufferFilePath, SCommon.EMPTY_BYTES);
this.DeleteBufferSize = 0;
this.DeleteMemoryLoad = 0;
this.UpdateBufferSize = 0;
this.UpdateMemoryLoad = 0;
}
public void Sort(Comparison<string[]> comp)
{
if (comp == null)
throw new Exception("Bad comp");
this.Flush();
CsvFileSorter.Sort(this.FilePath, comp);
}
public void Truncate()
{
File.WriteAllBytes(this.FilePath, SCommon.EMPTY_BYTES);
File.WriteAllBytes(this.DeleteBufferFilePath, SCommon.EMPTY_BYTES);
File.WriteAllBytes(this.UpdateBufferFilePath, SCommon.EMPTY_BYTES);
this.DeleteBufferSize = 0;
this.DeleteMemoryLoad = 0;
this.UpdateBufferSize = 0;
this.UpdateMemoryLoad = 0;
}
public void BulkInsert(Func<string[]> reader)
{
if (reader == null)
throw new Exception("Bad reader");
this.Flush();
using (CsvFileWriter writer = new CsvFileWriter(this.FilePath, true))
{
for (; ; )
{
string[] row = reader();
if (row == null)
break;
if (
row.Length < 1 ||
row.Any(v => v == null) ||
row[0] == ""
)
throw new Exception("Bad row");
writer.WriteRow(row);
}
}
}
}}
CsvFileSorter.cs
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.IO; using Charlotte.Commons; using Charlotte.Utilities;
namespace Charlotte.Tools { public static class CsvFileSorter { private static int MEMORY_LOAD_MAX = 200000000;
public static void DEBUG_SetMemoryLoadMax(int value)
{
MEMORY_LOAD_MAX = value;
}
public static List<int> DEBUG_LastRowCountList = new List<int>();
private static int RowToMemoryLoad(string[] row)
{
return 100 + row.Length * 100 + row.Sum(v => v.Length) * 2;
}
public static void Sort(string file, Comparison<string[]> comp)
{
Sort(file, file, comp);
}
public static void Sort(string rFile, string wFile, Comparison<string[]> comp)
{
rFile = SCommon.MakeFullPath(rFile);
wFile = SCommon.MakeFullPath(wFile);
if (!File.Exists(rFile))
throw new Exception("no rFile");
if (Directory.Exists(wFile))
throw new Exception("Bad wFile");
if (comp == null)
throw new Exception("Bad comp");
using (WorkingDir wd = new WorkingDir())
{
Queue<string> q = new Queue<string>();
DEBUG_LastRowCountList.Clear();
using (CsvFileReader reader = new CsvFileReader(rFile))
{
for (; ; )
{
List<string[]> rows = new List<string[]>();
string[] row;
int memoryLoad = 0;
for (; ; )
{
row = reader.ReadRow();
if (row == null)
break;
rows.Add(row);
memoryLoad += RowToMemoryLoad(row);
if (MEMORY_LOAD_MAX < memoryLoad)
break;
}
if (1 <= rows.Count)
{
rows.Sort(comp);
string midFile = wd.MakePath();
using (CsvFileWriter writer = new CsvFileWriter(midFile))
{
writer.WriteRows(rows);
}
q.Enqueue(midFile);
DEBUG_LastRowCountList.Add(rows.Count);
}
if (row == null)
break;
}
}
if (q.Count == 0)
{
File.WriteAllBytes(wFile, SCommon.EMPTY_BYTES);
}
else
{
while (2 <= q.Count)
{
string midFile1 = q.Dequeue();
string midFile2 = q.Dequeue();
string midFile3 = wd.MakePath();
using (CsvFileReader reader1 = new CsvFileReader(midFile1))
using (CsvFileReader reader2 = new CsvFileReader(midFile2))
using (CsvFileWriter writer = new CsvFileWriter(midFile3))
{
string[] row1 = reader1.ReadRow();
string[] row2 = reader2.ReadRow();
while (row1 != null && row2 != null)
{
int ret = comp(row1, row2);
if (ret <= 0)
{
writer.WriteRow(row1);
row1 = reader1.ReadRow();
}
if (0 <= ret)
{
writer.WriteRow(row2);
row2 = reader2.ReadRow();
}
}
while (row1 != null)
{
writer.WriteRow(row1);
row1 = reader1.ReadRow();
}
while (row2 != null)
{
writer.WriteRow(row2);
row2 = reader2.ReadRow();
}
}
q.Enqueue(midFile3);
}
SCommon.DeletePath(wFile);
File.Move(q.Dequeue(), wFile);
}
}
}
}}
CsvFileReader.cs
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.IO; using Charlotte.Commons;
namespace Charlotte.Utilities { public class CsvFileReader : IDisposable { public const char DELIMITER_COMMA = ','; public const char DELIMITER_SPACE = ' '; public const char DELIMITER_TAB = '\t';
private char Delimiter;
private StreamReader Reader;
public CsvFileReader(string file)
: this(file, SCommon.ENCODING_SJIS)
{ }
public CsvFileReader(string file, Encoding encoding)
: this(file, encoding, DELIMITER_COMMA)
{ }
public CsvFileReader(string file, Encoding encoding, char delimiter)
{
this.Delimiter = delimiter;
this.Reader = new StreamReader(file, encoding);
}
private int LastChar;
private int ReadChar()
{
do
{
this.LastChar = this.Reader.Read();
}
while (this.LastChar == '\r');
return this.LastChar;
}
private bool EnclosedCell;
private string ReadCell()
{
StringBuilder buff = new StringBuilder();
if (this.ReadChar() == '"')
{
while (this.ReadChar() != -1 && (this.LastChar != '"' || this.ReadChar() == '"'))
{
buff.Append((char)this.LastChar);
}
this.EnclosedCell = true;
}
else
{
while (this.LastChar != -1 && this.LastChar != '\n' && this.LastChar != this.Delimiter)
{
buff.Append((char)this.LastChar);
this.ReadChar();
}
this.EnclosedCell = false;
}
return buff.ToString();
}
public string[] ReadRow()
{
List<string> row = new List<string>();
do
{
row.Add(this.ReadCell());
}
while (this.LastChar != -1 && this.LastChar != '\n');
if (this.LastChar == -1 && row.Count == 1 && row[0] == "" && !this.EnclosedCell)
return null;
return row.ToArray();
}
public string[][] ReadToEnd()
{
List<string[]> rows = new List<string[]>();
for (; ; )
{
string[] row = this.ReadRow();
if (row == null)
break;
rows.Add(row);
}
return rows.ToArray();
}
public void Dispose()
{
if (this.Reader != null)
{
this.Reader.Dispose();
this.Reader = null;
}
}
}}
CsvFileWriter.cs
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.IO; using Charlotte.Commons;
namespace Charlotte.Utilities { public class CsvFileWriter : IDisposable { public const char DELIMITER_COMMA = ','; public const char DELIMITER_SPACE = ' '; public const char DELIMITER_TAB = '\t';
private char Delimiter;
private StreamWriter Writer;
public CsvFileWriter(string file, bool append = false)
: this(file, append, SCommon.ENCODING_SJIS)
{ }
public CsvFileWriter(string file, bool append, Encoding encoding)
: this(file, append, encoding, DELIMITER_COMMA)
{ }
public CsvFileWriter(string file, bool append, Encoding encoding, char delimiter)
{
this.Delimiter = delimiter;
this.Writer = new StreamWriter(file, append, encoding);
}
<summary>
</summary>
private bool FirstCell = true;
public void WriteCell(string cell)
{
if (this.FirstCell)
this.FirstCell = false;
else
this.Writer.Write(this.Delimiter);
if (
cell.Contains('"') ||
cell.Contains('\n') ||
cell.Contains(this.Delimiter)
)
{
this.Writer.Write('"');
this.Writer.Write(cell.Replace("\"", "\"\""));
this.Writer.Write('"');
}
else
{
this.Writer.Write(cell);
}
}
public void EndRow()
{
this.Writer.Write('\n');
this.FirstCell = true;
}
public void WriteCells(IList<string> cells)
{
foreach (string cell in cells)
{
this.WriteCell(cell);
}
}
public void WriteRow(IList<string> row)
{
foreach (string cell in row)
{
this.WriteCell(cell);
}
this.EndRow();
}
public void WriteRows(IList<string[]> rows)
{
foreach (string[] row in rows)
{
this.WriteRow(row);
}
}
public void Dispose()
{
if (this.Writer != null)
{
this.Writer.Dispose();
this.Writer = null;
}
}
}}