Ruteのプログラミング日記

競技プログラミング(AtCoder)の問題の解説や、過去問を解いた感想、また解けない過去問について共有したいと思ってます。

AtCoder Beginner Contest 168 解説(A~C)

2020/05/17 (日) 21:00-22:40に、AtCoder Beginner Contest 168 が開催されました！

皆さん、お疲れ様でしたー。

私は、ABCの3完で撤退でした。

C問題はゴリゴリの数学でしたね。茶Difficultyはありそう...

 

では問題について振り返っていきましょう。

 

A問題 A - ∴ (Therefore)

https://atcoder.jp/contests/abc168/tasks/abc168_a

問題概要:

以下のルールに従って、与えられたNに対して、N本　というときの「本」の読みを出力して下さい。

  • Nの1の位が2,4,5,7,9の時"hon"
  • Nの1の位が0,1,6,8の時"pon"
  • Nの1の位が3の時"bon"

 解説:

Nを整数ではなく文字列と考えます。参照する文字列をSとします。

  • Nが3桁の時、3桁目をSとします。
  • Nが2桁の時、2桁目をSとします。
  • Nが1桁の時、そのままそれをSとします。

後は、Sを問題文のルールに従って場合分けし、出力をすればよいでしょう。

コード: https://atcoder.jp/contests/abc168/submissions/13292375

 

B問題 B - ... (Triple Dots)

https://atcoder.jp/contests/abc168/tasks/abc168_b

問題概要:

文字列Sと整数Kが与えられます。

|S|を文字列の長さとしたとき

  • |S| ≦ KならばSを、
  • そうでないならSの先頭K文字と"..."を続けて出力しなさい。

 解説:

Pythonでは、文字列の長さをlen(S)などで取得出来ます。

あとは、文字列の長さについて、条件分岐を行って処理をすれば良いです。

Sの先頭K文字は、Python3ではS[0:K]で取得出来ます。

コード: https://atcoder.jp/contests/abc168/submissions/13298567

C問題 C - : (Colon)

(解説を長くしています)

https://atcoder.jp/contests/abc168/tasks/abc168_b

問題概要:

時針の長さがAセンチメートル、分針の長さがBセンチメートルであるアナログ時計を考えます。

それぞれの針は一定の角速度で時計回りで回転します。時針は12時間、分針は1時間で1修します。

ちょうどH時M分になったとき、2本の針の固定されていない位置の距離は何センチメートルでしょうか？

制約

  • 入力はすべて整数
  • 1≤A,B≤1000
  • 0≤H≤11

入力

入力は以下の形式で標準入力から与えられる。

A B H M

 

時計の針の位置について考えましょう。

時針の位置

H時M分の時、時針が回る角度は真上を0度としてからH×30+M×0.5度です。

時針は12時間で1周するので、1分で0.5度回る事に注意して下さい。

なお、制約より、 この角度が360以上になることはありません。

この角度を、以降hとおきます。

分針の位置

M分の時、分針が回る角度は真上を0度としてM×6度です。

なお、制約より、この角度が360以上になることはありません。

 この角度を、以降mとおきます。

 

時針・分針の角度の求め方

時針が3時を指しているところを\theta =\begin{eqnarray}0^\circ\end{eqnarray} として、円を考えます。

f:id:Rute_programming:20200517222152p:plain

このような時計を考えます。

角度について以下のことを行います。

0≦h,m≦90の時、それぞれの針は0度より0時側に90-h度、あるいは90-m度進んでいることになります。

h,mが条件を満たしているとき、それぞれ90-h, 90-mと変換します。

 

90<h,m<360の時、それぞれの針は0時側に450-h度、あるいは450-m度動いていることになります。

h,mが条件を満たしているとき、それぞれ450-h,450-mと変換します。

(X度、0度から6時側に進んでいる　というのは360-X度、0度から0時側に進んでいる　と同じ意味になります。

今回は、90<h,mなので、90度を起点として　このような処理を考えました)

 

少々説明がややこしくなってしまいましたが、このように、時針・分針の角度を考えれば、あとは入力の情報からそれぞれの時針・分針のx座標・y座標を考えれば良いです。

時針のx座標をx_1, y座標をy_1,

分針のx座標をx_2, y座標をy_2　とします。

この時、計算した角度を\thetaとおくと、

x_1 = A×cos\theta

y_1 = A×sin\theta

x_2 = B×cos\theta

y_2 = B×sin\theta

という座標になります。

後は、(x_1-x_2の絶対値の2乗)+(y_1-y_2の絶対値の2乗)　つまりx座標とy座標の距離の差をそれぞれ求めて、それを平方根にしたものが求める距離となります。

 

Pythonのコードにすると以下のようになります。

f:id:Rute_programming:20200517223539j:plain

▲C問題のコードです(リンクからも確認できます)

コード: https://atcoder.jp/contests/abc168/submissions/13315659

 

以上、ABC 168のA問題～C問題の解説でした。

(C問題の解説が少々冗長かもしれません....)

AtCoder Beginner Contest 167 解説 (A ~ C)

AtCoder Beginner Contest 167の解説(A ~ C)です。

今回私は都合によりバーチャル参加をすることになりました。

時間内にABしか解けず2完でした(参考パフォーマンス559)

が、Cも解くことが出来たのでその解説もしたいと思います。

(D問題以降の解説は公式の解説動画を参照して下さい)

A問題 A - Registration

https://atcoder.jp/contests/abc167/tasks/abc167_a

問題概要:

文字列S, Tが与えられるので

文字列Tが以下の条件を満たすか判定して下さい。

  • TはSの末尾に1文字追加した文字列である

制約が|T| = |S|+1であることから、これは単純な条件分岐で済みそうです

Pythonの場合は T[0:len(S)]がSと同じ文字列かを判定すればよいでしょう。

(応用例 制約が1≦|S|≦|T|≦10で、以下のような問題)

文字列S, Tが与えられるので

文字列Tが以下の条件を満たすか判定して下さい。

  • TはSの末尾に1文字のみ追加した文字列である

コード: https://atcoder.jp/contests/abc167/submissions/13106673

B問題 B - 

https://atcoder.jp/contests/abc167/tasks/abc167_b

問題概要:

1が書かれたカードがA枚、0が書かれたカードがB枚、-1が書かれたカードがC枚あります。

これらのカードから、ちょうどK枚を選んで取るとき、取ったカードに書かれた数の和の最大値はいくつになるかを求めよ。

  • K≦Aの時、1が書かれたカードのみを取るので、最大値はKになります。
  • A<K ≦A+Bの時、1が書かれたカードをA枚、残りの枚数を0が書かれたカードで取るので、最大値はAになります。
  • A+B < K ≦A+B+Cの時、1が書かれたカード全て、0が書かれたカード全て、そしてK-(A+B)枚の-1が書かれたカードを取ることになります。
    よって、求める最大値はA-(K-(A+B))になります。

コード:(嘘解法?) https://atcoder.jp/contests/abc167/submissions/13106718

コード:(実際の解法)https://atcoder.jp/contests/abc167/submissions/13128516

 

C問題 C - Skill Up

https://atcoder.jp/contests/abc167/tasks/abc167_c

問題概要:

以下の条件が与えられます。

  • 参考書の数Nと、学びたいアルゴリズムの数M,目標の理解度X
  • i (1≦i≦N)冊目の参考書の金額C_iと、j (1≦j≦M)番目のアルゴリズムの理解度の上昇幅C_{i,j}が記されたリスト(N行)

この条件を元に、M個全てのアルゴリズムの理解度が全てX以上となる参考書の買い方の組み合わせの内、必要な金額の最小になるときの金額を計算しなさい。

制約

  • 1≦N,M≦12
  • 1≦X≦10^5
  • 1≦C_i≦10^5
  • 0≦A_i,j≦10^5

制約のN,Mが非常に小さいです。この場合組み合わせはせいぜい2^{12} = 4096通りなので全探索を用いると良いでしょう。

といいたいところですが、今回は組み合わせの全探索なのでせっかくなので

「Bit全探索」を利用してみましょう。

まずは、 i (1≦i≦N)番目の商品の値段C_iと、 j(1≦j≦M)番目のアルゴリズムの理解度の上昇幅をN行入力します。

その後、全ての組み合わせにおいてbit全探索を行ってアルゴリズムの理解度の最小値がX以上となる組み合わせで、本を買ったときの合計金額をリストansに入れます。

最後に、リストansの最小値を出力すれば良いです。(ソート,ans[0]でもOK)

計算量はbit全探索でO(N 2^N)であるため、制約上では十分速いです。

 

Bit全探索は、組み合わせなどを考察するときに非常に役立つアルゴリズムなのでこの機会に覚えておきましょう。

 

コード: https://atcoder.jp/contests/abc167/submissions/13123166

 

以上、 AtCoder Beginner Contest 167 A ~ C問題の解説でした。

次回は体調を整えて参加出来るようにしようと思います。

YSF(J)H Beginner Contest 006　感想&解説

Nanashi(@WrongAccept)とcitrus(@citrus_WA)さんがWriterの、

"YSF(J)H Beginner Contest 006"が2020/5/6 20:00 - 21:30の間で行われましたー。

 

皆さん、お疲れ様でしたー。

そしてWriterのNanashi(@WrongAccept)さんとcitrus(@citrus_WA)さん、問題提供ありがとうございました！

 

私は　3完700点でした(ACD完)

 

では、問題を振り返っていきましょう

 

A問題 A - HelloWhiter

https://www.hackerrank.com/contests/ysfjh-beginner-contest-006/challenges/helloworld-16

問題概要:

"HelloWorld" と出力してから、改行し,"LoveNanashi" と出力せよ。

もはや解説不要です。"Hello World"、"LoveNanashi"と出力すればよいです

コード:

f:id:Rute_programming:20200512170402j:plain

▲A問題のコードです(Python3)



 

B問題 B - highway

https://www.hackerrank.com/contests/ysfjh-beginner-contest-006/challenges/nan1

Nan君は誰なのでしょうか...

問題概要:

以下のデータが与えられます。

  • ゲートの数Nと車の台数T
  • i (1≦i≦N)番目のゲートを通るのにかかる時間A_iのリスト
  • j (1≦j≦T)番目の車がインターチェンジに差し掛かる時間B_jのリスト

このデータをもとに一台も待つことなく車がインターチェンジに入れるかどうかを判定しなさい。

まず、N>Tの時、"Yes"と出力すればいいです。

理由としてはゲートの数が車の数より多いため、一台も待つ状況を考える必要がないからです。

N ≦Tの時

A_iのリストを降順に並べ替えます

B_jのリストを昇順に並べ替えます

以下のような処理を考えました。

  • 各ゲートの所要時間をまとめたリストをls[0]*Nとして定義
  • T回以下のループを行う(初期値i = 0 now = 0)
  • ls[now]にA[now]+B[i]を加算
  • now に1を加算し、now = Nなら now = 0とする。
  • 後は、リストの値の種類をcollections.Counterなどで集計し、リストの値の種類が1種類なら"Yes",そうでなければ"No"を出力する。

おそらくはこのような空いたゲートから順番に入れる貪欲法が想定解だと思ったのですが、全ケースACとはなりませんでした

解説を見て精進しようと思います！(追記:Priority Queueでした)

 

C問題 C - Triangle with five sticks

https://www.hackerrank.com/contests/ysfjh-beginner-contest-006/challenges/5-23

問題概要:

長さがそれぞれA_1,A_2,A_3,A_4,A_5である棒がある。(棒の長さはそれぞれ異なる)

この5本の棒のうち3本の棒を使って三角形を作成できる棒の組み合わせの数は何通りかを求めよ。

 

 三角形の成立条件を考えます。

長さがa,b,cである3本の棒があるとします。このときa,b,cについて

a+b ＞c , b+c ＞a, c+a ＞b

の3つの条件式が成り立っていればこの3本の棒で三角形を作成することが出来ます。

この時考えるのはこの5本の棒のうち3本を用いて三角形を作成する組み合わせ、

つまり5C3 = 10通り について上の式が成り立っているかどうかを考えればよいです。

よって、この問題は全探索によりO(10)で解くことが出来ました。

コード:

f:id:Rute_programming:20200512170414j:plain

▲C問題のコードです(Python3)

 

D問題 D - Error detection

https://www.hackerrank.com/contests/ysfjh-beginner-contest-006/challenges/1-241

問題概要:

5個の整数N_1,N_2,N_3,N_4,N_5が与えられます。

これらは、ある等差数列の相次ぐ数値であるはずだが、どれか1個の数値が間違っているようです。

間違っている数値が何番目かを出力し、また末尾に改行をいれ出力してください。

 

パターンで考えます。

以下、差のリストlsを

N_2-N_1 ,N_3-N_2 ,N_4-N_3 ,N_5-N_4で考えることにします。

  • N_1が間違っている時、N_2-N_1の値のみがlsの他の要素と異なっています。
  • N_2が間違っている時、N_2-N_1の値と、N_3-N_2の値の両方がlsの他の要素と異なっています。
  • N_3が間違っている時、N_3-N_2の値と、N_4-N_3の値の両方がlsの他の要素と異なっています。
  • N_2が間違っている時、N_4-N_3の値と、N_5-N_4の値の両方がlsの他の要素と異なっています。
  • N_1が間違っている時、N_5-N_4の値のみがlsの他の要素と異なっています。

よってこの問題は、以上の5パターンを考察することにより解くことができました。

コード:

f:id:Rute_programming:20200512170423j:plain

▲D問題のコードです

E問題はよく分かりませんでした。6^{1000}を考えるとおそらくオーバーフローするのでDPか何かだと思います。

 

以上、YSF(J)H Beginner Contest 006　感想&解説でした！

最後になりますが、Writerの皆さん　問題提供&コンテスト開催ありがとうございました＾＾

AtCoder Beginner Contest 166 感想 &解説

ABC参加記

AtCoder Beginner Contest 166が、先日5/3 21:00-22:40の期間で開催されました。

皆さん、お疲れさまでしたー。

私は3完で撤退。今回はD問題を落としたのがもったいない....

 コンテスト成績証

ユーザ名 Rute
コンテスト名 AtCoder Beginner Contest 166
順位 5398th / 11684
パフォーマンス 642
レーティング 561 → 569 (+8) Highest更新！
段級位 8 級
発行日: 2020/05/03

 

今回、問題名を見てふと思ったのが、"あれ？これABC164の問題名に似ているぞ"という問題があったということでした(後述するD問題のことです)。問題名が似ていたので難しいと思ったのですが、実際は頭を捻れば解ける問題でした。(Difficultyも茶色だったので難しいとはいえないです)

 

A問題 A?C

https://atcoder.jp/contests/abc166/tasks/abc166_a

問題概要:

ABC が開催された次の週には ARC が開催され、ARC が行われた次の週には ABC が開催されます。

先週開催されたコンテストを表す文字列 Sが与えられるので、今週開催されるコンテストを表す文字列を出力せよ。

(ほぼ問題文のままですが...)

 

単純です。 S = "ABC"なら"ARC"を出力、S = "ARC"なら"ABC"を出力すればよいです。

コード: https://atcoder.jp/contests/abc166/submissions/12706874

 

B問題 B - Trick or Treat

https://atcoder.jp/contests/abc166/tasks/abc166_b

問題概要: 

人数とお菓子の種類数を表すN,Kが1行、その後に

i (1≦i≦K)番目のお菓子を配った人数d、

K種類のお菓子を配ったデータA_{i,1}, A_{i,2},...A_{i,d}が[それぞれd個の要素で与えられ、これらが合計で2K行続けて入力されます。

N人のうち、お菓子が配られなかったのは何人かを出力せよ。

 

AtCoder Beginner Contestの問題では珍しいICPC形式の問題のように思いました。

 

問題を整理すると、

1～Nのうち、K行のA_{i,1}, A_{i,2},...A_{i,d}のデータに含まれない数字が何個あるか

 

という問題文に言い換えることができます。

よって以下のような実装を考えます。

 

snuke = [0]*Nとし、これをお菓子をもらったかどうかの判定に利用します。

  1. N,Kを入力し、その後以下のようなループをK回実行します。
  2. dを入力する
  3. A_{i,1}, A_{i,2},...A_{i,d}のデータを見て、snuke[ A_{i,j}-1 ]に1を加算する。(1-Indexなのでこのような処理をします)
  4. snukeのうち0の要素の個数を出力する。

 

計算量は合計のデータ数に依存するので、最大でO(NK)です。

よってこれは制約上では十分高速です。

コード: https://atcoder.jp/contests/abc166/submissions/12714791

 

C問題 C - Peaks

https://atcoder.jp/contests/abc166/tasks/abc166_c

問題概要:

以下のデータが与えられます。

  1. 展望台の個数N
  2. 展望台同士を結ぶ道の本数M
  3. 展望台i(1≦i≦N)の標高H_iのリスト
  4. M本の道のうち、j(1≦j≦M)番目の道において結んでいる展望台の組A_j,B_j(ただし A_j \neq B_j)

このデータをもとに、"いい展望台"がいくつあるかを求めなさい。

ただし、"いい展望台"の条件として

  • 展望台i (1≦i≦N)から1本の道でたどり着く展望台のうち、展望台iより高い展望台がなければ、それは"良い展望台"である
  • 一本の道を使ってたどり着ける展望台がない場合は、"いい展望台"である

という条件が与えられます。

 

問題を見て、実装ベースであると考えました。まず、この問題の出力例1について、簡単な図で示します。

f:id:Rute_programming:20200505153701p:plain

▲入力例1を図で示すとこのようになります

それぞれの展望台について

展望台1は展望台3より低いです。よって"いい展望台"とは言えません。

展望台2は展望台3よりも、また展望台4よりも低いです。よってこれも"いい展望台"とはいえません。

展望台3は展望台2よりも、展望台2よりも高いです。よってこれは"いい展望台"です。

展望台4は展望台2よりも高いです。よってこれも"いい展望台"です。

よって、出力すべき答えである"いい展望台"の数は2となります。

 

つまり、この問題は展望台同士のつながりを「無向グラフ」として考え、

各i (1≦i≦N)に対してのつながりで、展望台iが最も高ければそれが"良い展望台"になるので、その個数を出力すればいいということになります。

 

実装:

書くと長くなりますので省略しますが、基本的には

  • ans = 0と定義する
  • 入力されたデータで無向グラフ(連想配列)の作成
  • 各i(1≦i≦N)のつながりに対して、つながっている部分のHを参照し、i番目の展望台が最も高いかどうかを判定する。最も高い場合はそれが"いい展望台"になるので変数ans に1を加える。
  • ansを出力する

 

という実装をすれば解けます。　計算量はO(N+M)程度になると思います

(この実装の計算量は正確にはわかりません、申し訳ないです....)

コード: https://atcoder.jp/contests/abc166/submissions/12728071

ところで、この問題のDifficultyを見たときに唖然としました。灰Difficultyだったのです。グラフ実装の問題をこれほど多くの方が解けているのを見て、参加者のレベルが高くなっていることを感じました。)

D問題 D- I hate Factorization

https://atcoder.jp/contests/abc166/tasks/abc166_d

問題概要:

A^5-B^5 = Xを満たす整数の組(A,B)を一つ示せ。

120^5-119^5 が約10億くらいです。よって、(-120,120)の範囲でA,Bを定め、全探索すれば良いです。

計算量は-200≦A≦200, -200≦B≦200としたときに400^2 = 160000回の計算をすれば良いので、これは十分高速です。

(私はこの問題を解くときに愚直に式変形して解くことが出来ませんでした...)

コード: https://atcoder.jp/contests/abc166/submissions/12784477

 

以上、AtCoder Beginner Contest 166感想 &　解説でした。

今回も茶Difficultyの問題が解けませんでした...次回こそは4完を目指したいと思います！

AtCoder Beginner Contest 165 感想&解説

2020/05/02 (土) 21:10-22:50に、AtCoder Beginner Contest 165 が開催されました！

皆さん、お疲れ様でしたー。https://atcoder.jp/contests/abc165

 

私は、ABの2完で撤退。今回はC問題のDifficultyが1197と、ほぼ水色近くのDifficultyでしたが、D問題はそれに対し505でした。

(C問題とD問題でDifficultyに壁が出来るのはよく見るのですが、今回の場合は

C問題とE問題の間にD問題の谷が出来ていたように感じます。)

 コンテスト成績証

ユーザ名 Rute
コンテスト名 AtCoder Beginner Contest 165
順位 6478th / 11719
パフォーマンス 524
レーティング 565 → 561 (-4)
発行日: 2020/05/02

 

では問題について振り返っていきましょう。

 

A問題 A-We Love Golf

https://atcoder.jp/contests/abc165/tasks/abc165_a

 

問題概要:

A以上B以下の整数の範囲のうち、Kの倍数があれば"OK",なければ"NG"と出力せよ。

 

100点問題でループ....!? と最初戸惑いました。私はループを用いてA以上B以内にKの倍数があるかを判定しました。

(これは、O(B-A+1)で高速です。)

ただ、回答例を見るとO(1)で解く解法もあったので、そういう考え方もあるのかと納得させられました。

コード: https://atcoder.jp/contests/abc165/submissions/12578851

 

B問題 B-1%

https://atcoder.jp/contests/abc165/tasks/abc165_b

問題概要:

100×1.01^{N}≧Xが成り立つNのうち、最小のものを求めよ。

 

最初、Dice And Coinのようにlogを用いて解くのかと思っていました。

＜このような式変形を考えていました＞

X≦100×1.01^{N}

\log_{1.01} X≦ \log_{1.01} 100 +\log_{1.01} 1.01^N

\log_{1.01} X≦\log_{1.01} 100+ N

\log_{1.01} X- \log_{1.01} 100 ≦ N

(これを満たす最小のNが答え)

ただ、式変形が間違っていたかどうか分からないのですが、計算結果がサンプルの出力と異なっていました。

 

よくよく考えると、X = 10^{18}の時、答えは3760となっていたので、

100に1.01を掛け合わせて続け、掛け合わせた段階でXを超えていた時の年数を出力すればよかったのでした。(単純なループで良かったのです)

コード: https://atcoder.jp/contests/abc165/submissions/12592603

 

D問題 D - Floor Function

https://atcoder.jp/contests/abc165/tasks/abc165_d

 

問題概要:

A,B,Nという3つの整数が与えられます。

0≦x≦Nの範囲における、floor(Ax/B)-A×floor(x/B)の最大値を求めよ。

コンテスト中に解けなかったのですが、よくよく考えるとこれはwolframを利用すれば考えが容易になるということがわかりました。

 

wolframでこの関数のグラフを出力してみると、

f:id:Rute_programming:20200505144743p:plain

▲この関数を実行した結果のグラフです

このような出力になりました。よって、考えるのは0≦x≦B-1の範囲まででよく、

関数をf(x)としたときに、f(N)とf(B-1)の値のうち最大のものを出力すればよかったということになります。

計算量は言うまでもなくO(1)です。

コード: https://atcoder.jp/contests/abc165/submissions/12846652

(コンテスト後で復習しました。)

 

以上、AtCoder Beginner Contest 164 感想 &解説でした。

(今回は茶Difficultyが解けなかったのがつらい....)

AtCoder Beginner Contest 164 感想&反省

AtCoder Beginner Contest 164が終了しました。お疲れ様でしたー。

 

今回のコンテスト、気になったのですが...

 

ズバリ　"ABC早解きコンテスト" だったと思います。

(A問題、B問題、C問題を早く解くことと、ABC○○コンテストにあやかってこのような名称としました)

D問題がかなり難しかったみたいです...

f:id:Rute_programming:20200426221152p:plain

▲D問題難しかったですね....

 

Twitterなどで私が何度も言及した"C問題とD問題の間にある壁"が今回はより一層分厚かったように感じます。

個人的には、このような問題セットもアリだとは思うのですが、おそらく今回のコンテスト、早解きをした方ほどパフォーマンスが高くなる傾向になったのではないでしょうか？(私は3完早解き上位20人くらいに入っていたと思います)

 

A問題 A - Sheep and Wolves

https://atcoder.jp/contests/abc164/tasks/abc164_a

W ≧Sかどうかを判定し、W≧Sならば"unsafe",そうでなければ"safe"と出力すれば良いです。

コード: https://atcoder.jp/contests/abc164/submissions/12332240

 

B問題 B - Battle

 https://atcoder.jp/contests/abc164/tasks/abc164_b

以下のようなループを変数iを用いて有限回回します(私は10^5回としました)

iを2で割った余りが0なら、CをC-Bにする。

もしCが0以下ならば"Yes"と出力する。

iを1で割った余りが0なら、AをC-Dにする。

もしAが0以下ならば"No"と出力する。

 いずれの場合でも、何らかの文字列を出力した段階でループを終了する。

これにより、この問題を解くことが可能です。

コード: https://atcoder.jp/contests/abc164/submissions/12339019

 

C問題 C - gacha

https://atcoder.jp/contests/abc164/tasks/abc164_c

 

何種類の景品を手に入れたでしょう？と聞いて思いつくのは

全ての入力(S_i)をリストにして、それを集合にして　集合の要素の個数を出力する

ということです。

Pythonでは、set(A)を実行することにより、リストAの要素の集合を作成することが出来ます。

また、list(set(A))を実行することにより、リストAの要素の集合をリストとしたものを出力することが出来ます。

集合の要素の数はlen(list(set(A)))などで求めることが出来るので、これで求められる値を出力すればよいでしょう。

以下、方針です

k = [空のリスト]とする

N回以下のループを実行する

　　kに文字列S_iを挿入する

リストkの集合の要素の個数を出力する

計算量はO(N)です。

コード: https://atcoder.jp/contests/abc164/submissions/12341880

 

D問題 D - Multiple of 2019

https://atcoder.jp/contests/abc164/tasks/abc164_d

聞いたことがある気がするのですが

長さNの文字列の部分文字列の個数は \frac{N(N+1)}{2}個だったと思います。

<証明>

長さNの文字列において

長さ1の部分文字列の個数はN個です。

長さ2の部分文字列の個数は、連続した2文字を選ぶのでN-1個です。

・

・

長さNの部分文字列の個数は長さNの文字列しか考えられないので1個です。

 

以上のことから、部分文字列の個数は\sum_{k=1}^{N} k=\frac{N(N+1)}{2}個であるといえます。

今回の制約では、1≦|S|≦2×10^5だったので、最大で20000100000(200億)個の部分文字列を考えないといけなかったのです。当然、PythonどころかC++でも列挙するまでにTLEになりそうだと思い、さじを投げました。orz

 

今回は先述した通りABC早解きコンテストになったということで、予想よりパフォーマンスが高く出たと感じた方が多かったと思います。私もおそらく初の水パフォになりそうです。

 

以上、ABC164の感想&反省でした。

(レートが冷えてしまった方、私を恨まないようにお願いしますよ....)

yukicoder 問題　"乱数サイ"

A問題のWriterをしておりました、Ruteです。

今回はA問題の作問を担当させて頂きました。

それでは早速問題から振り返っていきましょう。

 

問題文:

一般的に乱数サイとは

0から9までの数字がちょうど2回ずつ現れるようになっているサイコロのことをいいます。
今回は、0からNまでの整数がちょうどK回ずつ現れるようになっているサイコロを考えます。
(ただし、それぞれの整数が等確率で出るものとします)

このサイコロの出目の期待値を求めて下さい。

 

この問題の解法は２つあります。

解法１：

ans = 0とします

(0,N)で以下のループを回します。(変数をiとします)

ここで、ansに \frac{i}{N+1}を足し続けます。

本来はK回足すので分子がK倍、さらに分母も(N+1)×Kとなる必要がありますが、分子分母のKの部分が消えるので、事実上は上の式を足し続ければよいです。

計算量はO(N)でしょう。

 Python3のコードです:

  1. N,K = map(int,input().split())
    ans = 0
    for i in range(0,N+1):
    ans += i/(N+1)
    print(ans)

解法２：

N = 3で、Kの数を増やしたとき期待値がどのようになるかを考えてみましょう。

(解法2の計算式では分子が0のものは考えないことにします)

K = 1

\frac{1}{4}+\frac{2}{4}+\frac{3}{4} = \frac{6}{4} = \frac{3}{2}

K = 2

\frac{1}{8}+\frac{1}{8}+\frac{2}{8}+\frac{2}{8}+\frac{3}{8}+\frac{3}{8} = \frac{12}{8} = \frac{3}{2}

K = 3

\frac{1}{12}+\frac{1}{12}+\frac{1}{12}+\frac{2}{12}+\frac{2}{12}+\frac{2}{12}+\frac{3}{12}+\frac{3}{12}+\frac{3}{12} = \frac{18}{12} = \frac{3}{2}

 

既に気づいた方もいるかも知れませんがKを変更しても期待値の総和は変化していないのです。

では次に、K = 3で、Nの数を増やしたとき期待値がどのようになるかを考えてみましょう。

N = 1

\frac{1}{6}+\frac{1}{6}+\frac{1}{6} = \frac{3}{6} = \frac{1}{2}

N = 2

\frac{1}{9}+\frac{1}{9}+\frac{1}{9}+\frac{2}{9}+\frac{2}{9}+\frac{2}{9} = \frac{9}{9} = 1

N = 3

\frac{1}{12}+\frac{1}{12}+\frac{1}{12}+\frac{2}{12}+\frac{2}{12}+\frac{2}{12}+\frac{3}{12}+\frac{3}{12}+\frac{3}{12} = \frac{18}{12} = \frac{3}{2}

 

実は、答えは任意のNに対してKの値にかかわらず一意に定まることがわかります。よって答えはN/2となり、計算量O(1)で計算することが可能です！

Python3のコードです:

  1. N,K = map(int,input().split())
  2. print(N/2)

(帰着させると0からNまでのサイコロを1個振ったときの期待値を求めることになります)

(この解法を思いついた方は果たして何人いるのでしょうか....)

以上、A問題の解説でした。

 

難易度について、また問題の感想についてコメントなどでぜひ教えて下さい！

(コメントの一部を、Twitterで匿名で紹介するかもしれません。)