【書評】Amazon Web Services 基礎からのネットワーク&サーバー構築

インフラエンジニアとして、AWSくらいちゃんと触れるようになっておこうかなあと思って手に取った一冊。

結果として、とりあえずAWSで簡単な環境を作って動かしてみるという目的にぴったりな一冊でした。

向いている人

  • インフラの知識が少ないフロントエンジニアでAWSを触ってみたい人
  • オンプレミスでの経験があるインフラエンジニアでこれからAWSに取り組もうとしている人

書かれていること

AWSにおける基本的な機能である、VPC、サブネット、ルートテーブル、EC2、NATなどの知識が一通り学べます。

流れとしては、VPC内にパブリック用サブネットとプライベート用サブネット作成し、それぞれにWEBサーバとDBサーバのノードを構築。

WEBサーバにApache、DBサーバにはMySQLをインストールして、最終的にはWordpressの環境を構築してインターネットに公開するまでが行えます。

ハンズオン形式になっていて、作業自体は半日もあれば終わってしまうと思います。

所々に、TCP/IPやDNSといったインフラ周りの説明も盛り込まれていますが、インフラの知識が少ないフロントエンジニア向けの内容なので、既にわかっているというインフラエンジニアの方であれば読み飛ばして問題無いと思います。

全体通してAWSの無料枠で試せる内容になっているので、まさに初めてAWSを触ってみるといった人にお勧めできる本です。

書かれていないこと

実際にシステムを運用する上で必要になるパフォーマンスや構成の考え方、ELB、Route53、VPNなどの話は書かれていません。

なので、実践でAWSを活用するためには本書で得た知識を元に追加で勉強が必要になると思います。

まとめ

個人的にはとりあえずAWS触ってみたい、という目的には非常にあった本だったと思います。

また、本書の内容とは直接関係ないですが、クラウドになることで、これまでのようにサーバ、ネットワークなど個々の専門家といった区切りでは無く、インフラ全体の知識が求められるようになると感じました。


radikoのタイムフリー&エリアフリーを保存する(ruby版)

以前にradikoのタイムフリー&エアフリーを保存するする手順を書きましたが、今回はRuby版です。

radikoのエリアフリーを保存する方法
以前、radikoのタイムフリーを保存する方法を書きましたが、今回はエリアフリー対応版です。 基本的な手順は同じですが、異なるのは最初...

環境

  • macOS Mojava
  • ruby 2.5
  • 事前にffmpegとswftoolsを導入しておく
  • httpclient gemをインストールしておく

事前準備

myplayer-release.swfのダウンロード

認証のための事前準備としてswfファイルをダウンロードする

$ curl -O http://radiko.jp/apps/js/flash/myplayer-release.swf

swfファイルから画像ファイルを取り出す

認証にキーとなる画像ファイルをswfextractで取り出す

$ swfextract myplayer-release.swf -b 12 -o authkey.png
$ ls authkey.png
authkey.png

実行方法

タイムフリー(エリア内)

$ ruby rec_radiko.rb --sid=LFR --ft=201812190000 --to=20181219010000

エリアフリー(mailとpassにプレミア登録している情報を設定する)

$ ruby rec_radiko.rb --sid=MBS --ft=201812190000 --to=20181219010000 --mail=hoge@example.com --pass=password

rec_radiko.rb

require 'optparse'
require 'date'
require 'httpclient'

M4A_FILE = DateTime.now.strftime('%Y%m%d%H%M%S') + ".m4a"

LOGIN_URL = 'https://radiko.jp/ap/member/login/login'
LOGIN_CHECK_URL = 'https://radiko.jp/ap/member/webapi/member/login/check'
AUTH1_URL = 'https://radiko.jp/v2/api/auth1_fms'
AUTH2_URL = 'https://radiko.jp/v2/api/auth2_fms'

params = ARGV.getopts("", "sid:", "ft:", "to:", "mail:", "pass:")

if params["sid"] == nil || params["ft"] == nil || params["to"] == nil
    puts "Usage: ruby rec_radiko.rb --sid=<station id> --ft=<start time> --to=<end time> --mail=<mail address --pass=<password>"
    exit
end

sid = params["sid"]
ft = params["ft"]
to = params["to"]

PLAYLIST_URL = "https://radiko.jp/v2/api/ts/playlist.m3u8?station_id=#{sid}&l=15&ft=#{ft}&to=#{to}"

mail = params["mail"]
pass = params["pass"]

client = HTTPClient.new

header = { \
    'Content-Type' => 'application/x-www-form-urlencoded', \
    'Referer' =>  'http://radiko.jp/', \
    'Pragma' => 'no-cache', \
    'User-Agent' =>  'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_4) AppleWebKit/603.1.30 (KHTML, like Gecko) Version/10.1 Safari/603.1.30', \
    'X-Radiko-Device' => 'pc', \
    'X-Radiko-App-Version' =>  '4.0.0', \
    'X-Radiko-User' =>  'test-stream', \
    'X-Radiko-App' => 'pc_ts' \
    }

# premium login
if mail != nil && pass != nil
    res = client.post(LOGIN_URL, {'mail' => mail, 'pass' => pass}, header)
    res = client.get(LOGIN_CHECK_URL, nil, header)
    if HTTP::Status.successful?(res.code) != true
        puts "Login failed"
        exit 1
    end
    puts "Login Succeed"
end

# Authentication 1
res = client.post(AUTH1_URL, nil, header)
if HTTP::Status.successful?(res.code) != true
    puts "Auth1 failed"
    exit 1
end
puts "Auth1 Succeed"

# X-Radiko-AuthToken が大文字の場合と小文字の場合があるため両方に対応
if res.headers['X-Radiko-AuthToken'] != nil
    header['X-Radiko-Authtoken'] = res.headers['X-Radiko-AuthToken']
elsif res.headers['X-RADIKO-AUTHTOKEN'] != nil
    header['X-Radiko-Authtoken'] = res.headers['X-RADIKO-AUTHTOKEN']
else
    puts "X-Radiko-AuthToken not found"
    exit 1
end
    
header['X-Radiko-Partialkey'] = `dd if=authkey.png ibs=1 skip=#{res.headers['X-Radiko-KeyOffset']} count=#{res.headers['X-Radiko-KeyLength']} 2>/dev/null | base64`.chomp

# Authentication 2
res = client.post(AUTH2_URL, nil, header)
if HTTP::Status.successful?(res.code) != true
    puts "Auth2 failed"
    exit 1
end
puts "Auth2 Succeed"

# ffmpegで保存
ffmpeg = "ffmpeg \
-content_type 'application/x-www-form-urlencoded' \
-headers 'Referer: http://radiko.jp/' \
-headers 'Pragma: no-cache' \
-headers 'X-Radiko-AuthToken: #{header['X-Radiko-Authtoken']}' \
-user_agent 'User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_4) AppleWebKit/603.1.30 (KHTML, like Gecko) Version/10.1 Safari/603.1.30' \
-i '#{PLAYLIST_URL}' \
-vn -acodec copy -bsf aac_adtstoasc #{M4A_FILE}"

`#{ffmpeg}`

CentOS7でApache+PassengerのRails本番環境を構築する手順

Apache + PassengerでのRails本番環境を作成する手順についてまとめました。

前提

  • Vagrant のCentOS7.5イメージを利用する
  • Rails のアプリケションはgithub等のリモートリポジトリから取得する
  • Vagrant + Virtual Boxはインストール済みとする

環境

  • CentOS 7.5(Vagrant Box)
  • Ruby 2.5.3 (rbenv)
  • Rails 5.2.2
  • DBはMysql

手順

Vagrant環境構築

ホストOSの任意のディレクトリでCentOS7.5の仮想環境を構築します

$ vagrant init centos/7

Vagrantfileの以下の部分のコメントアウトを外し、ホストOSの8080番ポートをゲストOSの80番ポートにフォワードするようにします。

config.vm.network "forwarded_port", guest: 80, host: 8080, host_ip: "127.0.0.1"

仮想環境を起動してログインします。

$ vagrant up
$ vagrant ssh

CentOS7.5の構成

OSを更新します。

$ sudo yum -y update

SELinuxを無効化します。

/etc/selinux/configのSELINUXをdisabledにします。

SELINUX=disabled

OSを再起動します。

$ sudo reboot

rbenv で Ruby をインストール

まずはrbenvのインストールに必要な各種パッケージをインストールします。

$ sudo yum -y install git-all openssl-devel readline-devel sqlite gcc gcc-c++

続いて、rbenvをインストールします。

$ git clone git://github.com/sstephenson/rbenv.git ~/.rbenv
$ git clone git://github.com/sstephenson/ruby-build.git ~/.rbenv/plugins/ruby-build
$ echo 'export PATH="$HOME/.rbenv/bin:$PATH"' >> ~/.bashrc
$ echo 'export PATH="$HOME/.rbenv/plugins/ruby-build/bin:$PATH"' >> ~/.bashrc
$ echo 'eval "$(rbenv init -)"' >> ~/.bashrc
$ echo 'gem: --no-ri --no-rdoc' > ~/.gemrc
$ source ~/.bashrc
$ rbenv --version
rbenv 1.1.1-39-g59785f6

rbenvがインストールできたら、Rubyをインストールします。

バージョンは、公開しようとしているRailsアプリケーションが指定しているバージョン(2.5.3)に合わせます。

$ rbenv install 2.5.3
$ rbenv global 2.5.3
$ ruby -v
ruby 2.5.3p105 (2018-10-18 revision 65156) [x86_64-linux]

bundlerもあわせてインストールします。

$ gem install bundler
$ bundle version
Bundler version 1.17.2 (2018-12-11 commit 43e950846)

Apacheのインストール

Apacheをインストールし、自動起動の設定を行います。

$ sudo yum -y install httpd httpd-devel curl-devel apr-devel apr-util-devel
$ sudo systemctl enable httpd

Passengerのインストール

Passengerをインストールします

$ sudo yum install -y epel-release pygpgme curl
$ sudo curl --fail -sSLo /etc/yum.repos.d/passenger.repo https://oss-binaries.phusionpassenger.com/yum/definitions/el-passenger.repo
$ sudo yum install -y mod_passenger

node.jsのインストール

Rails に必要なJavaScriptランタイムとしてnode.jsをインストールします。

なお、node.jsはEPELリポジトリから取得するため、Passengerのインストールの最初に実施しているepel-releaseのインストールが前提となっていますので注意してください。

$ sudo yum install -y nodejs

Mysqlのインストール

Mysqlをインストールします。

$ sudo yum install -y mariadb-server mariadb-devel
$ sudo systemctl enable mariadb
$ sudo systemctl start mariadb
$ sudo mysql_secure_installation

本番DBの作成

本番環境用のデータベースと接続ユーザを作成します。

以下の情報はRailsアプリケションのconf/database.yamlの内容と合わせます。

  • データベース名: prodution_db
  • 接続ユーザ: prod_user
  • パスワード: Password
$ mysql -u root -p

MariaDB [(none)]> CREATE DATABASE production_db DEFAULT CHARACTER SET utf8;

MariaDB [(none)]> GRANT ALL PRIVILEGES ON production_db.* TO prod_user@localhost IDENTIFIED BY 'Password' WITH GRANT OPTION;

Rails環境を構築

いよいよ、Railsの環境を構築します。

ここでは、github等のリモートリポジトリからファイルを取得する前提としています。
(SSH接続の設定については割愛します)

$ git clone <リモートリポジトリ>

以降、アプリケーションのディレクトリを rails_app とします。

アプリケーションのディレクトリを/var/www配下に移動します。

$ sudo mv rails_app /var/www

bundle install でRailsと必要なgemをインストールします。

なお、ここではpathを指定して、gemをローカルにインストールすることにします。

$ cd /var/www/rails_app
$ bundle install --path vendor/bundler
$ bundle exec rails -v
Rails 5.2.2

Credential情報の管理に使うキー情報をconfig/master.keyに設定します。

Rails5.2が生成する.gitignoreでは/config/master.keyがデフォルトで指定されているため master keyはリモートリポジトリに含まれません。

そのため、rails ini した環境のmaster.keyの内容を設定します

$ vi config/master.key

config/database.yamlの内容を先ほど作成したmysqlの環境と合わせます。

production:
  adapter: mysql2
  encoding: utf8
  database: production_db
  pool: 5
  username: prod_user
  password: Password

マイグレーションを行い、本番環境のデータベースを作成します。(必要に応じてdb:seedで初期データの登録も実施します)

$ bundle exec rails db:migrate RAILS_ENV=production
$ bundle exec rails db:seed RAILS_ENV=production

アセットのプリコンパイルを行います。

$ bundle exec rails assets:precompile

Apacheの設定

/etc/httpd/conf.d/passenger.conf を修正します。

  • PassengerRuby をrbenvのパスに変更
  • ServerName をlocalhostに変更
  • DocumentRoot と Directory をRailsアプリケーションのpublic フォルダに設定
<IfModule mod_passenger.c>
   PassengerRoot /usr/share/ruby/vendor_ruby/phusion_passenger/locations.ini
   PassengerRuby /home/vagrant/.rbenv/shims/ruby
   PassengerInstanceRegistryDir /var/run/passenger-instreg
</IfModule>

<VirtualHost *:80>
   ServerName localhost
   # Be sure to point to 'public'!
   DocumentRoot /var/www/rails_app/public
   <Directory /var/www/rails_app/public>
      # Relax Apache security settings
      AllowOverride all
      Require all granted
      # MultiViews must be turned off
      Options -MultiViews
   </Directory>
</VirtualHost>

設定を反映させるために、httpdを再起動します。

$ sudo systemctl restart httpd

動作確認

ホストOSのブラウザから http://localhost:8080 にアクセスし、railsアプリケーションにアクセスし正常に動作すれば成功です。

なお、エラーが発生した場合は、Apacheのエラーログ(/var/log/httpd/error_log)等を確認して切り分けていくことになります。


AtCoder BC074 D: Restoring Road Network

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

ワーシャルフロイド法をベースにしてその考え方を応用することで解けます。

問題を「道路の構造が存在するかどうか」と「存在する道路の長さの和が最小となるようなもの」の二つに分けて考えます。

  • 道路の構造が存在するかどうか

表Aが「都市間の道路に沿った最短距離を表した表」なので、表Aに対してワーシャルフロイド法を適用し、表内の値が更新されることがあった場合に表Aは矛盾することになります。

例えば、(iからjへの距離)> (iからkへの距離)+(kからjへの距離)のような場合に、表Aはそもそも矛盾することになります。

よってそのような組み合わせが一つでもあれば、’-1’を出力して終了すれば良いです。

  • 存在する道路の長さの和が最小となるようなもの

どのような場合に道路が存在しないといけないかを考えます。

表Aは各都市間の最短経路を表しているので、iからjへの経路を考える場合、

(iからjへの距離)= (iからkへの距離)+(kからjへの距離)

のようなkが存在した場合、k経由で迂回しても距離は変わらないので、iからjへの道路は不要ということになります。

よって、表のサイズと同じ表を用意しておき、道路が必要か不要かをtrue/falseなどで記憶しておき、最後にtrueな経路の距離だけ加算すればよいです。

実装

#include<iostream>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define MOD 1000000007

using namespace std;

typedef long long int ll;

const ll INF=(ll)1e18;

int main(){
    int N;

    cin >> N;

    ll a[N][N];
    bool f[N][N];

    REP(i,N)REP(j,N)cin >> a[i][j];
    REP(i,N)REP(j,N)f[i][j] = true;

    REP(k,N)REP(i,N)REP(j,N){
        if(a[i][k] + a[k][j] < a[i][j]){
            cout << -1 << endl;
            return 0;
        }else if(a[i][k] + a[k][j] == a[i][j] && i != k && k != j){
            f[i][j] = false;
        }
    }

    ll ans = 0;
    REP(i,N)REP(j,N){
        if(f[i][j])ans+=a[i][j];
    }

    cout << ans / 2 << endl;
}

AtCoder BC074 C: Sugar Water

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

質量の合計の最大値が3000gに対して、水は100g単位、砂糖は1g単位です。

なので、全ての組み合わせを試したとしても間に合います。

よって、4重ループで全探索すれば解けます。

実装

A, B, C, D, E, F = gets.chomp.split(" ").map(&:to_i)

limit = E.to_f / (100 + E)

tmp = 0
max_s =0
max_sw = 0
for a in 0..(F/100/A)
    for b in 0..((F-100*a*A)/100/B)
        next if a + b == 0
        for c in 0..((F-100*a*A-100*b*B)/C)
            for d in 0..((F-100*a*A-100*b*B-c*C)/D)
                sw = c*C+d*D+a*A*100+b*A*100
                s = c*C+d*D
                n = s.to_f / sw
                break if n > limit
                if tmp < n
                    tmp = n
                    max_s = s
                    max_sw = sw
                end
            end
        end
    end
end
if max_s > 0
    puts "#{max_sw} #{max_s}"
else
    puts "#{100*A} #{max_s}"
end

AtCoder Beginner Contest 113 参戦記

今度こそは水色へ、と意気込んだABC113。

C完でDも解法はある程度わかったのですが、実装で手間取って例題を通す前に時間切れとなりました。

うーん、水色目前で停滞中です。

A – Discount Fare

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

X + (Y/2) を出力するだけ

実装

x,y=gets.chomp.split.map(&:to_i)
puts x+y/2

B – Palace

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

各Hi毎に平均気温とA度との差の絶対値を計算し、それが最小の時のiを出力すればよい。

実装

n=gets.to_i
t,a=gets.chomp.split.map(&:to_i)
h=gets.chomp.split.map(&:to_i)

m=Float::INFINITY
ans=0
h.each_with_index do |v, i|
    mm = (a-(t-v*0.006)).abs
    if mm < m
        ans = i+1
        m = mm
    end
end
puts ans

C – ID

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

各市を読み込みながら、各県に誕生年を振り分けていく。

全て読み込んだら、各県毎の誕生年をソートして各市の順番(x番目)を決定する。

最後に各市毎に認識番号を出力していく。

ということで、考え方自体はそんなに難しくないが、誕生年の順番をどのように知るかにちょっと工夫が必要。

実装

実装としては、配列とハッシュを使って以下のようにした。

まず、各県ごとに誕生年を配列に格納してから最後にソートする。

その後、配列を先頭から見ていき、誕生年をキー、順番を値とするハッシュに格納する。

認識番号を決める際はこのハッシュを使って誕生年から順番を取得するようにする。

n,m=gets.chomp.split.map(&:to_i)
p = []
y = []

py = Array.new(n+1).map{Array.new()}

m.times do |i|
    pp, yy = gets.chomp.split.map(&:to_i)
    p << pp
    y << yy

    py[pp] << yy
end

ph = Array.new(n+1).map{Hash.new()}
py.each_with_index do |v, i|
    v.sort!
    v.each_with_index do |vv, j|
        ph[i][vv] = j+1
    end
end

0.upto(m-1) do |i|
    printf("%06d%06d\n", p[i], ph[p[i]][y[i]])
end

D – Number of Amidakuji

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

あと一歩で解けなかったD問題。

取りかかってから10分ぐらいで動的計画法を使うっていうのは分かったんだけど、実装に手間取って例5を通すことが出来なかった。

この問題のポイントは、動的計画法の漸化式をどうたてるか、と、各縦線の数に対して有効な横線の引き方が1段について何通りあるか、です。

  • 漸化式の考え方

i番目の行まで横線が引き終わっている時にj列目に存在するときの組み合わせをDP[i][j]とします。

すると、i+1番目でj列にいく組み合わせは

DP[i+1][j] = DP[i][j-1] x (j-1とjの間に線を引くときの組み合わせ)+ DP[i][j] x (j-1とjとj+1の間に線を引かない組み合わせ)+ DP[i][j+1] x (jとj+1の間に線を引くときの組み合わせ)

で求められます。

例を使って説明します。

i+1番目で4列目にいけるのは、i番目で3列目、4列目、5列目にいる場合です。

3列目にいる場合は、3列目と4列目の間に横線を引く必要があります。この場合、それ以外の場所については、左側は1、2列目の間、右側は5、6列目の間の横線の引き方の組み合わせとなります。

4列目にいる場合は、3列目と4列目、及び、4列目と5列目の間に横線を引いてはいけません。この場合、それ以外の場所については、左側は1、3列目の間、右側は5、6列目の間の横線の引き方の組み合わせとなります。

5列目にいる場合は、4列目と5列目の間に横線を引く必要があります。この場合、それ以外の場所については、左側は1、3列目の間、右側はこれ以上横線は引けません。

  • 有効な横線の引き方

では、あみだくじとして有効な横線の引き方をどう算出するかです。

これも漸化式の考え方で求めることが出来ます。

縦棒の数がi本の時の一行分の線の引き方をSiとします。

このとき、漸化式は以下のようになります。

これは、i列目とi+1列目に横棒を引く場合はi-1列目とi列目に横棒は引けないのでそれより左側の組み合わせはSi-1通りとなり、i列目とi+1列目に横棒を引かない場合はそれより左側の組み合わせはSi通りになるためです。

ちなみにこれはフィボナッチ数列になります。なお、今回の問題は縦棒は8本までしかないので、数列はハードコードしてしまってます。

実装

以下の実装では、左端と右端は場合分けしていますが、両端に0の列を追加すればもう少し綺麗なるかも。

h,w,k=gets.chomp.split.map(&:to_i)
dp=Array.new(h+1).map{Array.new(w)}

MOD = 1000000007

nn = [1,2,3,5,8,13,21,34]

dp[0][0] = 1
1.upto(w-1) do |i|
    dp[0][i] = 0
end

if w == 1
    puts 1
    exit
end

1.upto(h) do |i|
    0.upto(w-1) do |j|
        dp[i][j] = 0
        if(j==0)
            dp[i][j] += dp[i-1][j] * nn[w-2]
            dp[i][j] += dp[i-1][j+1] * nn[[0,w-3].max]
        elsif(j==w-1)
            dp[i][j] += dp[i-1][j] * nn[w-2]
            dp[i][j] += dp[i-1][j-1] * nn[[0,w-3].max]
        else
            n = nn[[0,j-2].max]
            n *= nn[[0,w-2-j].max]
            dp[i][j] += dp[i-1][j-1] * n

            n = nn[j-1]
            n *= nn[[0,w-2-j].max]
            dp[i][j] += dp[i-1][j] * n

            n = nn[j-1]
            n *= nn[[0,w-3-j].max]
            dp[i][j] += dp[i-1][j+1] * n
        end
        dp[i][j] = dp[i][j] % MOD
    end
end

puts dp[h][k-1] % MOD

結果

Cまでは順調だったんですが、Dで躓いてしまいました。

しかも、Dは動的計画法の漸化式まではある程度思いついたんですが、結局実装しきれませんでした。

とはいえ、動的計画法は苦手分野だったので、途中まで書けただけでも成長したかなという感じです。

いずれにせよ、水色手前でなかなか上がれません。

やはり400点問題は確実に解けるようにしたいところですね。


AtCoder BC079 D: Wall

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

各数字を1に書き換えるコストが最小になるようにし、その合計を出せば良い。

「1に書き換える最小コスト」=「1への最短距離」と考えることが出来るので、事前にワーシャルフロイド法などで最短距離を求めておけば、あとは各Aijについて加算していけばよい。

実装

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstdlib>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define MOD 1000000007

using namespace std;
 
typedef long long int ll;

const ll INF=(ll)1e18;

int main(){
    int H,W;

    cin >> H >> W;

    int c[10][10];

    REP(i,10)REP(j,10){
        int tmp;
        cin >> tmp;
        c[i][j] = tmp; 
    }

    REP(i,10)REP(j,10)REP(k,10){
        c[j][k] = min(c[j][k], c[j][i] + c[i][k]);
    }

    int ans = 0;
    REP(i,H)REP(j,W){
        int a;
        cin >> a;
        if(a != -1 && a != 1){
            ans += c[a][1];
        }
    }

    cout << ans << endl;

}

AtCoder BC079 C: Train Ticket

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

演算子の場所は3カ所で+-の2通りしかない。そのため、全パターン試しても 通りで十分に速い。

全パターン試す実装はビット演算で実施。

実装

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
#include<string>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define MOD 1000000007

using namespace std;
 
typedef long long int ll;

const ll INF=(ll)1e18;

int main(){
    string str;
    int A,B,C,D;
    cin >> str;
    A = stoi(str) / 1000;
    B = stoi(str) / 100 % 10;
    C = stoi(str) / 10 % 10;
    D = stoi(str) % 10;
 
    REP(i,8){
        int tmp = A;
        char op1,op2,op3;
        if(i & 1){
            tmp += B;
            op1 = '+';
        }else{
            tmp -= B;
            op1 = '-';
        }
        if(i & 2){
            tmp += C;
            op2 = '+';
        }else{
            tmp -= C;
            op2 = '-';
        }
        if(i & 4){
            tmp += D;
            op3 = '+';
        }else{
            tmp -= D;
            op3 = '-';
        }
        if(tmp == 7){
            cout << A << op1 << B << op2 << C << op3 << D << "=7" << endl;
            return 0;
        }
    }
}

AtCoder Tenka1 Programmer Beginner Contest 参戦記

ABCやARCと違うコンテストに参加するのは今回が初でした。

KLabさん主催とのことですが、ほぼいつもの問題の感じと同じでしたね。

今度こそは水色に、と意気込んだのですが、Cの考察不足で最後までWAが残ってしまいまたもや撃沈でした。。。

A – Measure

問題

https://beta.atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_a

解法

入力文字列の長さで分岐させるだけ

実装

s=gets.chomp
if s.size == 3
    puts s.reverse
else
    puts s
end

B – Exchange

問題

https://beta.atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_b

解法

二人の操作を愚直にシミュレートしていくだけ

実装

a,b,k=gets.chomp.split.map(&:to_i)
k.times do |i|
    if i % 2 == 0
        if a%2 == 1
            a -= 1
        end
        b += a/2
        a /= 2
    else
        if b%2 == 1
            b -= 1
        end
        a += b/2
        b /= 2
    end
end

printf("%d %d\n",a,b)

C – Align

問題

https://beta.atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_c

解法

整数の数Nはなので、全て列挙する方法だとぜんぜん間に合いません。

よってどういう並びが適切かを考えることになります。

例えば、1、3、5という3つの整数を並べる場合を考えます。

この場合、1 3 5 と3つを昇順に並べるのは、1 5 という並びと等価です。

なぜならば、1 3 5 は (5-3) + (3-1) = 4 であり、1 5は (5-1) = 4 となるため、真ん中に3を入れる意味が無くなります。これは降順についても同じです。

よって、並べ方のうち3つ以上が昇順(または降順)で現れるものは最適ではありません。

そのため、作る列をsで表すとすると、 のような凸凹の並びになります。

この際、整数の数が偶数か奇数かで分けて考える必要があります。

そこで実際にNが偶数の場合として6を考えてみます。

すると、 と が考えられます。

それぞれの計算結果は

となりますが、両者は並び順が異なるだけなので同じとみなせます。

前者を最大にすることを考えた場合、2倍で加算されるやにはなるべく大きい値、2倍で減算されるやにはなるべく小さい値を当てはめるべきです。

よって、事前に与えられた整数をソートしておき、大きい方の半分は2倍して加算、小さい方の半分は2倍して減算していけばよいことがわかります。ただし、中央値の2つの数については1倍のままにする必要があります。

次にNが奇数の場合として5を考えてみます。

今度は、 と が考えられます。

それぞれの計算結果は

となり、 両者は異なります。これは、並びの両端に大きい数を配置するか小さい数を配置するかの違いになります。(本番では2パターンあることに気づかずに片方だけ実装してしまい見事にWAをくらいました。。。)

よって、奇数の場合は両方のケースを計算してみて、結果が大きい方を解とすればよいです。

実装

n=gets.to_i
a = []
n.times do
    a << gets.to_i
end
a.sort!

ans = 0
if n % 2 == 0
    (n/2+1).upto(n-1) do |i|
        ans += a[i] * 2    
    end

    ans += a[n/2]
    (0).upto(n/2-2) do |i|
        ans -= a[i] * 2    
    end
    ans -= a[n/2-1]
else
    (n/2+1).upto(n-1) do |i|
        ans += a[i] * 2    
    end

    (0).upto(n/2-2) do |i|
        ans -= a[i] * 2    
    end
    ans -= a[n/2]
    ans -= a[n/2-1]

    tmp = ans
    ans = 0

    (n/2+2).upto(n-1) do |i|
        ans += a[i] * 2    
    end
    ans += a[n/2]
    ans += a[n/2+1]

    (0).upto(n/2-1) do |i|
        ans -= a[i] * 2    
    end

    ans = tmp if tmp > ans

end
puts ans

D – Crossing

問題

https://beta.atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_d

解法

満たすべき条件の対称性や入力例1の結果を見る限り、部分集合に含まれる整数の数は全て等しいと予想されます。

そこで、試しに部分集合のサイズが3になるケースを考えてみます。

すると部分集合の組は {1, 2, 3} {1, 4, 5} {2, 4, 6} {3, 5, 6} となります。この場合、Nは6になります。

さらにサイズが4になるケースを考えてみます。

{1, 2, 3, 4} {1, 5, 6, 7} {2, 5, 8, 9} {3, 6, 8, 10} {4, 7, 9,10} となります。この場合、Nは10になります。

ここで、部分集合の組の数kは部分集合のサイズより1大きい点に気づくかどうかがポイントです。

例えば {1, 2, 3, 4}を基点に考えた場合、他の部分集合との積は必ず1つしかなく、かつ、各整数は各部分集合のうち2つにしか含まれないため、他の部分集合は4つしか作れません。

どの整数も部分集合の組の2つにしか含まれないため、 となります。

よって、この条件を満たさないNが与えられた場合は、解は NO となります。

では次に、具体的な組み合わせを列挙する方法ですが、本番ではここでつまずいてしまいました。。。

以下のように考えます。

を考えた場合、これは必ずユニークな値になります。

よって、iとjを2重ループでまわして組み合わせを列挙していき、そこに整数を1つずつ当てはめていきます。その際に、各部分集合にその整数を割り当てていき、最後に各部分集合に含まれる値を出力すればよいです。

実装

n=gets.to_i

k = 0
1.upto(1000) do |i|
    if i * (i-1) / 2 == n
        k = i
        break
    elsif i * (i-1) / 2 > n
        break
    end
end

if k == 0
    puts "No"
    exit
else
    puts "Yes"
end

s = 1
ans = []
1.upto(k-1) do |i|
    (i+1).upto(k) do |j|
        ans[i] = [] if ans[i] == nil
        ans[j] = [] if ans[j] == nil
        ans[i] << s
        ans[j] << s
        s += 1
    end
end
puts k
1.upto(k) do |i|
    printf("%d ", ans[i].size)
    puts ans[i].join(" ")
end

感想

400点のCはほぼ解法がわかっていたのに、もう一歩考察が足りずにWAとなってしまいました。

500点のDも考え方はあっていたのですが、組み合わせの列挙で躓いてしまった。

ということで、またしても水色手前で足踏み状態です。


AtCoder BC073 D: joisino’s travel

問題

https://beta.atcoder.jp/contests/abc073/tasks/abc073_d

解法

訪れる町の数が最大で8のため、訪れる順番の組み合わせは最大でも8!(=40320)通りです。

町の数は最大200であり、事前にワーシャルフロイド法(計算量はO(N3))等でそれぞれの町の間の最短距離を求めておけば、全ての組み合わせを試しても十分に間に合います。

実装

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
#include<string>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define MOD 1000000007

using namespace std;
 
typedef long long int ll;

const ll INF=(ll)1e18;

ll d[201][201];

int main(){
    int N, M, R;
    cin >> N >> M >> R;
    vector<int> r;

    REP(i,R){
        int tmp;
        cin >> tmp;
        r.push_back(tmp);
    }
    
    sort(r.begin(),r.end());

    REP(i,N+1)REP(j,N+1)d[i][j] = INF;

    REP(i,M){
        int a,b,c;
        cin >> a >> b >>c;
        d[a][b] = c;
        d[b][a] = c;
    }


    REP(i,N+1)REP(j,N+1)REP(k,N+1){
        d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
    }

    ll ans = INF;
    do {
        ll tmp = 0;
        REP(i,R-1){
            tmp += d[r[i]][r[i+1]];
        }
        ans = min(ans,tmp);
    } while (std::next_permutation(r.begin(), r.end()));

    cout << ans << endl;

}