AtCoder Beginner Contest 170 解説(A~C) - Ruteのプログラミング日記

AtCoder Beginner Contest 170 解説

ABC170を終えて(感想と難易度の崖について)
コンテスト成績証
A問題 - A「Five Variables」
- 1.問題概要
- 2.解法
B問題 - B「Crane and Turtle」
- 1.問題概要
- 2.解法
C問題 - C「Forbidden List」
- 1.問題概要
- 2.解法
最後に) 皆さんに聞きたいことがあります

ABC170を終えて(感想と難易度の崖について)

Ruteです！AtCoder Beginner Contest 170 (A問題～D問題)について解説します。

私は、コンテスト中に3完しました！

コンテスト成績証

ユーザ名	Rute
コンテスト名	AtCoder Beginner Contest 170
順位	3692nd / 10521
パフォーマンス	862
レーティング	521 → 561 (+40)

発行日: 2020/06/14

今回はA(1:09),B(10:59),C(16:24)と3完16分でフィニッシュだったのですが、思ったよりパフォーマンスが高かったですね。

理由としては簡単で、D問題のDifficultyが緑色(1034)と、他の問題より高かったためです。

このような現象はここ最近ではABC164が当てはまりますね。

A問題:0　B問題:8　C問題:32　D問題:1204　E問題:1814　F問題:2777

(↑明らかにC問題・D問題間に"難易度の崖"が出来ています。)

これは、典型的な問題セットでは起こりませんが、数学的な問題が出題された・または難しいアルゴリズムを使う問題が出題された　場合に起こりやすいです。

もし3完・2完しかできていなくても、順位表を見るともしかするとパフォーマンスが思っていたより高い場合があるかもしれません。

では、各問題の解説に入ります！(今回はA ~ C問題です)

A問題 - A「Five Variables」

問題ページ: https://atcoder.jp/contests/abc170/tasks/abc170_a

1.問題概要

5つの変数 $x_1,x_2,x_3,x_4,x_5$ が与えられます。

最初、変数 $x_i$ には整数 $i$ が代入されていました。

以下の操作を1回行います。

・これらの変数の中から1つを選び、その変数に0を代入する。

操作を行った後の5つの変数が与えられるので、0を代入した変数がどれであったかを答えてください。

2.解法

解法としてはいろいろなものが考えられます。Python3を利用した3つの解法を紹介したいと思います。

2-1. 15から引いたもの

最初、5つの変数はそれぞれ1,2,3,4,5です。

ここで変数の和=15であることに着目すると、

(最初の5つの変数の和(つまり15)) - (操作を行った後の変数の和)

を求めることによって0を代入した変数がどれであったかを考えることができます

コード: https://atcoder.jp/contests/abc170/submissions/14673733

2-2.for文で0がある部分を特定する

A問題にあるまじき回答かもしれませんが、以下のfor文ループで解くことも可能です。

私もこの方法でACしました！

・(0,4)の区間で x[i] == 0 かを判定。もし0なら(i+1)を出力する

コード:https://atcoder.jp/contests/abc170/submissions/14284433

2-3.indexを利用する

この問題は1行で解くことも可能です。どうするかというと、Pythonのライブラリの1つであるindexを利用します。

ここで、(入力したリスト).index(0) + 1を出力すればよいです。

コード: https://atcoder.jp/contests/abc170/submissions/14673774

以上、A問題の解説でした。今後もA問題についてはACした回答以外に思いついた回答があれば掲載することにします。

B問題 - B「Crane and Turtle」

問題ページ: https://atcoder.jp/contests/abc170/tasks/abc170_b

1.問題概要

庭の動物の総数 $X$ , それらの脚の総数 $Y$ が与えられます。鶴の足の本数を2本、亀の足の本数を4本としたとき、この情報が正しいような鶴と亀の数の組み合わせが存在するか判定してください。ただし庭には鶴か亀しかいないものとします。

2.解法

鶴の数を $x$ 、亀の数を $y$ と置くと、以下の連立方程式が成り立っている必要があります。

$x+y = X$
$2x+4y = Y$

この等式を満たす $x$ , $y$ があるかを考えるのですが、今回は制約が

$1 \leq X \leq 100$
$1 \leq Y \leq 100$

という制約ですので、鶴と亀の数を全探索して求めるのがよさそうです。

以下のループを回します

$(0,X)$ で変数iを用いて以下のループを回す

　now = $Y$ - 2 * i とする(これは亀の足の本数)

　もし　now を 4 で割ったあまりが0なら

　　もし　nowを4で割った商が ( x - i)と一致したら(つまり、亀の足の

　　本数が $X-i$ と同数になったら

　　　"Yes"と出力する

　　　flag関数を+1する

　　　ループを終了する

もし、flag関数が0ならば、"No"と出力する

ここで、flag関数とは私が「フラグが立った」として定義している関数です。

コード:https://atcoder.jp/contests/abc170/submissions/14303527

C問題 - C「Forbidden List」

問題ページ: https://atcoder.jp/contests/abc170/tasks/abc170_c

1.問題概要

整数 $X$ と、長さ $N$ の整数列 $p_1,...,p_N$ が与えられます。

整数列に含まれない整数のうち $X$ に最も近いもの、つまり $X$ との差の絶対値が最小のものを求めてください。

2.解法

問題文を純粋に実装すればよいです。

まず、lsを[(i+1) for i in range(-1000,1001)]などで定義します。

(これが、出力する値の候補リストとなります)

次に、 $N$ 回以下のループを回します。

　・lsからp[i]を除外する(これは、p[i]が互いに異なるので実行できます)

その後、now = $10^5$ 、ans = -200などで定義します。

(nowが $X$ との差の最小値、ansが出力する値です)

以下のループを[tex;|ls|]回行います。

　・もし|ls[i]-X| < now]の場合

　　・now = | ls[i]-X | とする

　　・ans = ls[i]とする

最後に、ansを出力すれば、求めたい値、つまり $X$ と絶対値が最も近い整数を出力することができるでしょう。

コード:https://atcoder.jp/contests/abc170/submissions/14309381

最後に) 皆さんに聞きたいことがあります

ABC170の解説はここまでです。最後まで見ていただいた方、ありがとうございました！

さて、ここで私から皆さんにお聞きしたいことがあります。

これまでは、AtCoder Beginner Contestで私が解けた問題をすべて1つの記事で列挙していたのですが、おそらく"記事が長い"などと考える方もいると思います。十分承知です。

そこでですがいろいろと考えています

・問題別で解説記事を作成する

これは、単純に記事を短くして、1つ1つの記事で解説をより分かりやすいものにしたいと思ったからです。ただ、これによって記事間を遷移しないといけないというデメリットが生じます

・解法を大筋のみ書いて、後はリンク先のコードで解説をする

これは、記事の長さが短くなりますし、単純にコードに解説が書かれているので良い試みだと思っています。

その他、このブログに対して「こうすればもっと解説が読みやすくなる」という取り組みがあれば、コメント　または @rute_not_routeのツイッターにDMをして教えていただけると助かります！(ABC172の解説以降で繁栄予定です)

私としてはPython3をメイン言語にされている方にとってわかりやすい解説にしたいと思いますが、C++を利用されている方、Javaを利用されている方等も遠慮なく教えていただけると助かります！

皆さんのコメントを参考にして今後記事を書いていきます！よろしくお願いいたします。