atCoderとGo言語のメモ
競プロ典型 90 問の055 - Select 5
大きな数の余り
Aiは、10の9乗なので、Aを5個掛けるとint64の範囲を超えてしまう。
int64は、おおよそ19桁
しかし、これは除算の余りを求める問題なので、余剰の性質を使う。
(A * B) % x = ((A % x) * (B % x)) %x
組み合わせ
n個の中から、5個をとる組み合わせ。
自分のコーディングスキルの性か、再帰で組み合わせを求める関数を書いたら、TLEになってしまった。
よくわかっていないが、動的計画法?のような方法で、列挙した方がよいらしい。
※他の回答者の回答を参考にさせていただいたところ、そうなっていた。
パナソニックプログラミングコンテスト(AtCoder Beginner Contest 195)
B - Many Oranges 解説 by kyopro_friends
問題:1 個がA グラム以上B グラム以下のみかんをちょうどN 個選んで W キログラムにすることはできるか?
この問題に対する答えは、AN≤1000W≤BN が成り立つとき Yes、成り立たないとき No です。
解説を読んでもしばらく、よくわからなかったが、
- この条件を満たしていないと、そもそもN個で目的が達成できない
- この条件を満たしていると、A<X<Bを満たす任意の重さのミカンをN個組わせて、AN≦Y≦BNの範囲の任意の重さYを作るれる
ということか。
AtCoder Beginner Contest 088
C - Takahashi's Information
問題のどこにも、a,bは非負とか書いていないのだけど。
他の人の正答を見てみると、非負の範囲で回しているものもACとなっている。
まぁ、-100から回してもACになるし、TLEにはならないので良いのですが、
制約事項には、書いてほしい気がする。
第一回 アルゴリズム実技検定 過去問 F - DoubleCamelCase Sort
かなり苦戦した。
理由としては、単語ごとに文字を区切る際に、別のバッファに文字のコピーを取るのだけれど、これを一文字ずつ、スライスにappendしている処理が遅かった、ということに気が付くのに時間がかかった。
また、一旦別のruneスライスを作成して、そこに一旦退避した後、それを文字列に変換して、再度コピーする、という処理を行っていたことも問題だったのだろう。
オリジナルの文字列から、単語単位で、文字列を切り出すことでLTEすることはなくなった。
シンプルな問題にも関わらず、1時間程度ハマってしまった。