2019年4月13日 | ブログ記事

初心者がABC106を全完出来たよろこび【新歓ブログリレー36日目】

OrangeStar

こんにちは。実は今日4/13が誕生日の、情報工学系4年、オレスタです。祝ってね。

普段はサウンド班として活動している私ですが、最近は競技プログラミングにもハマっています。というわけで、プログラミング系の記事も書いてみようかな、と。
そっちに興味ある新入生多そうだし。

競技プログラミングとは、簡単に言うとプログラミングの問題を解くコンテストです。その中でも、AtCoderという会社が実施しているABC(AtCoder Beginner Contest)は、比較的初心者向けのコンテストであり、traPでも多くのメンバーが参加しています。
ABCでは毎回4問出題され、難易度が低い方からA~Dと問題番号が付けられています。D問題が解けるようになったらABCは卒業、ワンランク上のARC(AtCoder Regular Contest)に参加する…という流れになっているようです。

初めはC問題もおぼつかなかった私ですが、このごろはD問題まで何とか解けるようになりました。この成長のよろこびを共有したいな、ということで、初めてABCを全完出来た、第106回の問題を解説してみようかなと思います。

注意

当たり前ですが、ABC106のネタバレを含みまくっています。競技プログラミングに興味があり、自力で解いてみたい! という人は、先に自分で解いてから読んでくださいね。

AtCoder Beginner Contest 106

A問題

問題文

縦Aヤード、横Bヤードの畑に、下図のような形で縦横に1ヤードの道を作る。この時、畑の面積は?

( ・ω・)小4の面積の問題で良く出てくる等積移動だな… S=(A1)(B1)S=(A-1)(B-1)で行けるはず!

B問題

問題文
200以下の自然数Nに対し、以下の条件を満たす数の個数を求めなさい。

( ・ω・)約数の個数って言えば…素因数分解を使うんだよね、確か以下の3パターンのどれかだ。

a7:1/a/a2/a3/a4/a5/a6/a7a^7: 1/a/a^2/a^3/a^4/a^5/a^6/a^7
a3b:1/a/a2/a3/b/ab/a2b/a3ba^3b: 1/a/a^2/a^3/b/ab/a^2b/a^3b
abc:1/a/b/c/ab/bc/ac/abcabc: 1/a/b/c/ab/bc/ac/abc

( ・ω・)a7a^7の最小値は37=21873^7=2187… うん、あり得ない。
( ・ω・)a3ba^3bだったら…33×5=1353^3\times 5=13533×7=1893^3\times 7=189 …だけだな
( ・ω・)abcabcはどうだ…? 3×5×7=1053\times5\times7=1053×5×11=1653\times5\times11=1653×5×13=1953\times5\times13=195の3つっぽい。
( ・ω・)じゃあ、105、135、165、189、195の5つかな? あとは条件分岐を連打すれば…

A = int(input())

if(A<105):
    print(0);
elif(A<135):
    print(1);
elif(A<165):
    print(2);
elif(A<189):
    print(3);
elif(A<195):
    print(4);
else:
    print(5);

( ^ω^)スマートさゼロの解答が出来たよ!

※後で気づいたこと↓
オンライン数列大辞典というサイトに「約数が8個の整数からなる数列」という非常に便利なモノがありましたので、ここから「200以下の奇数」を抜き出して来ればそれで済みました。

C問題

問題文
1~9が並んでいる数字列に対し、各数字について以下のような操作を行う。
【1→1】
【2→22】
【3→333】
【4→4444】
…以下9まで続く…

例えば、「123」という数字にこの操作を行うと「122333」となり、もう1回この操作を行うと「12222333333333」となる。

さて、ある数字列Sに対しこの操作を5000兆回行ったとき、左からK文字目は何になるか答えなさい。
(条件:Sは1文字以上100文字以内の数字列、Kは101810^{18}以下の自然数) ←コレ超重要

( ・ω・)「2をnn回操作すると、2が2n2^n個並ぶわけね、じゃあ250000000000000002^{5000000000000000}っていくつなんだろう?」

print(2**5000000000000000);

#その後、消息が途絶える

( ;ω;)ウッ[1]
( ˘ω˘)待てよ…

log102=0.3010\log_{10}2=0.3010
5000log102=15055000\log_{10}2=1505

( ・ω・)250002^{5000}の時点で101810^{18}なんて余裕で超えるじゃん、つまり…

★K文字目の候補

  • 最初からK文字目までずっと1が続くときだけは、答えは1になる!
  • K文字目までに1以外の数字があるのなら、その数字が答えになる!

( ・ω・)どうやって実装しようか…

★考えた実装方法

  • Sを最初から順番に1文字ずつiに代入する
    • もしもiが1だったら…
      • その時点で「1文字目」を聞かれているのなら答えは1だ!
      • まだ先を調べる必要があるなら、1文字先に進むからK文字目までの距離は1減る。Kを1減らす。
    • もしもiが1じゃなかったら…
      • この後その文字(i)がめちゃくちゃたくさん続くわけだから、iの中身を出力すればいい!

( ^ω^)完全に理解した
、あとはコード書けばええやん

S = str(input());
K = int(input());

for i in S:
    if(i=="1"):
        if(K==1):
            print("1");
            break;
        else:
            K-=1;
    else:
        print(i);
        break;

D問題

( ・ω・)これまでD問題は解けたことがないんだけど、とりあえずやるだけやってみるか~

https://beta.atcoder.jp/contests/abc106/tasks/abc106_d
NN個の駅を結ぶ電車があり、その駅には「1、2、3… …N」というナンバリングがされている。
この路線にはMM本の電車が走っており、それらの電車が走る区間が駅番号で示されている。

このとき、「駅番号pから駅番号qの区間内だけを走る電車はいくつあるか?」という問いがQQ個与えられるので、
これらの問いにすべて答えなさい。
(条件:N500,M200000,Q100000N\leq 500, M\leq 200000, Q\leq 100000)

( ・ω・)制限時間(3sec=300~3000万くらい3\text{sec}= \text{300~3000万くらい})を考えると、MQ(=200億くらい)MQ(=\text{200億くらい})では到底間に合わなさそうだな…
( ・ω・)あれ? N500N\leq500だけヤケに低くない? N2N^2だったら間に合うのか?

★思考回路1

  • 各駅を始点と終点とするような組み合わせはN2N^2個考えられる(逆走とか同じ駅とかは面倒なので無視!)
  • 2重配列使えば楽なんだろうけど、pythonの2重配列って使いこなせないんだよな…無理矢理1重(?)の配列にしちゃおう。
    • 出発駅i、終着駅jに対して、k=(i1)×N+(j1)k=(i-1) \times N + (j-1)とすれば、2重配列を1重にできるはず。

( ・ω・)出発駅i、終着駅jである電車の数を表す配列として「trainList」っていうのを作ろう。
( ・ω・)そうしたら、trainListと別に「ansList」って答えを入れる配列を作って、そいつでfor文回せば行けるんじゃね?

(ここでしばらく考える)

( ・x・)よく考えたら、このままだとfor文回すにしても順番が上手く行かない気がしてきた…

※例を挙げて説明すると、「区間1~6」と「区間2~7」を先に求めれば「区間1~7」の計算に使える! などと考えたのですが、このままでは、区間2~7の計算は区間1~7の計算よりも後に行われることになるため、利用できない…と考えました。

( ^ω^)そうだ、「始点と終点」じゃなくて「始点と区間の長さ」で配列作れば行ける!

★思考回路2

  • 今度は、k=(ji)×N+(i1)k=(j-i) \times N + (i-1)ってすれば、順番で悩まずに済む!
    • さっきは「始点を後ろにずらしていく」という考え方をしたが、区間の長さを増やしていくという計算をすることで、長くする際に元の(短い時の)値を利用することができる!(さっき説明した問題点を解決できる!)

( ・ω・)これで、答えの配列ansListを次のように実装すれば…行けるのでは?

(i<Ni<Nのとき → 区間の長さが0のとき)
ansList[i]=trainList[i]\text{ansList}[i] = \text{trainList}[i]

(i<2Ni<2Nのとき → 区間の長さが1のとき)
ansList[i]=trainList[i]+ansList[iN]+ansList[iN+1]\text{ansList}[i] = \text{trainList}[i] + \text{ansList}[i-N] + \text{ansList}[i-N+1]
 ※区間が1短い場合の計算結果は、既にansListで求めたのでそれを使用する!
 [iN][i-N]→始点が同じで区間が1短い
 [iN+1][i-N+1]→始点が1つ先で区間が1短い(つまりは、終点が同じで区間が1短い)

(それ以外のとき → 区間の長さが2以上のとき)
ansList[i]=trainList[i]+ansList[iN]+ansList[iN+1]ansList[i2N+1]\text{ansList}[i] = \text{trainList}[i] + \text{ansList}[i-N] + \text{ansList}[i-N+1] - \text{ansList}[i-2*N+1]
 ※始点側が1短い区間と終点側が1短い区間とを比較すると、重複した部分が出てくる。
 例)区間[3,7]で考えると、区間[3,6]と区間[4,7]における答え、そして[3,7]を走る電車の数を足せばよい…のだが、
   区間[4,6]は[3,6]と[4,7]の両方でカウントしているため引く必要がある。
   イメージは集合の演算で、AB=A+BABA\cup B=A+B-A\cap Bという感じ。
 i2N+1i-2*N+1→始点が1つ先で区間が2短い(つまりは、始点が1つ先で終点が1つ手前)

(;・ω・)これで…どうだ!! ←緊張

画像.png

≫≫≫勝利≪≪≪

キタ━━━━━━━(゚∀゚)━━━━━━━!!

※このあたりで喜びのあまり絶叫、親に説教を受ける。

はい、という感じのABC106でした。読んでいただきありがとうございます。
ちなみに、今ではAtCoderのレーティングは1212(水色)になりました。1200を超えるとABCは卒業になる[2]ので、いよいよ次のステップに進んだんだなあ、という気持ち。
これからもがんばります。よろしくおねがいします。

--3

余談

今夜、AtCoder Beginner Contest 124が開催されるようです!
競技プログラミングに興味があるのであれば、ぜひチャレンジしてみてください!
AtCoder Beginner Contest 124


  1. なぜ消息が途絶えたのかというと、かけ算を5000兆回やるとなると、いくら計算が得意なパソコンだとしても時間がかかるから。私のパソコンでは丸1日かかっても終わりません。東工大が誇るスパコン「TSUBAME」でさえ、数十秒はかかってしまうのではないでしょうか…。 ↩︎

  2. 正しくは、参加してもレーティングが変化しなくなるだけで、参加することはできます。 ↩︎

この記事を書いた人
OrangeStar

traPのサウンド班で作曲をしています! また、個人製作で音楽ゲーム「アイシューター」を制作しています! tw→@hapdap

この記事をシェア

このエントリーをはてなブックマークに追加

活動の紹介

カテゴリ

タグ