AtCoder Beginner Contest 140 D - 今日から始める競プロ日記
はじめに
AtCoder Beginner Contest 140 D ( ABC 140 D ) 。
コンテスト中に解けなかった。
前に見たことあるなー、 解けそうだなー、 と思いながら結局解けなかった問題。
D - Face Produces Unhappiness
解いた方針
自分なりに考えてみた解き方なので、 全然スマートではない。
文字列の圧縮（連続した同じ文字の文字数をカウント）
以下の文字列において、 同じ文字がいくつ連続しているかでまとめてみる。
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である。
さらに、
一度幸福値を求めたら、
この11121は11111と考えられる（もうカウントされているから）。
反転したときの処理
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;
}
おわりに
解けそうで解けない問題だった。
今日から始める競プロ日記のまとめページ
AtCoder Regular Contest 054 B - 今日から始める競プロ日記
はじめに
chokudaiさんの今日の一問を解いてみた。
AtCoder Regular Contest 054 B ( ABC 054 B ) 。
三分探索で解いた。
今日の一問は、ARC054より、ムーアの法則！
— chokudai(高橋 直大)🍆🍡🌸 (@chokudai) August 29, 2019
問題自体は競プロ的なんだけど、ちょっと問題テーマが面白いから個人的に好きな問題。難易度は400点くらいで少し難しいかも？#chokudai今日の一問
B - ムーアの法則 https://t.co/fuchkfm5bP
B - ムーアの法則
コンピュータの計算速度が1.5年で2倍になる。
タカハシマン関数を計算するのに、 現在のコンピュータではP時間かかってしまう。
計算が終わるまでの最短時間を求めよ。
解いた方針
計算時間の関数の最小値を求めればいいなってことはまず分かった。
計算時間関数：f(x) = x + P * 2^(x/1.5)
最初、微分をして傾きを調べながら、二分探索をしようと思ったけど、 実装がなんかおかしくなった（たぶん解けるはず）。
ということで三分探索を使って解いた（こっちのほうがスマートだった）。
三分探索の解説は以下の記事が分かりやすかった。ありがたい。
三分割する区切りの更新をしっかり実装できれば解ける問題だった。
コード
#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;
}
おわりに
三分探索を使ったのが生まれて初めてだった。
今日から始める競プロ日記のまとめページ
AtCoder Regular Contest 005 C - 今日から始める競プロ日記
はじめに
chokudaiさんの今日の一問を解いてみた。
AtCoder Regular Contest 005 C ( ARC 005 C ) 。
実装がちょっと大変で、 もっとスマートに書けるんだろうなーと思いながらコードを書いてた。
今日の一問を出すのを忘れていたので、器物損壊高橋君置いておきます＞＜#chokudai今日の一問https://t.co/xMP36188so
— chokudai(高橋 直大)🍆🍡🌸 (@chokudai) August 26, 2019
C - 器物損壊！高橋君
縦Hマス、横Wマスの街がある。
各マスは'.', '#', 's', 'g'で表されている。
高橋君は 's' から 'g' へ行きたい。
'.' は通ることができる道であり、 '#' は通ることができない塀である。
高橋君は二度まで塀を壊して通ることができる。
このとき、 高橋君は 's' から 'g' へ行くことができるか求めよ。
解いた方針
'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;
}
おわりに
実装が大変
今日から始める競プロ日記のまとめページ
ノートPCの HDD を SSD に換装（ Crucial SSD ）
はじめに
4年以上使い続けてきたノートPCの動作が明らかに遅くなってきたので、 SSDにデータを丸ごと移して換装しました。
その流れをメモとして残しておきます。
環境
HDDをSSDに換装する際の注意点
HDDをSSDに換装する作業は予想以上に簡単です。
しかし、失敗する可能性はあります。
最悪の場合はすべてのデータが消失することもあるので
重要なデータのバックアップは行ったほうがいいです（安心もできる）。
そして、アクシデントが起こったとしても焦ってはいけません。
私はこの前に一度、 Windowsのクリーンインストールに失敗して、 Windowsが立ち上がらなくなり泣きそうになりましたが、 最終的にはなんとか復旧できました。
なんとかなることも多いので、とにかく焦らずに対処すること。
購入したSSD
購入したSSDは以下のもの。
- 出版社/メーカー: Crucial(クルーシャル)
- 発売日: 2017/12/19
- メディア: Personal Computers
- この商品を含むブログを見る
元々のHDDの容量が750GBだったので、 1TBのものを買いました。
HDDからSSDにデータを丸ごと移す場合（クローンする場合）、 元々のHDDで使っているデータ容量よりも大きい容量のSSDを用意する必要があります。
他に必要なもの
SATAをUSBに変換するケーブルが必要になります。
SSDをUSB経由でPCに接続するためです。
HDDのデータをSSDにクローンするときに使用します。
このケーブルはAmazonで1000円以下で売っています。
Crucial SSD の換装方法
Crucial 公式が出している、換装方法の説明動画があります。
私はこれを参考に行いました。
part1からpart4に分かれていて、説明も分かりやすいです。
また動画内でもでてきますが、Crucial の公式がSSDへ換装するためのソフトを公開しています。
このソフトを使えば簡単にHDDのデータをSSDへクローンすることができます。
データのクローンには時間がかかるため（数時間はかかる）、 時間に余裕を作って作業をしたほうが良いです（寝ている間とか）。
失敗した場合
失敗の原因はいろいろあると考えられますが、 やり直せる状態ならやり直します。
そこで必要になる作業がSSDのフォーマットです。
以下に続きます。
SSD のフォーマット
SSDに書き込まれたデータをすべて削除します。
以下の記事が分かりやすいです。
また、SSDのパーティションが分けられていて、 なおかつ削除できない場合があります（Windowsの回復パーティションなど）。
そのときはコマンドプロンプトからパーティションを削除する必要があります。
以下の記事が分かりやすいです。
おわりに
HDDからSSDに換装して、ノートPCの動作速度がかなり改善されました。
あとは、メモリの増築もできればしたいと思ってます。
AtCoder Beginner Contest 006 D - 今日から始める競プロ日記
はじめに
chokudaiさんの今日の一問に挑戦。
AtCoder Beginner Contest 006 D ( ABC 006 D ) 。
解説を読みながら自分なりにまとめていきます。
今日の一問は、トランプ挿入ソート！
— chokudai(高橋 直大)🍆🍡🌸 (@chokudai) August 27, 2019
現代AtCoderでは出づらいストレートな知識勝負。
問題の言い換え→アルゴリズムによる計算量の最適化、という流れは、まさに競プロ的。問題の言い換えまでは頑張ってみよう！#chokudai今日の一問https://t.co/3ZoZKOYLqk
D - トランプ挿入ソート
数字が書かれたN枚のカードが並んでいる。
以下の操作を行う。
操作：一枚カードを抜き取り、任意の位置に挿入
カードを昇順に並べるために必要な操作の最小回数を求めよ。
解いた方針
解説を参考。
単純に並び替えを全通りやっていたらきりがないので工夫が必要になる。
ここでとりあえず挿入ソートについて調べてみる。
すると、
「一般に計算量のオーダはO(N^2)と遅いが、ある程度ソート済みの配列に対しては高速」
みたいなことが書かれていた。
そこから考えられることとして、 挿入ソートは「与えられた配列がどの程度ソートされているか」によって計算量が変わってくるということが分かる。
つまり、 与えられた配列の中でソート済みの要素がいくつあるか数えれば良さそうだということが分かる。
たとえば、
1 3 5 2 4 6
という配列が与えられたとする。
この中でソート済みの要素の例として以下のような部分列がある。
1 3 5 6
この 1, 3, 5, 6 は昇順に並んでいる。
さらにここから、残りの 2, 4 を適切な場所に挿入すればすべての要素がソートされることが分かる。
つまり、必要な操作回数は2回。
以上のことから、 ソート済みの部分列の中で、最大の部分列の長さを求められれば答えが分かる ということになる。
動的計画法を用いて部分列の長さを計算
ソート済みの部分列の長さを求める計算にも工夫が必要。
愚直にやるとたぶんTLEする。
そこで動的計画法（DP）を使う。
まず、DP配列を作る（長さはN+1やN+2にする）
このDP配列では、 ソート済みの部分列の長さごとに管理をしていく。
- 長さ1の部分列の最小値はdp[1]
- 長さ2の部分列の最小値はdp[2]
- 長さ3の部分列の最小値はdp[3]
- ......
このようなDPをして何が分かるかというと、 さっき言った通り、ソート済みの部分列の中で最大の長さが求められる。
例として以下の配列を考える。
1 3 5 2 4 6
dp配列を初期化
[0]=-INF, [1]=INF, [2]=INF, [3]=INF, [4]=INF, [5]=INF, [6]=INF
各入力の値cに対して、dp[i] < c < d[i+1]を満たすか調べ、
満たした場合は更新する。
1が入力される。
[0]=-INF < 1 < [1]=INFより、長さ1の部分列の最小値は[1]=1になる
[0]=-INF, [1]=1, [2]=INF, [3]=INF, [4]=INF, [5]=INF, [6]=INF
3が入力される。
[1]=1 < 3 < [2]=INFより、長さ2の部分列の最小値は[2]=3になる。
[0]=-INF, [1]=1, [2]=3, [3]=INF, [4]=INF, [5]=INF, [6]=INF
5が入力される。
[2]=3 < 5 < [3]=INFより、長さ3の部分列の最小値は[3]=5になる。
[0]=-INF, [1]=1, [2]=3, [3]=5, [4]=INF, [5]=INF, [6]=INF
2が入力される。
[1]=1 < 2 < [2]=3より、長さ2の部分列の最小値は[2]=2になる。
[0]=-INF, [1]=1, [2]=2, [3]=5, [4]=INF, [5]=INF, [6]=INF
4が入力される。
[2]=2 < 4 < [3]=5より、長さ3の部分列の最小値は[3]=4になる。
[0]=-INF, [1]=1, [2]=2, [3]=4, [4]=INF, [5]=INF, [6]=INF
6が入力される。
[3]=4 < 6 < [4]=INFより、長さ3の部分列の最小値は[4]=6になる。
[0]=-INF, [1]=1, [2]=2, [3]=4, [4]=6, [5]=INF, [6]=INF
以上の計算より、ソート済みの部分列の最大の長さは4であることが分かった。
N - 4 = 6 - 4 = 2より、答えは2。
lower_bound を使って高速化
上で説明したdpは愚直にやるとO(N^2)となり遅い（一応それでもACはできた）。
そこでdp配列がソート済みであることを利用してlower_boundを使う。
lower_boundは二分探索で更新するべき場所を探してくれるのでO(NlogN)となる。
lower_boundの分かりやすい説明は以下の記事。ありがたい。
lower_boundは、「ソート済みの配列」と「Keyとなる値」を与えると、 Key以上で一番小さい値を配列の中から探してくれる。
ちなみに返り値はイテレータ。
コード
#include <iostream>
#include <vector>
using namespace std;
const int INF = 1<<29;
int main()
{
int N; cin >> N;
vector<int> dp(N+2, INF); dp[0] = -INF;
for(int i = 0; i < N; i++) {
int c; cin >> c;
auto itr = lower_bound(dp.begin(), dp.end(), c);
dp[itr-dp.begin()] = c;
}
int ans = 0;
for(int i = 0; i < N+1; i++) {
if(dp[i] != INF) ans = N-i;
}
cout << ans << endl;
return 0;
}
おわりに
難しかった。
今日から始める競プロ日記のまとめページ
AtCoder Beginner Contest 060 C - 今日から始める競プロ日記
はじめに
chokudaiさんの今日の一問を解いてみた。
AtCoder Beginner Contest 060 C ( ABC 060 C ) 。
簡単めの問題だったので特に苦労せず解けて良かった。
今日の一問はSentou！前回の問題が難しかったから今日は簡単めで。
— chokudai(高橋 直大)🍆🍡🌸 (@chokudai) 2019年8月25日
こういうのって明確に「アルゴリズム」って言われるほどのものじゃないけど、苦戦する人もいるし、さらっと組めて欲しい、って感じの問題。そんなんばっか選んでる気がする！#chokudai今日の一問https://t.co/nmlTh7JDkj
C - Sentou
スイッチを押してからT秒間お湯が出るシャワーがある。
シャワーが出ている間にスイッチが押された場合は、押した瞬間からT秒間出る。
ti秒にスイッチが押されるので、 合計で何秒間シャワーが出ていたかを求めよ。
解いた方針
問題文で強調されている通り、 スイッチが押されるタイミングには、
- (1) シャワーが出ている場合
- (2) シャワーが出ていない場合
の二通りが考えられる。
この二通りについて上手く考えられれば解けそうだなということは分かる。
まず、t[i] にスイッチが押される。
すると T 秒間お湯が出続ける。
この t[i] から t[i] + T までにスイッチが押された場合(1)と押されなかった場合(2)を考えればよい。
（つまりシャワーが出ている間にスイッチが押されるか押されないかを考えることにした）。
t[i] から t[i] + T までにスイッチが押されないのであれば T だけお湯は出続ける。
スイッチが押された場合は押されるまでお湯が出たとして、 次の t[i+1] に移行する。
この処理はお湯が出ていた時間をカウントする変数をcntとして
cnt += min(T, t[i+1]-t[i])
というように実装できる。
コード
解説を読んで書き直した。
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
int main()
{
ll N, T; cin >> N >> T;
vector<ll> t(N+1, INF);
for(int i = 0; i < N; i++) cin >> t[i];
ll time = 0;
for(int i = 0; i < N; i++) {
time += min(T, t[i+1] - t[i]);
}
cout << time << endl;
return 0;
}
おわりに
ちょうどいい問題だった。
今日から始める競プロ日記のまとめページ
AtCoder Beginner Contest 062 C - 今日から始める競プロ日記
はじめに
chokudaiさんの今日の一問を解いてみた。
AtCoder Beginner Contest 062 C 。
とりあえず解き方を自分なりにまとめておく。
今日の問題は、ABC062より、Chocolate Bar！
— chokudai(高橋 直大)🍆🍡🌸 (@chokudai) August 24, 2019
自分が個人的に解けてほしい問題を選んでるのが分かりやすいチョイスかなーと思うけど、これも緑くらいあったら解けてほしい問題。400点だけどね＞＜#chokudai今日の一問
C - Chocolate Bar https://t.co/nWB7rNyyuM
C - Chocolate Bar
縦Hブロック、横Wブロックのチョコレートをできるだけ均等に3分割したい。
3つのブロックの最大面積をSmax、
最小面積をSminとするとき、
Smax - Sminを最小化せよ。
解いた方針
公式の解説を参考にしながらまとめてみる。
https://img.atcoder.jp/arc074/editorial.pdf
全通りの切り方を試そうとするとTLEするから、 工夫する必要がある。
そこで考えてみると、 三分割する方法は4通りしかない。
- 1 : (1) 横に切ってから、(2) 横に切る
- 2 : (1) 横に切ってから、(2) 縦に切る
- 3 : (1) 縦に切ってから、(2) 横に切る
- 4 : (1) 縦に切ってから、(2) 縦に切る
(1) では切る場所を全通り試すO(N^5)。
(2) では、(1) で切ったあとの残りのブロックを半分にすればいいので、
単純に真ん中を切ればいいO(1)。
「(1) 横に切ってから、(2) 縦に切る」を図に表すとこんな感じ。
まず、0 < h < H で横に切る場所 h を全て試すfor文を回す (1)。
そのfor文の中で、横に切った後の残りのブロックを半分にする (2)。
そうすると、三分割ができるので、Smax - Smin を求められる。
その中で最も小さい Smax - Smin を見つければよい。
自分のコード
解説を読んでから書いたので、 たぶん解説寄りなコードになっているはず。
#include <iostream>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
int main()
{
ll H, W; cin >> H >> W;
ll ans = INF;
for(int h = 1; h < H; h++) {
ll h2 = (H - h) / 2;
if(h2 > 0) {
ll S1 = W * h;
ll S2 = W * h2;
ll S3 = W * (H - h - h2);
ll Smax = max(S1, max(S2, S3));
ll Smin = min(S1, min(S2, S3));
ans = min(ans, Smax-Smin);
}
ll w2 = W / 2;
if(w2 > 0) {
ll S1 = W * h;
ll S2 = (H-h) * w2;
ll S3 = (H-h) * (W - w2);
ll Smax = max(S1, max(S2, S3));
ll Smin = min(S1, min(S2, S3));
ans = min(ans, Smax-Smin);
}
}
for(int w = 0; w < W; w++) {
ll w2 = (W - w) / 2;
if(w2 > 0) {
ll S1 = H * w;
ll S2 = H * w2;
ll S3 = H * (W - w - w2);
ll Smax = max(S1, max(S2, S3));
ll Smin = min(S1, min(S2, S3));
ans = min(ans, Smax-Smin);
}
ll h2 = H / 2;
if(h2 > 0) {
ll S1 = H * w;
ll S2 = (W-w) * h2;
ll S3 = (W-w) * (H - h2);
ll Smax = max(S1, max(S2, S3));
ll Smin = min(S1, min(S2, S3));
ans = min(ans, Smax-Smin);
}
}
cout << ans << endl;
return 0;
}
おわりに
そこそこ時間がかかってしまった。
もっとシンプルに問題を考えられるように精進していきたい。
