問題 https://abc097.contest.atcoder.jp/tasks/arc097_b 解法 最初、貪欲に操作をシミュレートして解こうと思ったのですが、組み合わせが果てしなくあることに気づき早々に断念。 例題の解き方を眺めているうちに、各操作のグルーピングがポイントであるこ…
問題 https://abc097.contest.atcoder.jp/tasks/abc097_c 解法 最初に問題を見たときは、長さ5000以下の文字列の部分文字列なんていっぱいあるし、これ本当に300点？って思ったのですが、Kが5以下に抑えられているので、高々Kまでの長さの部分文字列を全て列…
問題 https://abc097.contest.atcoder.jp/tasks/abc097_b 解法 bpがX以下になる組み合わせについて考えます。 これはbについては1〜X、pについては2〜Xの組み合わせが考えられ、これは2重ループのO(N2)で求めることが出来ます。 ただし、pについては計算結果…
問題 https://agc023.contest.atcoder.jp/tasks/agc023_b 解法 まず、初期状態で「よい盤面」なものについて考える。 例えば、N=3の場合、以下のような盤面が「よい盤面」である。 a b c b d e c e f これを右方向に1、下方向に1ずらすと f c e c a b e b d …
問題 https://agc023.contest.atcoder.jp/tasks/agc023_a 解法 最初に問題を見て、これ本当に200点？って思うくらい悩んだ。 とりあえず、累積和をとってみる。 例えば、サイズ4の数列：{a1 a2 a3 a4}の累積和を考える。 S1 = a1 S2 = a1 + a2 S3 = a1 + a2 …
問題 与えられた整数Nについて、N以下で数字が左から昇順に並ぶ最大の数を求める。 例えば、132であれば、129が132以下で数字が1,2,9と昇順に並ぶ最大の数となる。 https://code.google.com/codejam/contest/3264486/dashboard#s=p1 方針 Nから順にデクリメ…
問題 https://arc093.contest.atcoder.jp/tasks/arc093_a 解法 観光スポットに行かないケースを毎回計算していると、O(n2)の計算量になってしまいます。 そこで以下のように考えます。 観光地が5カ所の場合、全ての観光地に行くケースの総距離は、 $$総距離 …
問題 https://arc089.contest.atcoder.jp/tasks/arc089_a 解法 時刻が1進む毎に上下左右のいずれかに1進めるので、次の場所に進むことを考えると ・次の場所との距離（X座標とY座標の差の絶対値の和）が時刻の差に等しい がまず最もシンプルな条件になります…
問題 https://arc091.contest.atcoder.jp/tasks/arc091_a 解説 実際にカードの反転処理をシミュレートして解こうとすると、計算量がO(N2)になってしまって現実的では無いです。 そのため、計算で解くことにします。 まず基本的な考え方です。最初はカードは…
問題 と - からなる文字列Sが与えられる。以下の操作を繰り返して、+ のみの文字列に変換するための最小回数を求める。 ・文字列Sのi番目までの+と-を反転させて、なおかつ、逆順にする。 例： 文字列Sが ++--+ でi=3の場合、++- を反転(--+）して逆順（+--…
問題 与えられた非負整数Nについて、N×1,N×2,…とNの倍数をあげていく。その数の10進表記で見た場合の桁が0～9全て出そろった時の最後の数を出力する。(そろわない場合は"INSOMNIA"を出力) 例：N=2の場合、2×1=2,2×2=4,…,2×35=70,…,2×44=88,2×45=90 で0～9が…
8月末で退職しました。 当面はサバティカルとして自分のスキルの見直しを行い、いずれは転職かフリーランスとしてお仕事したいと思っています。 そこで、当面の勉強の内容についてまとめてみました。 勉強の内容 目標はAIの分かるフルスタックエンジニア、と…
OS Xにrailsをインストールしようとしたら、初っぱなからつまずいたので対応をメモっておく。 環境 OS X EI Capitan 10.11.5 rbenv 1.0.0 ruby 2.2.5 問題点 rbenvで構成したruby 2.2.5 でrailsをインストールしようとしたところ、nokogiriのインストールで…
Windowsのリモートデスクトップで複数セッションを使っていた場合、コマンドでセッションを切り換えたい場合がある。 手順 最初に接続中のセッション一覧を確認する。query sessionというコマンドを使用する。 C:\Users\Administrator>query session セッシ…
Rubyのgemのhttpclientを使うと、Webサイトのスクレイピングなどが簡単に作れます。 以下のようにすることで、リクエスト送信時のUser-Agentも設定できます。 hc = HTTPClient.new('','XXXX') ただし、これだと実際のHTTPリクエストのUser-Agentには、以下の…
node.jsにもGoogle APIを使用するためモジュールが用意されています。 参考：google/google-api-nodejs-client インストールは、npmから行います。 $ npm install googleapis 次の例はGoogle+のユーザIDから名前を取得しています。 var googleapis = require…
最近はやりのnode.jsですが、まだまだ頻繁にバージョンアップが行われます。 毎回、makeして入れ直すのも面倒なので、nvmで手軽にバージョンを切り替えられるようにします。 nvmのインストールはgitで行います。 $ git clone git://github.com/creationix/nv…
さくらのレンタルサーバに標準でインストールされているRubyは1.8.7です。 そのため、1.9系を使用するには、ホームディレクトリ配下に自分でrubyをインストールすることになります。 ソースをFTPサーバから取得する % mkdir ~/local % mkdir~/loca/src % cd …
幕張のアウトレットモールへ買い物に行ったついでに寄りました。 以前に普通の野郎ラーメンは食べたことがあったので、今回は汁無し野郎に挑戦。 あいかわらず、ニンニクの臭いが強く食欲をさそう。 汁無しということで、混ぜそばに近い感じがした。 チャー…
2012/12/21、草月ホールで行われた「他力本願ライブ２」に参戦してきました。 他力本願ライブとは、ラジオ「山里亮太の不毛な議論」のリスナーが投稿したネタを芸人が披露するというもの。ネタには事前にお題となる「オチ」の一言が用意されており、リスナー…
Code Jam Japan 2011の決勝の問題Aを解いてみた。 ■ 考え方 ・最大になる組み合わせを総当たりで計算した場合、間違いなくLargeが解けないので、何らかの法則を見つける必要がある ・まずは三角形の面積について、基本的な計算方法を明確にする。隣り合うエ…
Lionに備えて、10.6.8 updateをインストールしたところ、何故かCPUファンが唸りだした。アクティビティモニタをチェックしたところ、DockのCPU使用率が100%に。何でDockが?ってことで、いろいろ調べたところ、Parallelsを使ってると起きる問題みたい。 現在…
RubygemsのOAuthライブラリを使用して、TwitterアプリのOAuth認証の登録を行う手順です。 ここで取得したトークン等を利用することで、OAuth認証を利用したTwitterクライアントを作成することが出来ます。 1. RubygemsのOAuthをインストールする $ sudo gem …
Blogを再開することにする。 一応、LifeHack的なことをメインに、技術的な話も織り交ぜていきたい。 今年の目標 体重を60kg以下にしてキープする ハーフマラソンを走る TOEIC900点 レビューBlogを2週間に一回更新する ピアノのレパートリーを3曲にする
