今日の競プロ（2015/05/19）

前回サボったARCの問題を解く．

ARC 039 A

問題

A: A - B problem - AtCoder Regular Contest 039 | AtCoder

回答

Submission #408274 - AtCoder Regular Contest 039 | AtCoder

最初の方針としては絶対値をとって～
と思っていましたが，なんか違いそうなので，回答を見たら，総当りで良かったみたいです．
その通り，総当りで実装しました．
基本的にpythonでは途中の文字を書き換えることはできないので（多分，エラーになるよ，st[1] = "h"とかはできない），一旦リストに落としなおしてから，変換して，文字列で～ みたいな処理になりました．
あとは数値の最上位桁は0にできない，ということだけ重要ですね．

def f(i, x, idx):
    li = list(str(i))
    li[idx] = str(x)
    return int("".join(li))
 
A, B = map(int, input().split())
clac = lambda s, x, idx: int(str())
amax = max(f(A, 9, 0) - B, f(A, 9, 1) - B, f(A, 9, 2) - B)
bmax = max(A - f(B, 1, 0), A - f(B, 0, 1), A - f(B, 0, 2))
print(max(amax, bmax))

ARC 039 B

問題

B: 高橋幼稚園 - AtCoder Regular Contest 039 | AtCoder

回答

80点分：
Submission #408286 - AtCoder Regular Contest 039 | AtCoder

100点分：
Submission #408287 - AtCoder Regular Contest 039 | AtCoder

4 10 の入力例を見た時に，なんとなく組み合わせじゃないかな？ と思いました．（N)C(K % N)です．*1
その方針で80点分まではなんとかなったのですが，N < K の時の処理がよくわからずに答えを見ると…．M < K のときは （N - K + 1)C(K) で良いみたいですね．こちらは自力で計算式が発想できませんでした．（計算しなければいけない範囲はわかっていたのですが）

実装はreduceを試しに使ってみました．python3では，組み込みではないのでimportが必要です．

from functools import reduce
from operator import mul
 
N, K = map(int, input().split())
combi = lambda i, j: reduce(mul, range(i, i - j, -1)) // reduce(mul, range(j, 0, -1)) if j > 0 else 1
 
res = combi(N + K - 1, K) if N > K else combi(N, K % N)
print(res % 1000000007)

C問題は解決指針がなんとなくわかった気がしますが，放置（簡単な問題ばかりとく屑）

*1: 通常コンビネーションなどを下付き文字が使えない環境下ではどう記述するのでしょうか？