kmjp's blog

競技プログラミング参加記です

CODE FESTIVAL 2014 予選A : Python練習編

CODE FESTIVAL 2014 予選に参加。
Dにちょっと苦戦したけど、何とか順調に完答。
http://code-festival-2014-quala.contest.atcoder.jp/assignments

A - CODE FESTIVAL 2014

入力に2014を追加して出力せよ。
そのまま出すだけ。

import sys

a=raw_input().strip()
print a+"2014"

B - とても長い文字列

文字列Aを繰り返した文字列のうち、B文字目を答えよ。
Aの文字数で剰余を取ればよい。

import sys

A=raw_input().strip()
B=input()
print A[(B-1)%len(A)]

C - 2月29日

西暦A年~B年の間で閏年が何回あるか答えよ。
1~B年の閏年から1~(A-1)年の閏年を引く典型問題。

import sys

A,B=map(int,raw_input().strip().split())

def leap(v):
	return (v/4)-(v/100)+(v/400)

print leap(B)-leap(A-1)

D - 壊れた電卓

数値Aが与えられる。
K種類の数字で表現できる整数のうち、Aとの距離が最小のものを求め距離を答えよ。

[今の桁][使用した数字のbitmask]を引数として上の桁から再帰的に処理していく。
今d桁目を決めるとして、d桁目を0~9総当たりする。

  • d桁目にAのd桁目より大きな数字を入れる場合:それより下の桁はもっとも小さい数字で確定
  • d桁目にAのd桁目より小さな数字を入れる場合:それより下の桁はもっとも大きい数字で確定
  • d桁目にAのd桁目と同じ数字を入れる場合:d-1桁目を再帰的に処理

後は再帰処理の過程でK種類を超える数字を使わないようにする。
Leading Zeroは数字を使った数にカウントされないので注意。

まとめ

Dだけずいぶん難易度上がるな。