YKpages

ロボット分野で勉強したことのまとめ

CODE FESTIVAL 2015 C - 今日から始める競プロ日記

はじめに

chokudaiさんの今日の一問を解いてみた。

CODE FESTIVAL 2015 チーム対抗早解きリレー C

問題自体は簡単だけど、 早解きするとなると難しい。

C - 円周率

  • 一桁の整数Nが与えられる
  • そのNが円周率の何桁目に現れるか求めよ

atcoder.jp

解いた方針

円周率を50桁くらいコピペしただけ。

chokudaiさんのツイートを読んでなるほどなーとおもった。

コード

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string pi = "3141592653589793238462643383279502884197169399";
    char N;
    cin >> N;
    for(int i = 0; i < pi.size(); i++)
    {
        if(N == pi[i])
        {
            cout << i << endl;
            return 0;
        }
    }
}

おわりに

「問題を解けること」と「問題を早解きできること」は別物だなーということを改めて知った。

今日から始める競プロ日記のまとめページ

kato-robotics.hatenablog.com

AtCoder Beginner Contest 141 D - 今日から始める競プロ日記

はじめに

AtCoder Beginner Contest 141 ( ABC 141 ) に参加。

D問題でだいぶ躓いてしまったので、 解いた方針をまとめておく。

ちなみに、priority_queue の存在を忘れていて、 結局 multiset を使って解いた。

この記事では priority_queue を使ったほうでまとめる。

D - Powerful Discount Tickets

  • N個の品物を買う。
  • i番目の品物の値段はAi
  • 割引券をM枚持っている
  • 任意の品物に対して任意の枚数の割引券を使うことができる
  • 割引券一枚で半額(小数点以下切り捨て)
  • 最小いくらで買い物ができるか求めよ

atcoder.jp

解いた方針

方針はすぐに立った。

一番値段が高い品物から順々に割引券を使っていけば良い。

問題は実装方法。

一番大きい値段を知るために、 常に配列をソートした状態にしたいが、 愚直にやるとO(NM)になるはずだからダメ。

だからデータをどの型で扱うかを考える必要がある。

私はmultisetを使って解いたけど、 解説を読んだらpriority_queueを使うといいよって書いてあって、 「聞いたことある~」とちょっと悲しくなった。

コンテスト中にもっと早く気づきたかった。

cpprefjp.github.io

qiita.com

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main()
{
    // 入力
    ll N, M;
    cin >> N >> M;
    priority_queue<ll> pq; // ソートの状態でデータを保持
    for(int i = 0; i < N; i++)
    {
        ll a;
        cin >> a;
        pq.push(a);
    }
 
    // M回分、最大値を半分に
    for(int i = 0; i < M; i++)
    {
        ll maxv = pq.top() / 2LL;
        pq.pop();
        pq.push(maxv);
    }
 
    // 合計値を計算
    ll sum = 0;
    for(int i = 0; i < N; i++)
    {
        sum += pq.top();
        pq.pop();
    }
 
    // 解を出力
    cout << sum << endl;
    return 0;
}

おわりに

D問題までを早解きできるようになりたい(目標は三十分)。

今日から始める競プロ日記のまとめページ

kato-robotics.hatenablog.com

AtCoder Beginner Contest 111 C - 今日から始める競プロ日記

はじめに

chokudaiさんの今日の一問を解いてみた。

AtCoder Beginner Contest 111 C ( ABC 111 C )

方針はすぐに立ったけど、 結局20分くらいかかってしまった。

たぶん方針の立て方が甘いのだと思う。

C - /\/\/\/

数列が与えられる。

この数列の偶数番目と奇数番目をそれぞれ同じ値にしたい。

値を書き換える最小回数を求めよ。

atcoder.jp

解いた方針

  1. 与えられた数列を偶数番目の数列と奇数番の数列に分ける
  2. 二つの数列においてそれぞれ最頻値と二番目の最頻値を求める
  3. あとは最頻値となる値に数列を揃えればよい(書き換える最小回数を求める)
  4. 気を付けることは偶数番目と奇数番目の値は異なる必要があること
  5. つまり最頻値となる値が同じ場合はどちらかを二番目の最頻値の値にすることが必要

コード

解いた方針とちょっと違うことをしてる。

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
 
int main()
{
    // 入力
    map<int, int> mp1;
    map<int, int> mp2;
    int N;
    cin >> N;
    for(int i = 0; i < N; i++)
    {
        int a;
        cin >> a;
        if(i % 2 == 0) mp1[a]++;
        else mp2[a]++;
    }

    // 最頻値から答えを求める1
    int max1 = 0;
    int key = 0;
    for(pair<int, int> m: mp1)
    {
        if(m.second > max1)
        {
            max1 = m.second;
            key = m.first;
        }
    }
    int max2 = 0;
    for(pair<int, int> m: mp2)
    {
        // mp1の最頻値となるkeyとは異なる値を選ぶ
        if(m.second > max2 && m.first != key) max2 = m.second;
    }
    int ans1 = (N/2 - max1) + (N/2 - max2);

    // 最頻値から答えを求める2
    max1 = 0;
    key = 0;
    for(pair<int, int> m: mp2)
    {
        if(m.second > max1)
        {
            max1 = m.second;
            key = m.first;
        }
    }
    max2 = 0;
    for(pair<int, int> m: mp1)
    {
        // mp2の最頻値となるkeyとは異なる値を選ぶ
        if(m.second > max2 && m.first != key) max2 = m.second;
    }
    int ans2 = (N/2 - max1) + (N/2 - max2);

    // 答えを出力
    int ans = min(ans1, ans2);
    cout << ans << endl;
    return 0;
}

おわりに

無難に解けた

今日から始める競プロ日記のまとめページ

kato-robotics.hatenablog.com

AtCoder Beginner Contest 140 D - 今日から始める競プロ日記

はじめに

AtCoder Beginner Contest 140 D ( ABC 140 D ) 。

コンテスト中に解けなかった。

前に見たことあるなー、 解けそうだなー、 と思いながら結局解けなかった問題。

D - Face Produces Unhappiness

atcoder.jp

解いた方針

自分なりに考えてみた解き方なので、 全然スマートではない。

文字列の圧縮(連続した同じ文字の文字数をカウント)

以下の文字列において、 同じ文字がいくつ連続しているかでまとめてみる。

LRLRRL

Lが1つ、Rが1つ、Lが1つ、Rが2つ、Lが1つ。

L R L R L
1 1 1 2 1

ここではもう、'L'と'R'はどうでもよくて、

11121

という整数列が重要になる。

反転する前の幸福人数を数える

11121

における幸福な人の数を数える。

条件:目の前にいる人が同じ向きを向いていれば幸福

以下は例。

文字列 幸福値
R 0
RL 0
RLR 0
RRL 1
RLL 1
RRR 2

上の表から分かる通り、 連続した文字数が1である文字列では幸福値は0になる。

連続した文字数が2である文字列は幸福値は1。

連続した文字数が3である文字列は幸福値は2。

つまり、

幸福値 = 連続した文字数 - 1

である。

ということで反転する前の整数列

11121

の幸福値は1である。

さらに、 一度幸福値を求めたら、 この1112111111と考えられる(もうカウントされているから)。

反転したときの処理

11111

を一度反転させたとき、 幸福値はどのように変化するか考える。

例として2番目を反転させてみると、 両隣の文字と同じ文字になるので1+1+1=3より 以下のようになる。

131

このとき、幸福値は+2されたことが分かる。

では端っこの場合はどうなるか。

11111の左端を反転させてみると以下のようになる。

2111

このときの幸福値は+1されたことが分かる。

つまり、

  • 端っこの場合は+1
  • 端っこでなければ+2

することが分かる。

あとはK回の反転回数の内、 まずできるだけ端っこの文字を反転させて、 まだ反転させられるのならば端っこも反転させる。

ちなみに、 最大値はN-1になるので気を付ける。

流れ

  • 同じ文字を数えて整数列を作成
  • できるだけ端っこではない文字を反転させる
  • 左端と右端も反転させられるならさせる
  • 最大値はN-1を超えないので気を付ける

計算量のオーダーはO(N)になるはず。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main()
{
    // 入力
    ll N, K;
    cin >> N >> K;
    string S;
    cin >> S;
 
    // 連続した文字を数えて整数列を作成
    vector<ll> v;
    ll cnt = 1;
    char c = S[0];
    for(int i = 1; i < N; i++)
    {
        if(c == S[i])
        {
            cnt++;
        }
        else
        {
            v.push_back(cnt);
            c = S[i];
            cnt = 1;
        }
        if(i == N-1) v.push_back(cnt);
    }
 
    // 反転する前の幸福値を計算
    ll ans = 0;
    for(int i = 0; i < v.size(); i++) ans += v[i]-1;
 
    // 反転処理
    
    // 端っこではない文字の反転
    if(K <= v.size()-2) // K回だけ反転
    {
        ans += 2 * K;
        K = 0;
    }
    else // 端っこではない文字をすべて反転
    {
        ll times = max(0LL, (ll)(v.size()-2));
        ans += 2LL * times;
        K -= times;
    }
 
    // 端っこの文字を反転
    ans += min(2LL, K); //端っこは左端と右端の二つしかない
 
    // 最大値はN-1より大きくはならない
    ans = min(N-1, ans);
 
    // 出力
    cout << ans << endl;
    return 0;
}

おわりに

解けそうで解けない問題だった。

今日から始める競プロ日記のまとめページ

kato-robotics.hatenablog.com

AtCoder Regular Contest 054 B - 今日から始める競プロ日記

はじめに

chokudaiさんの今日の一問を解いてみた。

AtCoder Regular Contest 054 B ( ABC 054 B ) 。

三分探索で解いた。

B - ムーアの法則

コンピュータの計算速度が1.5年で2倍になる。

タカハシマン関数を計算するのに、 現在のコンピュータではP時間かかってしまう。

計算が終わるまでの最短時間を求めよ。

atcoder.jp

解いた方針

計算時間の関数の最小値を求めればいいなってことはまず分かった。

計算時間関数:f(x) = x + P * 2^(x/1.5)

最初、微分をして傾きを調べながら、二分探索をしようと思ったけど、 実装がなんかおかしくなった(たぶん解けるはず)。

ということで三分探索を使って解いた(こっちのほうがスマートだった)。

三分探索の解説は以下の記事が分かりやすかった。ありがたい。

naoyat.hatenablog.jp

三分割する区切りの更新をしっかり実装できれば解ける問題だった。

コード

#include <iostream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
 
// 判定に使う小さい値
const double EPS = 1e-10;
 
// 時間を求める関数
double f(double x, double p)
{
    return x + (p/pow(2.0, x/1.5));
}
 
int main()
{
    // 入力
    double p;
    cin >> p;
 
    // 答え
    double ans = 1e18;
 
    // 三分探索の両端
    double left = 0.0;
    double right = 1000.0;
 
    while(abs(right-left) > EPS)
    {
        // 三分探索の区切り、leftを足すのを忘れずに
        double x1 = left + (right-left) / 3.0;
        double x2 = left + 2.0 * (right-left) / 3.0;
 
        // 区切ったところを値を計算
        double tmp1 = f(x1, p);
        double tmp2 = f(x2, p);
 
        // 最小値を更新
        ans = min(ans, tmp1);
        ans = min(ans, tmp2);
 
        // 三分探索の範囲を更新
        if(tmp1 <= tmp2) right = x2;
        else if(tmp1 > tmp2) left = x1;
    }
 
    cout << setprecision(10) << ans << endl;
    return 0;
}

おわりに

三分探索を使ったのが生まれて初めてだった。

今日から始める競プロ日記のまとめページ

kato-robotics.hatenablog.com

AtCoder Regular Contest 005 C - 今日から始める競プロ日記

はじめに

chokudaiさんの今日の一問を解いてみた。

AtCoder Regular Contest 005 C ( ARC 005 C ) 。

実装がちょっと大変で、 もっとスマートに書けるんだろうなーと思いながらコードを書いてた。

C - 器物損壊!高橋君

縦Hマス、横Wマスの街がある。

各マスは'.', '#', 's', 'g'で表されている。

高橋君は 's' から 'g' へ行きたい。

'.' は通ることができる道であり、 '#' は通ることができない塀である。

高橋君は二度まで塀を壊して通ることができる。

このとき、 高橋君は 's' から 'g' へ行くことができるか求めよ。

atcoder.jp

解いた方針

's' マスのコストを0として、 すべてのマスに対してコスト計算を行う。

コストとはそのマスにたどり着くまでに '#' を通った回数。

また、探索中に同じマスを何回も通る可能性があるが、 そのときはコストが小さくなるように更新していく。

そして 'g' マスまでのコストが2以下かどうかを判定する。

2以下ならば 'YES' を出力し、 2より大きいならば 'NO' を出力する。

コード

かなり雑なコードになってしまった。

もっとスマートに書きたい。

#include <iostream>
#include <vector>
using namespace std;
const int MAX = 502;
const int INF = 1<<29;
vector<pair<int, int>> p;
vector<vector<int>> cnt(MAX, vector<int>(MAX, INF));
vector<vector<char>> field(MAX, vector<char>(MAX, '?'));
string ans = "NO";
int sx, sy, gx, gy;
int H, W;
 
// 再帰的にコストを計算していく関数
void func(int x, int y)
{
    // 'g'マスにおいてコストが2以下なら'YES'を出力
    if (x == gx && y == gy && cnt[x][y] <= 2)
    {
        ans = "YES";
        return;
    }
 
    // 上下左右(東西南北)への移動
    for (int i = 0; i < 4; i++)
    {
        // 次のマスの座標を取得
        int nx = x + p[i].first;
        int ny = y + p[i].second;
        // 範囲外なら無効
        if (nx < 0 || nx >= H)
            continue;
        if (ny < 0 || ny >= W)
            continue;
        if (field[nx][ny] == '?')
            continue;
        // 移動先のマスが '#' ならばコスト+1する
        int tmp = cnt[x][y];
        if (field[nx][ny] == '#' && cnt[nx][ny] > tmp+1 && tmp+1 <= 2)
        {
            cnt[nx][ny] = tmp + 1;
            func(nx, ny);
        }
        // 違うならそのままコストを引き継ぐ
        else if (field[nx][ny] != '#' && cnt[nx][ny] > tmp && tmp <= 2)
        {
            cnt[nx][ny] = tmp;
            func(nx, ny);
        }
    }
    return;
}
 
int main()
{
    // 上下左右(東西南北)への移動を定義
    p.push_back(make_pair(0, 1));
    p.push_back(make_pair(0, -1));
    p.push_back(make_pair(1, 0));
    p.push_back(make_pair(-1, 0));
 
    // 入力
    cin >> H >> W;
    for (int x = 0; x < H; x++)
        for(int y = 0; y < W; y++)
            cin >> field[x][y];
 
    // 's' と 'g' マスの座標を取得
    for (int x = 0; x < H; x++)
    {
        for (int y = 0; y < W; y++)
        {
            if (field[x][y] == 's')
            {
                sx = x;
                sy = y;
            }
            else if (field[x][y] == 'g')
            {
                gx = x;
                gy = y;
            }
        }
    }
 
    // 's'マスのコストを0で初期化
    cnt[sx][sy] = 0;
 
    // 's'を起点としてコスト計算
    func(sx, sy);
 
    // 出力
    std::cout << ans << endl;
    return 0;
}

おわりに

実装が大変

今日から始める競プロ日記のまとめページ

kato-robotics.hatenablog.com

ノートPCの HDD を SSD に換装( Crucial SSD )

はじめに

4年以上使い続けてきたノートPCの動作が明らかに遅くなってきたので、 SSDにデータを丸ごと移して換装しました。

その流れをメモとして残しておきます。

環境

  • OS : Window10 Home
  • PC : Let's note CF-SX4
  • HDD : 容量750GB
  • SSD : Crucial 1TB (後述)

HDDをSSDに換装する際の注意点

HDDをSSDに換装する作業は予想以上に簡単です。

しかし、失敗する可能性はあります。

最悪の場合はすべてのデータが消失することもあるので

重要なデータのバックアップは行ったほうがいいです(安心もできる)。

そして、アクシデントが起こったとしても焦ってはいけません。

私はこの前に一度、 Windowsクリーンインストールに失敗して、 Windowsが立ち上がらなくなり泣きそうになりましたが、 最終的にはなんとか復旧できました。

なんとかなることも多いので、とにかく焦らずに対処すること。

購入したSSD

購入したSSDは以下のもの。

元々のHDDの容量が750GBだったので、 1TBのものを買いました。

HDDからSSDにデータを丸ごと移す場合(クローンする場合)、 元々のHDDで使っているデータ容量よりも大きい容量のSSDを用意する必要があります。

他に必要なもの

SATAをUSBに変換するケーブルが必要になります。

SSDをUSB経由でPCに接続するためです。

HDDのデータをSSDにクローンするときに使用します。

このケーブルはAmazonで1000円以下で売っています。

Crucial SSD の換装方法

Crucial 公式が出している、換装方法の説明動画があります。

私はこれを参考に行いました。

www.crucial.jp

part1からpart4に分かれていて、説明も分かりやすいです。

また動画内でもでてきますが、Crucial の公式がSSDへ換装するためのソフトを公開しています。

このソフトを使えば簡単にHDDのデータをSSDへクローンすることができます。

www.acronis.com

データのクローンには時間がかかるため(数時間はかかる)、 時間に余裕を作って作業をしたほうが良いです(寝ている間とか)。

失敗した場合

失敗の原因はいろいろあると考えられますが、 やり直せる状態ならやり直します。

そこで必要になる作業がSSDのフォーマットです。

以下に続きます。

SSD のフォーマット

SSDに書き込まれたデータをすべて削除します。

SSDのフォーマットはWindowsの機能で行います。

以下の記事が分かりやすいです。

qa.elecom.co.jp

www.crucial.jp

また、SSDパーティションが分けられていて、 なおかつ削除できない場合があります(Windowsの回復パーティションなど)。

そのときはコマンドプロンプトからパーティションを削除する必要があります。

以下の記事が分かりやすいです。

pc-karuma.net

おわりに

HDDからSSDに換装して、ノートPCの動作速度がかなり改善されました。

あとは、メモリの増築もできればしたいと思ってます。