takashi

AtCoder

AtCoder BC098 B: Cut and Count

問題 解法 文字列のサイズが最大でも100なので、全ての切断箇所のパターンで「どちらにも含まれる文字」の種類を数え上げれば解けます。 Rubyの場合、配列の「&」をとると共通部分が求められるので、実装は以下...
Mac

radikoのタイムフリーを保存する方法

先日、MacBookのOSをクリーンインストールした際、それまでradikoのタイムフリーの保存に使っていたradikoroの最新版がタイムフリーの保存機能を削除していたことに気づきました。 ループバック機能を使えば、再生しながら保存する...
AtCoder

AtCoder BC097 D: Equals

問題 解法 最初、貪欲に操作をシミュレートして解こうと思ったのですが、組み合わせが果てしなくあることに気づき早々に断念。 例題の解き方を眺めているうちに、各操作のグルーピングがポイントであることに気づきまし...
AtCoder

AtCoder BC097 C: K-th Substring

問題 解法 最初に問題を見たときは、長さ5000以下の文字列の部分文字列なんていっぱいあるし、これ本当に300点?って思ったのですが、Kが5以下に抑えられているので、高々Kまでの長さの部分文字列を全て列挙してしま...
AtCoder

AtCoder BC097 B: Exponential

問題 解法 bpがX以下になる組み合わせについて考えます。 これはbについては1〜X、pについては2〜Xの組み合わせが考えられ、これは2重ループのO(N2)で求めることが出来ます。 ただし、pについて...
AtCoder

AtCoder GC023 B: Find Symmetries

問題 解法 まず、初期状態で「よい盤面」なものについて考える。 例えば、N=3の場合、以下のような盤面が「よい盤面」である。 a b c b d e c e f これを右方向に1、下...
AtCoder

AtCoder GC023 A: Zero-Sum Ranges

問題 解法 最初に問題を見て、これ本当に200点?って思うくらい悩んだ。 とりあえず、累積和をとってみる。 例えば、サイズ4の数列:{a1 a2 a3 a4}の累積和を考える。 S1 = a1 ...
CodeJam

GCJ 2017 Qualification Round B: Tidy Numbers

問題 与えられた整数Nについて、N以下で数字が左から昇順に並ぶ最大の数を求める。 例えば、132であれば、129が132以下で数字が1,2,9と昇順に並ぶ最大の数となる。 方針 Nから順にデクリメントして条件...
AtCoder

AtCoder RC093 C: Traveling Plan

問題 解法 観光スポットに行かないケースを毎回計算していると、O(n^2)の計算量になってしまいます。 そこで以下のように考えます。 観光地が5カ所の場合、全ての観光地に行くケースの総距離は、 ...
AtCoder

AtCoder RC089 C: Traveling

問題 解法 時刻が1進む毎に上下左右のいずれかに1進めるので、次の場所に進むことを考えると ・次の場所との距離(X座標とY座標の差の絶対値の和)が時刻の差に等しい がまず最もシンプルな条件になります。 ...
タイトルとURLをコピーしました