パソコン甲子園2019本選参加記「AはDPのA」

予選の様子はこちらです。

private-yusuke.hatenadiary.jp

チームメンバーの簡単な紹介:

  • 自分(public_yusuke)
    • 元部長
    • ❤️💻。🇰🇷📖🔰。🔢↘😱(∵🏫🈴📝🕘, ¬🔢📝🕘)
  • 後輩(season)
    • 現部長
    • ❤️∫πΣ∞∇∂📖💪。🔢↗↗💪。

予選はだいたい1ヶ月前の9/14(土)に行われた。そこで運よく地域枠に引っかかったため、本選へ出場する運びとなりました。

参加前の話

予選の数日前に台風15号が千葉県に甚大な被害をもたらし、私や後輩も長期間の停電や断水の被害を被りました。「こんな状況の後で通るわけないよ」なんて思いながら予選に出たら、凍結時点で24位。千葉県では高専や他の高校を抜いて一位となり、地域枠をもらって本選出場することになりました。

受験勉強があったので私は一切精進しなかったのですが、後輩はコンスタントに400点ぐらいの問題を解いていました。

0日目

私の学校は東京から一時間半ほど離れた場所にあるので、学校から会津若松まで片道4時間半くらいかかります。そのため、金曜日は午後から公欠、いわば早退に近い形で早くから電車に乗ることになりました。
出発は1時半ごろで、会津若松駅に到着したのは17:54ごろ。

東京駅で、チーム「らてd」の@nn1k_さんと@Selfgrudgeさんに、新幹線を待っているとき物理的に接近しました(接近しているだけで、このとき会話はしませんでしたが後の選手交流会で例のエンカ特有のプロフ撮影をした)。

続きを読む

パソコン甲子園2019予選参加記「AはDPのA」

本選の様子はこちらです。

private-yusuke.hatenadiary.jp

チームメンバーと予選前

チームは以下の通りに組みました。

簡単な紹介:

  • 自分(public_yusuke)
    • 元部長
    • コンピュータがないと死ぬ病。パソコンとの出会いが早い。

  • 後輩(season)
    • 現部長
    • 数学徒。強い。数学との出会いが早い。


予選は9/14(土)に行なわれたのですが、私は校内の模試の日と被ってしまいました。しかも担任に大会参加することを伝え忘れたままパソコン室に行く始末。図書室でクラスメイトに会ったのですが、そこで模試を休むことを言い忘れたまま参加していたのがバレて、担任から少しお叱りを受けました。皆さんは大会に参加するときは先生にちゃんと伝えましょうね。先生方ごめんなさい。

予選の数日前、台風15号によって停電、断水などライフラインが止まりました。そんな状況下では数学書も精進もできず、一日一日をどう過ごすか真剣に考えるサバイバル生活を送ることとなりました。*1*2予選当日は親戚の家から電車に乗り、なんとか学校に着くことができましたが、この忙しさの後の予選のため相当厳しいものがあるのではないかと思っていました。それに自分は競プロを休止していたので。

*1:これはライフハックですが、冷えた水を十分大きい容器に入れて足をつけると非常に涼しくなれます。この方法によって、本を読むことができました。(は?)

*2:断水したので近所の井戸から水を汲んでいました。江戸時代か?

続きを読む

AtCoder Beginner Contest 126の解説

A - Changing a Character

入力:
 N\ K
 S
出力: 新しくできた S
制約:

  •  1 \le N \le 50
  •  1 \le K \le N
  •  Sは'A', 'B', 'C'からなる長さ Nの文字列

A, B, Cをそれぞれa, b, cに変換する関数を作ってあげればよいです。

void main() {
	auto ip = readAs!(int[]), N = ip[0], K = ip[1];
	auto S = rs;
	writeln(S[0..K-1] ~ f(S[K-1]) ~ S[K..$]);
}
 
char f(char x) {
	switch (x) {
		case 'A': return 'a';
		case 'B': return 'b';
		case 'C': return 'c';
		default: return '1';
	}
}

こんな手間をかけなくても、標準ライブラリに入力された文字列に含まれる大文字を小文字に変換する関数が用意されていると思いますので、思いつく人はそちらを使うと良いと思います。

感想: 調べるのがめんどくさかったのでfを実装してしまった。

続きを読む

AtCoder Beginner Contest 125の解説

A - Biscuit Generator

入力:  A\ B\ C
出力: ビスケットの合計枚数
制約:

  •  1 \le A, B, T \le 20
  •  A, B, T \in \mathbb{N}

 T+0.5秒後まで生産するとありますが、この 0.5は無視してよいです。
 A, 2A, 3A秒後にビスケットが生産されるということは、 A秒毎に B枚のビスケットができるということなので、私たちがよく知っている「道のり=速さ×時間」の要領で答えを求めることができます。求める答えは、
 \displaystyle{\left\lfloor{\frac{T}{{A}}}\right\rfloor}\cdot{B}
になります。

auto ip = readAs!(int[]), A = ip[0], B = ip[1], T = ip[2];
writeln((T / A * B));

感想: ごくふつうのA問題でした。

B - Resale

入力:
 N
 V_1\ V_2\ \cdots\ V_N
 C_1\ C_2\ \cdots\ C_N
出力:  X - Yの最大値
制約:

  •  1 \le N \le 20
  •  1 \le C_i, V_i \le 50
  • 入力は全て整数

 i番目の宝石を手に入れるとき、 +V_iの価値と -C_iのコストを得るため、最終的にはその宝石について V_i - C_iの価値を得ることができます(答えは \displaystyle{X}-{Y}=\sum_{{i}}{\left({V}_{{i}}-{C}_{{i}}\right)}ですから、価値とコストを同一視できます)。

したがって、 V_i - C_i > 0のとき、その宝石を取るのが得です。そのような宝石を全て取れば、最大値を求めることができました。

int res = 0;
foreach(i; 0..N) {
	if(V[i] - C[i] > 0) res += V[i] - C[i];
}
res.writeln;

感想: 実装をミスって少し時間がかかってしまった。

C - GCD on Blackboard

入力:
 N
 A_1\ A_2\ \cdots\ A_N
出力: 書き換えた後の N個の整数のGCDの最大値
制約:

  •  2 \le N \le 10^5
  •  1 \le A_i \le 10^9
  • 入力は全て整数

ある整数を好きな整数に書き換えられるということは、 N個の整数 A_1, A_2, \cdots, A_N全体のGCDをとるとき、その整数についてだけGCDの演算をしないようにすることと同等です。
したがって、 N個の整数それぞれについて、それ以外の整数のGCDをとったときの最大値を求める問題だと言い換えることができます。

そこで、 N個それぞれについてループを回して、それ以外の N-1個の整数のGCDをとってあげればわかる…というような解法は O(N^2 \log A)となりTLEします。(今回の問いの中心です)

ここでGCDという演算がどのような性質を持つのか考えてみると、これは結合法則交換法則が成り立ちます。したがって、 i番目の整数以外のGCDは \displaystyle \gcd{{\left( \gcd{{\left({A}_{{1}},{A}_{{2}},\ldots,{A}_{{{i}-{1}}}\right)}}, \gcd{{\left({A}_{{{i}+{1}}},{A}_{{{i}+{2}}},\ldots,{A}_{{N}}\right)}}\right)}}として求めてもよいことがわかります。ゆえに、前処理として
 \displaystyle{L}_{{i}}={\left\lbrace\begin{matrix}{A}_{{0}}&{\quad\text{if}\quad}{i}={0}\\ \gcd{{\left({L}_{{{i}-{1}}},{A}_{{i}}\right)}}&\text{otherwise}\end{matrix}\right.}

 \displaystyle{R}_{{i}}={\left\lbrace\begin{matrix}{A}_{{{N}-{1}}}&{\quad\text{if}\quad}{i}={N}-{1}\\ \gcd{{\left({R}_{{{i}+{1}}},{A}_{{i}}\right)}}&\text{otherwise}\end{matrix}\right.}

とすると(0-indexed)、 \displaystyle \gcd{{\left({L}_{{{i}-{1}}},{R}_{{{i}+{1}}}\right)}}の最大値を求めればよいことになり、時間計算量は O(N \log A_1 + N \log A_N)とすることができました。

なお、よくある累積和については、元 aに対して必ず逆元 -aが存在するため一つの配列で考えることができますが、GCDという演算においては逆元を考えることができないので、 L, Rとして両方から累積GCDを考える必要がありました。

auto L = new int[](N);
auto R = new int[](N);

L.front = A.front;
R.back = A.back;
foreach(i; 1..N) {
	L[i] = gcd(L[i-1], A[i]);
}
foreach_reverse(i; 0..N-1) {
	R[i] = gcd(R[i+1], A[i]);
}
ulong res;
foreach(i; 0..N) {
	if(i == 0) { res = R[1]; continue; }
	if(i == N-1) { res = max(res, L[N-2]); continue; }
	res = max(res, gcd(L[i-1], R[i+1]));
}
res.writeln;

感想: これは300点の中でもかなり難しい方だと思う(実装は大変ではないが、考察が大変)

D - Flipping Signs

入力:
 N
 A_1\ A_2\ \cdots\ A_N
出力:  \displaystyle{\sum_{{{i}={1}}}^{{N}}}{B}_{{i}}の最大値
制約:

  •  2 \le N \le 10^5
  •  -10^9 \le A_i \le 10^9
  • 入力は全て整数

この問題の操作は、となりあった整数の正負を反転するものですが、f:id:private_yusuke:20190428110528p:plain
このように操作を繰りかえすことで任意の2つの整数の正負を反転させることができます。

したがって、整数列の中の偶数の数を kとすると、 kが偶数の場合は全て正にすることができるので \displaystyle\sum_{{i}}{\left|{A}_{{i}}\right|}が答えになります。
一方、 kが奇数の場合はどのようにしても1つの整数が負のままとなるので、 \displaystyle\sum_{{i}}{\left|{A}_{{i}}\right|}-{2}\cdot\min{\left|{A}_{{i}}\right|}を出力すればよいです。

なお、奇数の場合に2回引き算をするのは、 \displaystyle\sum_{{i}}{\left|{A}_{{i}}\right|}の部分で \displaystyle\min{\left|{A}_{{i}}\right|}を足してしまっている分を引かなければならないからです。

ulong cnt = A.count!(i => i < 0);
ulong res = A.map!(i => i.abs).sum;
if(cnt % 2) res -= A.map!(i => i.abs).reduce!min * 2;
res.writeln;

感想: 気づけばすぐに解けそうだった。操作をうまく用いるとどんなことができるか、というところに着目することが大事な問題だった。

A: Submission #5138695 - AtCoder Beginner Contest 125
B: Submission #5140509 - AtCoder Beginner Contest 125
C: Submission #5164574 - AtCoder Beginner Contest 125
D: Submission #5163895 - AtCoder Beginner Contest 125

AtCoder Beginner Contest 122の解説

A - Double Helix

入力:  b
出力: 塩基  b と対になる塩基
制約:

  •  b は文字 'A', 'C', 'G', 'T' のいずれかである。

サンプルに全ての答えが書いてありますね…

switch(b) {
	case "A": writeln("T"); break;
	case "T": writeln("A"); break;
	case "G": writeln("C"); break;
	case "C": writeln("G"); break;
	default: break;
}

感想: かなりA問題らしい問題で好き

B - ATCoder

入力:  S
出力:  Sの部分文字列のうち最長のACGT文字列の長さ
制約:

  •  1 \le |S| \le 10

部分文字列の意味を考えて実装します。

ulong res;
ulong tmp;
foreach(i; S) {
	if(i == 'A' || i == 'T' || i == 'C' || i == 'G') {
		tmp++;
	} else {
		res = max(res, tmp);
		tmp = 0;
	}
}
res = max(res, tmp);
res.writeln;

感想: ループ後のmaxをとる処理を忘れて1WA…とてもかなしい凡ミスをした。

C - GeT AC

入力:
 N\ Q
 S
 l_1\ r_1
 \vdots
 l_Q\ r_Q
出力:  S の先頭から  l_i 文字目から  r_i 文字目までの部分文字列の中に含まれる 'AC' の数
制約:

  •  2 \le N \le 10^5
  •  1 \le Q \le 10^5
  •  |S| = N
  •  1 \le l_i < r_i \le N
  •  S はACGT文字列

 Q 個のクエリが与えられるので、毎回 'AC' を数えていると O(NQ)となりTLEします。

したがって、「先に 'AC' が出てくる回数を数えておいて、各クエリで記憶しておいた回数を使おう!」という方針を考えます。俗にいう累積和です。

arr[i] を「左から  i 番目までの  S に出現した 'AC' の数」とします。

foreach(i; 0..S.length-1) {
	if(S[i] == 'A' && S[i+1] == 'C') {
		arr[i+1] = arr[i] + 1;
	} else arr[i+1] = arr[i];
}

そして、  S l から  r までの 'AC' の数は「arr[r] - arr[l]」で求めることができました。

auto arr = new int[](N);
foreach(i; 0..S.length-1) {
	if(S[i] == 'A' && S[i+1] == 'C') {
		arr[i+1] = arr[i] + 1;
	} else arr[i+1] = arr[i];
}

foreach(i; 0..Q) {
	auto ip2 = readAs!(int[]), l = ip2[0]-1, r = ip2[1]-1;
	writeln(arr[r] - arr[l]);
}

感想: まさに「累積和をやれ」と言わんばかりの問題でした。

D - We Like AGC

入力:  N
出力: 条件を満たす文字列の数を  10^9+7 で割った余り
制約:

  •  3 \le N \le 100

条件を満たさない文字列は、"."を任意の文字として

  • AGC.
  • GAC.
  • ACG.

  • A.GC
  • AG.C
  • .AGC
  • .GAC
  • .ACG

の形で表すことができます。

愚直に全探索すると  O(4^N) になって間に合わないので、DPで  O(N) にします。

dp[n][t1][t2][t3] を「0-indexedでn-4, n-3, n-2番目の文字がt1, t2, t3と並ぶような、長さnの条件を満たす文字列の数」とします。

[t1, t2, t3]が条件を満たさない文字列になるときはdp[n][t1][t2][t3]==0ですから、その場合はすぐにcontinueします。(上で挙げた条件を満たさない文字列の前半ですね!)

そのあと、上で挙げた条件を満たさない文字列の後半にあたるところも同様にします。

条件を満たす文字列のときは、[t1, t2, t3, a]の並びが大丈夫であることがわかっているので、 dp[n+1][t2][t3][a] += dp[n][t1][t2][t3] として遷移を書きます。( 10^9 + 7で割ることを忘れずに)

最終的な答えは、dp[N]の内側にある値の総和になります。

auto dp = new long[][][][](N+1, 4, 4, 4);
dp[0][3][3][3] = 1;

foreach(n; 0..N) foreach(t1; 0..4) foreach(t2; 0..4) foreach(t3; 0..4) {
	if(dp[n][t1][t2][t3] == 0) continue;
	foreach(a; 0..4) {
		char c1 = t1.t, c2 = t2.t, c3 = t3.t, c4 = a.t;
		if([c1, c3, c4] == "AGC") continue;
		if([c1, c2, c4] == "AGC") continue;
		if([c2, c3, c4] == "AGC") continue;
		if([c2, c3, c4] == "GAC") continue;
		if([c2, c3, c4] == "ACG") continue;
		dp[n+1][t2][t3][a] += dp[n][t1][t2][t3];
		dp[n+1][t2][t3][a] %= MOD;
	}
}
long res;
foreach(t1; 0..4) foreach(t2; 0..4) foreach(t3; 0..4) {
	res += dp[N][t1][t2][t3];
	res %= MOD;
}
res.writeln;

感想: これDPだろということだけわかって、その後は椅子を温めた。

A: Submission #4685262 - AtCoder Beginner Contest 122
B: Submission #4688713 - AtCoder Beginner Contest 122
C: Submission #4687776 - AtCoder Beginner Contest 122
D: Submission #4710256 - AtCoder Beginner Contest 122

AtCoder水色になるまでにやったこと

先日のAtCoder Beginner Contest 118で、晴れて水色になることができたので、例によって色が変動したときに執筆されるタイプの記事を書いてみることにします。

灰色のとき

正直なところあまり記憶がありません。初回はABC069、C++で2完(perf: 397)したようです。
真面目に参加しはじめたのは2018年4月ごろからでした。

初回はC++で参加していたようですが、それより後はDを主に使っています。

「蟻本を買いなさい」という天の声が青い鳥を通じて聞こえたので、この頃にバイブルを買いました。しかし、真面目に読まないで「うっわマジでこんな難しいことをやるの??人間こわすぎでしょ」とか思ってた記憶があります。

  • 基本的な文法
  • stdin/stdout の扱い方、入力文字列のparse
  • 配列の使い方

これらの知識を持っていました。今ではhttps://atcoder.jp/contests/APG4bを利用することで上3つよりも多くの基礎を身につけられるようになっているので、初心者の方はぜひ活用してほしいです。

茶色のとき

ABC096でD - Five, Five Everywhereを解いて茶色になりました。茶色の期間は一番短くて、3回のコンテスト分だけでした。灰色のときと、実力はさほど変わっていなかったように思います。

茶色になってから始めたことは、自分が解説できそうな問題はブログで記事にしてみることと、Twitterの界隈に入りこんでみるということでした。記事として一度まとめてみることで、将来似た問題に遭遇したときに対処できる可能性が上がります。また、界隈において強い人が書いた記事や知見、思考、あるいはクソなぞなぞを目にすることで、柔軟な思考ができるようになりました(ほんまか?)。

このとき、競プロにおいて必要な早解き力をつけることを意識していました。レーティングは順位が高ければ高いほど、良い値がつきます。そのため、一秒でも早くコードを書きサンプルをテストすることを頑張りました。

  • A, Bの早解き
  • 整数
  • DFS, BFS
  • set(redBlackTree)
  • map, filterとかそういう数学チックな関数(早解きするとき役立つ)

緑色のとき

続きを読む