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;
}
おわりに
そこそこ時間がかかってしまった。
もっとシンプルに問題を考えられるように精進していきたい。
今日から始める競プロ日記のまとめページ
AtCoder Regular Contest 006 D 今日から始める競プロ日記
はじめに
chokudaiさんの今日の一問を解いてみた。
AtCoder Regular Contest 006 D
結局、他の人の提出コードを参考にしてAC。
今日の問題はアルファベット探し！太古のARCのD問題！
— chokudai(高橋 直大)🍆🍡🌸 (@chokudai) August 23, 2019
現行システムだと500点問題くらい？競プロ慣れしてない人でもチャレンジできる難問！
水色の人でもけっこう苦戦するんじゃないかなあ。#chokudai今日の一問 https://t.co/47xE9HJYHp
D - アルファベット探し
与えられた図の中から A、B、C の図形がそれぞれ何個あるか数える問題。
解いた方針
各図形のマスを数える
30分くらい考えていたら、 各図形を形作っている黒マスの数がそれぞれ異なっていることに気づいた。
- Aは12マス
- Bは16マス
- Cは11マス
さらに、 図形を整数倍してもそれぞれのマスの数は判別できそうだった。
- 図形を2倍にすると、マスの数は2*2=4倍
- 図形を3倍にすると、マスの数は3*3=9倍
- 図形を4倍にすると、マスの数は4*4=16倍
- ......
各図形を整数倍したときのマスの数
| 倍 | Aのマス数 | Bのマス数 | Cのマス数 |
|---|---|---|---|
| 1 | 12 | 16 | 11 |
| 2 | 12x2x2=48 | 16x2x2=64 | 11x2x2=44 |
| 3 | 12x3x3=108 | 16x3x3=144 | 11x3x3=99 |
| 4 | 12x4x4=192 | 16x4x4=256 | 11x4x4=176 |
| ... | ... | ... | ... |
つまり黒マスの数をカウントすれば、 その図形が A なのか、B なのか、C なのかが判別できる。
一つの図形のマスだけを数える方法
まず、黒マスを一つ見つける。
見つけた黒マスの周り8マスの見て、 また黒マスがあればそちらに移動する。
この処理を再帰的に行う。
こんな感じで黒マスを5つカウントできた（カウントの順番は実装方法によるため、図の通りになるかは分からない）。
コード
数えるところまでは実装できたけど、 図形の判別方法でおかしくなってしまった。
WAの原因が分からなかったので、 同じころに提出してACしていたta7uwさんのコードを参考にしたらACした（ありがたい）。
ta7uwさんの提出コード：
自分が提出したコード：
#include <iostream>
#include <vector>
#include <string>
using namespace std;
typedef long long ll;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
vector<string> field(10010);
int ans[3] = {0};
int cnt = 0;
void painting(int i, int j)
{
for(int x: dx) {
for(int y: dy) {
if(field[i+x][j+y] == 'o') {
cnt++;
field[i+x][j+y] = '.';
painting(i+x, j+y);
}
}
}
return;
}
int check(int a)
{
for(int i = 2; i*i <= a; i++) {
while(a % (i*i) == 0) a /= (i*i);
}
return a;
}
int main()
{
int H, W; cin >> H >> W;
for(int i = 0; i < H; i++) {
cin >> field[i];
}
for(int i = 1; i < H-1; i++) {
for(int j = 1; j < W-1; j++) {
if(field[i][j] == 'o') {
cnt = 0;
painting(i, j);
int a = check(cnt);
if(a == 3) ans[0]++;
else if(a == 1) ans[1]++;
else if(a == 11) ans[2]++;
}
}
}
cout << ans[0] << " " << ans[1] << " " << ans[2] << endl;
return 0;
}
おわりに
ふつうに難しかった。
今日から始める競プロ日記のまとめページ
AtCoder Beginner Contest 112 C - 今日から始める競プロ日記
はじめに
chokudaiさんの今日の一問を解いてみた。
ABC112のC問題。
前に見たことある問題だけど、 その時は解けなかったので再挑戦ということになる。
今日の一門はPyramid！300点問題ながら参加者の多くを苦しめた一問。何度か言及してるので、解いてる人も多そうな問題かな。https://t.co/YQYRDqrt7t#chokudai今日の一問
— chokudai(高橋 直大)🍆🍡🌸 (@chokudai) 2019年8月21日
C - Pyramid
ピラミッドが一つある。
ピラミッドには中心座標(Cx, Cy)と高さHが定まっている（入力で与えられる訳ではない）。
また、座標(x, y)における高さは max(H-|x-Cx|-|y-Cy|, 0)で求められる。
中心座標と高さの条件は
0 <= Cx, Cy <= 100 1 <= H
である。
N個の入力の組、座標(xi, yi)と高さhiが与えられたとき、 中心座標(Cx, Cy)と高さHを求めよ。
解き方
中心座標の可能性がある座標を全探索する。
座標(x, y)の条件は以下の通り。
0 <= x <= 100 0 <= y <= 100
つまり、縦101マス、横101マス
101*101=10201より合計10201マスを全探索する。
各座標でやること
- 入力の情報から
H = h + |x-Cx| + |y-Cy|の計算をして高さを求める - その高さがすべての入力の情報と合致するかどうか判定する
すべての入力情報と合致した座標と高さが答えとなる
気を付ける点として、 入力のhは0の場合があるということ。
h=0というのは高さ0というよりは、 そこにピラミッドはないということであるので、 高さ=0のつもりで計算するとおかしくなる（たぶん）。
コード
公式解説のサンプルコードのURLを貼っておきます。
おわりに
解き終わってみれば簡単な問題だったけど、 時間がかかってしまった。
今日から始める競プロ日記のまとめページ
AtCoder Regular Contest 001 B - 今日から始める競プロ日記
はじめに
chokudaiさんの今日の一問を解いてみた。
ARC001のB問題。
解くまでに11分。もうちょっと早く解けても良さそう。
今日の一問は、ARC001より、リモコン！AtCoderはここから始まった。
— chokudai(高橋 直大)🍆🍡🌸 (@chokudai) August 22, 2019
今の基準だと簡単目の300点くらいかな？解くことは出来るだろうけど、「5分で解いて」ってなると水色レベル。早解きを意識してやってみよう！https://t.co/z4G3AIGT7z#chokudai今日の一問
B - リモコン
エアコンの設定温度をA度からB度にしたい。
一度のボタン操作で以下の6つの操作のうち一つを実行できる。
- 1度上げる
- 1度下げる
- 5度上げる
- 5度下げる
- 10度上げる
- 10度下げる
操作の最小回数を求めよ。
解き方
6つの操作のうち、 最もB度に近くなる操作を繰り返していく。
という一番単純そうな解き方をした。
解説によると解き方は色々あるらしい。
サンプル2で試してみる。
19度から28度にしたい。
6つの操作を全て試す。
19 + 1 = 20 19 - 1 = 18 19 + 5 = 24 19 - 5 = 14 19 + 10 = 29 19 - 10 = 9
一番28度に近くなったのは19+10=29。
また同じように6つの操作を試す。
29 + 1 = 30 29 - 1 = 28 29 + 5 = 34 29 - 5 = 24 29 + 10 = 39 29 - 10 = 19
一番28度に近くなったのは29-1=28。
ということで操作の最小回数は2回。
コード
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int A, B;
cin >> A >> B;
vector<int> v{10, -10, 5, -5, 1, -1};
int cnt = 0;
while(A != B)
{
int diff = 0;
int minv = 1<<29;
for(int i = 0; i < v.size(); i++)
{
if(abs(B - (A+v[i])) < minv)
{
minv = abs(B - (A+v[i]));
diff = v[i];
}
}
A += diff;
cnt++;
}
cout << cnt << endl;
return 0;
}
おわりに
速解きを意識したい
今日から始める競プロ日記のまとめページ
AtCoder Beginner Contest 113 C - 今日から始める競プロ日記
はじめに
chokudaiさんの今日の一問を解いてみた。
ABC113のC問題。
何をすればいいかは分かったけど、 やっぱり実装方法でかなり悩んでしまった。
自分なりに解き方をまとめてみる（といいつつ何もまとめていない）。
緑の人がこの辺の問題を解けてないのを見ると、「こいつら実装力あるって言って大丈夫か」って思っちゃう部分もある。数学的な思考力があれば、実装力が全然なくても到達できちゃうのが緑、という側面はあるのよね。https://t.co/MryU1zLy6Q
— chokudai(高橋 直大)🍆🍡🌸 (@chokudai) August 19, 2019
C - ID
N個の県があり、これらの県には合計でM個の市が属している。
市i は Yi 年に誕生し、 県Pi に属している。
ここでそれぞれの市に12桁の識別番号を割り振ることにした。
市i が県 Pi の中で x 番目に誕生した市であるとき、 識別番号の上6桁を Pi、下6桁を x とする。
すべての市の認識番号を求めよ（入力順に出力する）。
解き方
まず、県Piについてソートすると同じ県同士がまとめられる。
そして、同じ県の中で誕生年順にソートする。
あとは県毎に市の順番をカウントして整理して出力するだけ。
なのに実装するときに、 公式の解説に載っているコードと同じようなことを思いついたんだけど、 勘違いでTLEする気がして他の方法を考えようとなってしまった。
それでいろいろいじってmapとか使って解いた。
公式の解説 : https://img.atcoder.jp/abc113/editorial.pdf
公式の解説のコードはだいぶスマート。
あと、こちらの解説記事も分かりやすかった。
特にpairの使い方でこんなことができるのかと思った。
pairを二つ使って三つの値をひとまとめにしてソートする。
こんな感じ
pair<pair<P, Y>, i> ： <<県, 年>, i番目>
pairのデータについてソートを行うと、 まず first のについてソートを行い、 first の値が同じもの同士は second の値についてソートが行われるらしい。
実際に確認してみる。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
// <<P,Y>,i>のように三つのデータを一つの配列で扱う
vector<pair<pair<int, int>, int>> data(10);
// データを入力
data[0] = make_pair(make_pair(1, 1), 0);
data[1] = make_pair(make_pair(2, 2), 1);
data[2] = make_pair(make_pair(3, 3), 2);
data[3] = make_pair(make_pair(1, 7), 3);
data[4] = make_pair(make_pair(5, 6), 4);
data[5] = make_pair(make_pair(1, 5), 5);
data[6] = make_pair(make_pair(2, 1), 6);
data[7] = make_pair(make_pair(1, 9), 7);
data[8] = make_pair(make_pair(3, 4), 8);
data[9] = make_pair(make_pair(1, 8), 9);
// Xについてソート、Xが同値の中でYについてもソート
sort(data.begin(), data.end());
// ソートされているか確認
for(auto d: data)
{
cout << d.first.first << " ";
cout << d.first.second << " ";
cout << d.second << endl;
}
return 0;
}
出力結果
P Y i ------ 1 1 0 1 5 5 1 7 3 1 8 9 1 9 7 2 1 6 2 2 1 3 3 2 3 4 8 5 6 4
このようにしてpairを使っても解くことができる。
もちろん、配列で十分ではあるけども。
おわりに
勉強になった
