問題リンク Maximum Sum Sequence 解法 最大連続部分和を求める問題です。 n区間の左と右を全通り試すO(n^2)の方法でももしかしたら通るかもしれませんが時間的に厳しそうです。 最大連続部分和はO(n)で求められます。 要素をa1〜anとします。 xiをa1〜aiま…

問題リンク Parallelism 解法 ２直線の傾きを求めてそれらが同じかを調べても解けると思いますが、ABベクトルとCDベクトルの外積が0なら平行と分かります。 AB x CD = |AB||CD|sinθ なので、ベクトルのなす角が平行(θ=0,180)なら外積が0になるわけです。 ソ…

問題リンク Capitalize 解法 英小文字を見つけたら英大文字に変換すればいいので、Character.toUpperCase()を使います。 以下のソースでAcceptしてるので、このメソッドはアルファベット以外の文字は何も変化が起きないという仕様なのでしょう。 ソース

問題リンク Factorial 解法 1 n! = n*(n-1)! なんでDPチックに解くのがより高速でしょうかね。 蛇足ですが、n!の桁数が欲しい時にはスターリングの近似で求められます。PKUにそんな問題があった気がします。 ソース

問題リンク Sorting Five Numbers 解法 超シンプルソーティング問題です。 Arrays.sort()でソートかけて後ろから出力すれば勝ちです。 なんか自分は選択法を直書きして解いてますが。 ソース

問題リンク Caesar Cipher 解法 アルファベットをK文字ずらして暗号解読する問題です。 一瞬方針が立たないかもしれないですが、Kは0〜25の時のみ考えればよく、暗号文も短いので全探索すればいいと思います。あるKのときに、"the","this","that"という単語…

問題リンク Treasure Hunt 解法 幾何問題です。 最初北を向いて原点にいます。(L,da)という対の入力がいくつか読み込んで、 自分が向いている方にLメートル進んでからda度向きを変えるということを繰り返します。 今いるところ(x,y)からa度の方向へLメートル…

問題リンク National Budget 解法 多倍長演算問題。大きさ80の配列を用意して・・・なんてしなくても BigIntegerという素敵なクラスがJavaにあるんでこれの恩恵を受けました。 桁数が８０を超えたら"overflow"を出さないといけないのでそれのチェックを忘れ…

超簡単な問題に対しても自分の解法を載せていく方針で行こうと思います。 簡単な問題でも他人の解法が気になるってこともあるし、簡単だからという理由で解法を紹介している記事が見つからず路頭に迷っているような方もいるかもしれないので。 あとJava使い…

問題リンク Sum of Integers 解法 0〜9のなかから異なるn個を選んで和がsになる組み合わせを答える問題。 数字を選ぶとき、小さい方の数字から、もしくは大きい方の数字から選ぶんだっていうルールを設ければ選ぶ数字の組み合わせが重複することがありません…

問題リンク English Sentence 解法 Mapを用意して、出現する文字列とその出現回数を格納します。 ただ、これをやるとボクシング変換とかそこらへんのものがごちゃごちゃ働いて遅いんですけど、問題のサイズが小さいので本問では大丈夫です。 （蛇足：問題の…

問題リンク Mode Value 解法 最頻する値を答える問題です。 入力された数字をカウントしていき、同時にカウントの最大値を記録。 入力が終わったら数字を小さい順にみていって出現回数が最頻だったら出力、で勝ちです。 ソース

問題リンク What day is today? 解法 カレンダー問題です。 C++とかの言語にあるかは知らないですが、JavaにはCalendarクラスが用意されているので瞬殺できます。 ただ、月数は1〜12じゃなくて0〜11で表現される、などといった注意点があるのでそこは頑張っ…

問題リンク Dropping Ink 解法 インクがしみる量は最大でも１２程度なので、インクの大きさに応じた移動量ベクトルを用意してしまうのが手っ取り早い解法でしょうか。 自分はこれまた面倒なことして解いています。 メソッド f(x, y, z)：座標(x,y)が座標(dx,…

問題リンク Hit and Blow 解法 Aさんの４つの数字で表れた場所を記録します。 Bさんの入力は１つずつ見ていき、 Bさんの数字がAさんにも表れているかつ場所が同じならHit++ そうでなければblow++ しています。ルールに忠実にカウントしてるだけです。 ソース

問題リンク Physical Experiments 解法 物理問題です。鉛直投げ上げ投げさげ、水平投射、斜方投射あたりは押さえておいて損はないと思います。 玉をN階から静かに落とし、玉が地面にぶつかるときの速度がVを初めて超えるのはNがいくつのときかを答えます。 …

問題リンク Circles Intersection 解法 幾何問題。２つの円の中心の距離Dと半径Ra, Rbを操って解く問題です。 (1) Ra + Rb (2) D + Ra (3) D + Rb (4) どれでもないなら円周は交点を１つか２つ持って、交わる の場合分けで解きました。たしか(2)と(3)のとこ…