Vercel LogoMagicode
1

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

5 min read

AtCoder Beginner Contest 225

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

94分で4完+3WA。残り数分で何故かF問題に特攻するも無事玉砕。 茶diffまではもっと安定させたいですね。

A - Distinct Strings

Difficulty: 12

if文で条件分岐してあげる(想定解法、スマート)

3つのパターンに場合分けしてあげると良し

  • Sに含まれる3文字が全て同じである
    • 答えは明らかに1通り
  • そうではなく、Sに含まれる3文字が互いに異なる
    • 答えは3!=6通り
  • 上記2つのどちらでもない場合、Sは2文字が等しい+1文字だけ異なる文字で構成されている
    • 答えは3通り

想定解

[ ]

力技(本番で恥ずかしげもなくこちらを提出)

[ ]

B - Star or Not

Difficulty: 62

グラフ理論のお話

  • 木とか、頂点とか、枝とかの説明はwiki参照…余裕があったら整理して纏めたい…。

結局どういう問題?

  • 頂点の数と、頂点の数より1つ少ない辺(=どの2点が結ばれているか)の情報が与えられます
  • 与えられた情報からできたグラフの形が、
    • 「どこか1つの頂点と、他すべての頂点に1本ずつ辺が結ばれているか」を判定してください
    • 「他全ての頂点(N-1)の数、辺が繋がれている頂点はありますか?」と言い換えても良いかもしれません
[ ]

C - Calendar Validator

Difficulty: 326

タイトルから推察

  • カレンダーバリデーター:カレンダー検証機…?
  • 左上が1のカレンダー、最終日が(10100×710^{100} \times 7)日のものを考える
    • その縦長なカレンダーから、入力された行列Bが切り出せるかの判定

カレンダーの切り抜きであるために必要な条件を考える

  1. 特定の要素Bi,jB_{i,j}は、1つ左の要素Bi,j1B_{i,j-1}に1を足した値であること
  2. 特定の要素Bi,jB_{i,j}は、1つ上の要素Bi+7,jB_{i+7,j}に7を足した値であること
  3. 7の倍数が出てきて良いのは、最終列だけ
[ ]

D - Play Train

Difficulty: 778

データの管理方法

  • 特定の電車に対して、
    • 電車iの前に繋がっている電車は?
    • 電車iの後ろに繋がっている電車は?
  • この2つを、それぞれの配列で管理する
  • クエリ3が来たら、前に繋がっている電車と後ろに繋がっている電車を芋づる式に引っ張り出す
[ ]

Discussion

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