キーエンス プログラミング コンテスト 2020 参加記

2020/1/18のキーエンス プログラミング コンテスト 2020の参加記です。

ちゃんと理解して進みたいので解法とか考察を書きます。

---ここでコンテスト---

終わりました。順位表です。

順位表

50分AC2完で、レートは微減...ちょっと辛いです。 流れとしては

1. Aを通す
2. Bを見る
3. 「あ、これ本で見たことあるな」となって実装を始める
4. 一生通らない
5. 順位表見たらみんなC通してるので簡単なのかな？と気づく
6. Cがギャグだった
7. Bは通らない

でした。

それぞれの問題をどう通したかを書いていきます。厳密性は問うことはあっても責めないでくれると嬉しいです。

---

A問題

ざっくり言うと「H * Wのマス目を縦横一列ずつ塗りつぶすとき、最小で何回やればNマス以上塗りつぶせるか？」という問題です。

まず、方針として「縦か横を選んでその方向だけを塗りつぶす」ということがわかります。なぜなら、最高効率で埋めるためには「被りが無い」ことが必要(多分)だからです。
よって、縦か横のどちらかを選ぶことになりますが、これはもちろん長い方を選ぶことになります。 なぜなら、その方が短い手数で埋めることができるからです。

長さXの列(または行)を選んでNマスを埋めるのに必要な手数は、ceil(N / X)で表せます。(ceilは切り上げ関数)。よって答えは以下のようになります。

H = int(input())
W = int(input())
N = int(input())
big = max(H, W)
from math import ceil
print(ceil(N / big))

---

B問題

日本語が弱いので問題文は自分で読んでください。
これを見たときの某「あ、これ見たことあるな、まふゆちゃんがくれた本だ」

なんか名前がついているらしくて、区間スケジュールというらしいです。
方針としては、Xでソートしてから右端を更新していけばいいです。イメージ的には、実際のエリアにロボットを一つずつ置いていくイメージです。

どういうことかというと、

1. 与えられたX, Lをペアにしてまとめてから、Xでソートします。
2. 右端を適当に設定します。
3. XLをループで回していきます。
4. その時見ているロボットの左端はX - Lです。右端はX + L + 1です。一つ前の右端が今の左端と被っていなければ(左端 > 右端)、普通に置きます(ansを1増やす)。 被っていたら、右端が小さい方に置換します。それでよい理由は後で説明します。
5. さいごにansを出力すればよいです。

右端更新らへんの理由

• もし後の奴のほうが右端が長い場合
  • 普通に邪魔なので置きません。右はできるだけ短い方がいいですもんね。
• 前の奴のほうが右端が長い場合
  • この場合、右端を短くしたいのは当然として、あとの奴の左端が前の左端より必ず右側にあることがわかるので問題が無く、置換します。

コードはこれでACしました(コンテスト終わって1分後にACしました、カス)

N = int(input())
XLlist = [tuple(map(int, input().split())) for _ in range(N)]
XLlist.sort(key=lambda x: x[0])
ans = 1
x, l = XLlist[0]
rl = x + (l - 1)
for x, l in XLlist:
    ll = x - l
    if ll <= rl:
        rl = min(rl, x + l - 1)
    else:
        ans += 1
        rl = x + l - 1

print(ans)

---

C問題

草

二つの和にする必要はありません、SをK個用意して、それ以外は適当に埋めればよいです。ちなみにS + 1とかS - 1にすると10**9, 1で落ちるので、適当に処理してください(値を決めてもよいし、modをとってもよさそうです)

N, K, S = map(int, input().split())
ans = [str(ele) for ele in ([S] * K + [(S - 1) if S != 1 else 10**9] * (N - K))]
print(" ".join(ans))

感想

いや悔しい

Bは見えたのに< と <=で通らなかったのは本当につらい

今からABCがあるので頑張ります！