' P '

whatever I will forget

復習すべき問題たちまとめ

AtCoder

とりあえずランクBの問題はスラスラ解けるようになりたい。
随時追加方式

計算量考慮

10進数

文字列結合

  • B - OddString
    文字列の結合をloop内で行う場合にはStringBuilderを使わないとメモリ制限が超過すると思っておいたほうがいい。
    あと、charで実施する場合は基本中の基本だと思われるが、char型値の文字列結合もしっかりと押さえておかないと。
    Java StringBuilder vs String Concatenate パフォーマンスの違い - ' P '
    Java charの結合 - ' P '

    6/4 追記

    charの結合で一旦提出してみたら、見事にMLEが。 String out += "" + s[i];みたいにした。
    やはり素直にStringBuilderを使うほうがよい。

Bucket Sort

  • B - すぬけ君の塗り絵 2 イージー
    問題固有のロジックを考える必要があるけれど、単純に行いたいことは何か？を考えると塗りつぶされていない部分の面積を求める = 面積を求めるための幅と長さを求めるになるはず。
    それを行うためのロジックを考えるような問題だと思う。Bだから面積分の二重arrayを使って塗り潰されたされた部分を把握する、という方法でも全くよさそうだけど、コードがどうしても長くなると思われる。
    ちなみに、縦*横がどちらもマイナスだとプラスになってしまうことは要注意。。
    Algorithm Bucket Sort - ' P '

連想配列

  • B - Two Colors Card Game
    下記記事でドヤ顔して書いてましたけど、Set/HashSetを用いたCollections.frequency()は使えるようになっておきたいところ。引数いつも間違えるけど、(list, str)です。listの中のstrの頻出をみるって感じで覚えようっと。

    6/4追記（やり方忘れてた）

    あとはMap/HashMapの使い方やループの方法、値の取得までは覚えておきたい
    Java HashMap（連想配列） - ' P '

グリッド系

集合の要素の個数（数学系）

  • B - Between a and b ...
    入力される値が最大18桁なので、まず普通にloopさせて回答を得ることはできない。
    じゃあどうするか？ということなんですけど、数学的な式には無知すぎるので、こういう問題が出たら、こう解く、と覚えておくほかなさそう。
    例をずっとみていて、もしかしたら閃くかもだけど期待は薄い。
    もしAが0なら、b/x+1 を行う それ以外は、 b/x - (a-1)/x を行う
    これで回答は出せる...

    追記 6/5

    やはりちゃんと理解していないと再度同じ問題を解こうとしても、あれ？これどーするんだっけ...となりますね
    というわけで下記記事を書きました。理解してしまえばなんてことない問題です... (AtCoderの解説が数式アレルギーには難しすぎるんだよなあ...)
    集合の要素の個数 - ' P '

周期性やパターンを見つける系

累積和

1000000007系