2

ABC222 茶色コーダーが解けた所まで+あと1問

5 min read

AtCoder Beginner Contest 222

https://atcoder.jp/contests/abc222

ABC222の問題を、本番で自分が解けた所+1問の解説です。

3完だったり、操作ミスでB問題にA問題のソース提出してREだったり、と散々でした…。
一応ギリギリHighestは+6で微増…しょっぱーい。
次は甘えずちゃんと4完…!

A - Four Digits

Difficulty: 5
https://atcoder.jp/contests/abc218/tasks/abc218_a

文字列としての長さを見る

  • len(S)で長さを測って、足りない分の0を補完する

文法一発ネタ

  • S.zfill(n)で、n桁の数値にしてくれる(右詰め、0埋め)
    • 今回は4桁なのでn = 4

入力の型を確認する

  • 最初からNをstrで入力させるとその後楽ですね
    • 脳死でintで入力させるのはよくない。つい手癖でint(input())してしまうの反省。



B - Failing Grade

Difficulty: 9
https://atcoder.jp/contests/abc222/tasks/abc222_b

愚直にループで1つずつ確認

  • forループで配列内要素を順に見ていく。条件以上であればカウント。
    • 内包表記で一括に書けると格好いいですね。
    • 可読性考えると愚直ループでも問題無い、かも、しれない。





C - Swiss-System Tournament

Difficulty: 367
https://atcoder.jp/contests/abc222/tasks/abc222_c

実装面倒くさい系シミュレーション

  • 1N501 \leq N \leq 501M1001 \leq M \leq 100で制約小さいので、愚直に実装する方向。

Point1:関数を自作する

  • じゃんけんの結果を求める部分は関数として分けとこうね
  • ソースごちゃごちゃしちゃうからね
  • 2人の手を引数として与えると、どっちが勝ったか教えてくれる関数
    • Point2:2人の関数を文字列として「'GP'」みたいな引数1つにすると判定楽かも(スタイリッシュ?)
    • Point3:返り値を決める時にちょっと悩んで実装すると、後々のコードが楽になる
      • これ本番で悩む余裕は個人的にはまだ無さそう…実力が足りない。

ソートに関して

  • 2次元配列のソートはlambda式とか、色々手法がある。
  • 個人的には-1を掛けるのが楽かな、と思う
    • 勝数も選手番号も、小さい順にソートしたい
      • 勝ち数はみんな0からスタート
      • 1回かつ毎に「-1」してあげる
      • 3回勝ったら「-3」



D - Between Two Arrays

Difficulty: 865
https://atcoder.jp/contests/abc222/tasks/abc222_d

愚直にDPしてみると…

  • dp[i][j]dp[i][j]:要素iまで確認していて、C[i]=jC[i]=jである場合の数

  • この時、計算量がO(NM2)O(NM^2)となりTLEとなってしまう。

  • どこかで計算量改善をしなきゃいけない

いもす法

  • dp[i][j]dp[i][j]から、dp[i+1][A[i]:B[i]]dp[i+1][A[i]:B[i]]の要素を考える時にいもす法が使えるのでは?
    • dp[i+1]dp[i+1]行を、いもす法で一括計算すると割と余裕でAC
    • 計算量等の詳細な考察までは自分のちからが及ばず…。
    • これは時間内に解きたかった…!



Discussion

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