1

ABC221 茶色コーダーが解けた所まで

5 min read

AtCoder Beginner Contest 221

https://atcoder.jp/contests/abc221

ABC221の問題を、本番で自分が解けた所までの解説です。

レートが74上がって655になりました。
緑まであと150…!年内入緑まで頑張ります…!

自分の中でも中々正確に理解できていない部分を、文字として起こすのは大変難しいですね…。

A - Seismic magnitude scales

  • Difficulty: 10

https://atcoder.jp/contests/abc221/tasks/abc221_a

n乗する話

  • マグニチュードが1大きくなる度に32倍する
    • マグニチュードの差だけ、32を掛けていくと答え
  • コーナーケースも考える
    • A=Bの時は…?
      • n0=1n^0 = 1となるので、やっぱり差で大丈夫



B - typo

  • Difficulty: 58

https://atcoder.jp/contests/abc221/tasks/abc221_b

操作

  • 文字列SSの隣り合う2文字を選び、入れ替える

    • 上記操作を0回、もしくは1回行う
      • 行わない事もある
  • 文字列SSと文字列TTが等しいならYes、そうでないなら、操作を行う

どこで操作を行う?

  • 文字列SSTTを先頭から1文字ずつ見ていき、最初に異なった文字と、その1つ右の文字列で操作を行う
    • 最初に異なった文字が、文字列の一番最後の文字なら操作をするまでもなくNo
    • 操作を行った結果、SSTTが等しいならYes
      • 操作を行った後も、SSTTが等しくないなら、No



C - Select Mul

  • Difficulty: 379

https://atcoder.jp/contests/abc221/tasks/abc221_c

積の最大値

  • ちっちゃいケースで考える
  • 集合A:{1,4,6,8,14}と、集合B:{3,5,6,8}が存在した時、
    • Aの中から1つ、Bの中から1つ選んでA×BA\times Bを行った時の最大値は?
      • Aの中で一番大きい数字:14と、Bの中で一番大きい数字:8をかけ合わせた値が答え=112
    • 一番大きい数と一番大きい数をかけ合わせたら一番大きくなる!

大きな数の作り方

  • これもちっちゃいケースで考える
  • 文字列:'521357'の順序を並べ替えて、一番大きい数を作ってみよう
    • 左から順に大きい数字を置いていくと、755321
    • これ以上大きい数字は作れないので、これが答え
    • 降順にソートしてあげると一番大きい数ができる!

整数Nを2つの数に分離する分け方:Bit全探索

  • Nの数値が大きい…?
    • 結局桁数毎にグループ分けするので、999999999:9桁で済む
    • Bit全探索が使えそうですね
      • 292^9個の分離で全パターン網羅できるので、間に合いそう



D - Online games

  • Difficulty: 832

https://atcoder.jp/contests/abc221/tasks/abc221_d

1日ずつシミュレーションすると…

  • 最大で10910^9+10910^9の長さの配列が必要
    • もちろんTLEする。さてどうしよう…

ログインしている人数が変化する日を考える

  • Aさんがログインした日、Aさんがログアウトした日
    • Aさんがログインする日より前、Aさんがログアウトした日より後にAさんは居ない
    • Aさんがログインした日〜Aさんがログアウトした日、Aさんは常に居る
  • 人数が変わる日に、何人増えた?何人減った?を記録しておく
  • 日付の順番で以下の処理を行う
    • 答えの配列[今ログインしている人数] += 人数が変動した日 - 前回人数が変動した日
    • 今ログインしている人数 += 変動した人数[人数が変動した日]
    • 前回人数が変動した日 = 人数が変動した日
  • いもす法、座標圧縮の考え方…?であってる、と思われる(自信無い)



Discussion

コメントにはログインが必要です。