Zenn
Open4

atCoderとGo言語のメモ

mortlackmortlack

競プロ典型 90 問の055 - Select 5

大きな数の余り

Aiは、10の9乗なので、Aを5個掛けるとint64の範囲を超えてしまう。
int64は、おおよそ19桁

しかし、これは除算の余りを求める問題なので、余剰の性質を使う。

(A * B) % x = ((A % x) * (B % x)) %x

組み合わせ

n個の中から、5個をとる組み合わせ。
自分のコーディングスキルの性か、再帰で組み合わせを求める関数を書いたら、TLEになってしまった。

よくわかっていないが、動的計画法?のような方法で、列挙した方がよいらしい。
※他の回答者の回答を参考にさせていただいたところ、そうなっていた。

それ、非再帰で書けます

mortlackmortlack

パナソニックプログラミングコンテスト(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を作るれる

ということか。

mortlackmortlack

AtCoder Beginner Contest 088

C - Takahashi's Information

問題のどこにも、a,bは非負とか書いていないのだけど。
他の人の正答を見てみると、非負の範囲で回しているものもACとなっている。
まぁ、-100から回してもACになるし、TLEにはならないので良いのですが、
制約事項には、書いてほしい気がする。

mortlackmortlack

第一回 アルゴリズム実技検定 過去問 F - DoubleCamelCase Sort

かなり苦戦した。

理由としては、単語ごとに文字を区切る際に、別のバッファに文字のコピーを取るのだけれど、これを一文字ずつ、スライスにappendしている処理が遅かった、ということに気が付くのに時間がかかった。

また、一旦別のruneスライスを作成して、そこに一旦退避した後、それを文字列に変換して、再度コピーする、という処理を行っていたことも問題だったのだろう。

オリジナルの文字列から、単語単位で、文字列を切り出すことでLTEすることはなくなった。

シンプルな問題にも関わらず、1時間程度ハマってしまった。

ログインするとコメントできます