AtCoder 第一回日本最強プログラマー学生選手権-予選- A - Takahashi Calendar (Go)

irisruneです。残念なことに仮眠したらコンテスト時間に寝過ごしてしまったので不参加でした。

問題

atcoder.jp

たまには簡単めの問題をということで。条件が少し複雑ですが愚直にやれば解けるはずです。

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    m, d := nextInt(), nextInt()

    ans := 0
    for mth := 1; mth <= m; mth++ {
        for dth := 1; dth <= d; dth++ {
            switch {
            case dth/10 <= 1:
                continue
            case dth%10 <= 1:
                continue
            case (dth/10)*(dth%10) == mth:
                ans++
            default:
                continue
            }
        }
    }
    fmt.Println(ans)
}

制約条件上、全部で高々通りしかないので愚直に全通り試してみることで解くことができます。満たすべき条件が少々複雑なので整理すると、

1. が2桁の整数
   1. を10で割った商が0ならば1桁なので除外すればよい。
   2. を10で割った商が10以上ならば3桁以上なので除外すればよいが、制約上あり得ないので無視できる。
2. の1の位が2以上
3. の10の位が2以上
   1. 条件1.1.と同時に確認できる。
4. がの1の位と10の位との積

となります。上記の通り、条件1.については個別に確認する必要はなく2.～4.を確認すればよいので、条件式を3つ用意すれば条件を満たすことの判定を行うことができます。

計算量を減らす方法について（おまけ）

少しあっさりすぎたので、おまけとして計算量を減らすことを考えてみます。2通りアプローチがあり、これらは組み合わせることもできます。

制約条件をさらに制限する

満たすべき条件から、考慮する値の範囲を絞ることができます。

1. 
   1. 条件を満たすmは合成数（1でも素数でない自然数）となる必要があるため、である。
   2. が2桁の整数であるため、である。
2. 
   1. の10の位と1の位がそれぞれ2以上となる必要があるため、である。
   2. が2桁の整数であるため、である。

与えられた制約条件上では以上の条件を追加しても定数倍最適化にしかなりませんが、例えばなどという条件が設定された場合でも計算量が増大せずに済みます。

条件から候補を求める

月または日を定めると、候補となる月または日を絞ることができます。そのため、月または日の一方を全通り試してもう一方は候補となる値を取り得るかどうかチェックするという方式で解くことができます。

例えば月から日を求める場合、日の1の位として2から9までの値を考えることで候補となる日を絞り込むことができます。あとは与えられたと候補日を比較することで答えを求めることができます。

この場合の計算量はとなるため、特にが大きい場合は（問題の制約上では高々10倍程度ですが）高速化が見込めます。

2つの手法を組み合わせる

制約条件を絞り込んだ上で月あるいは日のみ全通りチェックするということも可能です。

下記では月の範囲を絞りこんだ上で月から候補日を求めるという手法を用いています。日から候補月を求める手法の方が候補月が1つに定まるためかなり簡単な上に、計算量も削減できると思います。

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    m, d := nextInt(), nextInt()

    ans := 0
    for mth := 4; mth <= m; mth++ {
        if mth > 81 {
            break
        }
        for div := 2; div <= 9; div++ {
            if mth/div < 10 && mth/div > 1 && mth%div == 0 {
                if (mth/div)*10+div <= d {
                    ans++
                }
                if div*10+(mth/div) <= d {
                    ans++
                }
            }
        }
    }
    fmt.Println(ans / 2)
}

雑記

• AtCoder ProblemsのDifficultyの高さに驚きましたが、新形式のABCがARCを内包するようになったのでARC（相当）のコンテストも難易度が上がるのは当然かもしれません。
  • （いつもの企業コンとは違うけれども）企業コンなので、最近のABCによくいるD（,E,F）問題だけ解いて1完という人がいなかったということもあり得ますね。
    • AGCにもいない気はしましたが、こちらはA問題の配点が空気なので影響がないのかもしれません。