はい。
https://atcoder.jp/contests/abc007
A - 植木算
受け取ってそのまま-1。
B - 辞書式順序
a=input()
print("a" if a!="a" else -1)
一旦は変数に代入して比較してますけど、直接でもいいはずです。サンプルにある通りに"a"のときは"-1"で、ソレ以外は全部"a"で問題の条件を満たします。
xy=[(1,0),(-1,0),(0,1),(0,-1)]
r,c=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
d=set([(sy-1,sx-1)])
l=[]
for i in range(r):
l.append(list(input()))
l[sy-1][sx-1]=0
while len(d):
y,x=d.pop()
for i,j in xy:
i+=y
j+=x
if 0<i<r-1 and 0<j<c-1:
if l[i][j]=="." or (l[i][j] not in ["#","."] and l[y][x]+1<l[i][j]):
l[i][j]=l[y][x]+1
d.add((i,j))
print(l[gy-1][gx-1])
厳密にはこの方法だと幅優先ではない、set型からpopで取り出すのに順番がよくわからないので厳密には幅優先ではない気がします。 最小移動数を調べるのには影響しないので気にしないことにします。
座標や迷路を入力受け取りしてスタート座標を0手目として四方の移動先候補が"."か最小更新なら迷路のマスに移動数を記録して座標をset型にいれて保存。保存された座標が残っている間はpopで取り出して移動先〜を繰り返す。保存されている座標がなくなったら迷路のゴール座標にある値が最小移動数です。多分。
D - 禁止された数字
def sol(f):
s="0"+str(f)
l=[int(i) for i in s]
dp1=[0]*len(s)
dp2=[0]*len(s)
for i,j in enumerate(l):
if j not in [4,9]:
dp1[i]=1
else:
break
for i,j in enumerate(l):
if i==0: continue
x=y=0
if dp1[i]==1 or dp1[i-1]+dp1[i]==1:
y=l[i]-(l[i]>4)
dp2[i]=(dp2[i-1]*8)+(x*8)+y
return f-(dp1[-1]+dp2[-1]-1)
a,b=map(int,input().split())
print(sol(b)-sol(a-1))
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
long long x,dp[20][2];
long long cnt(char s[25],bool p) {
bool f=0;
x=0ll;
rep(i,20) {dp[i][0]=0; dp[i][1]=0;}
dp[0][0]=1ll;
long l=strlen(s);
for (long i=0;i<l;i++) {
x*=10;
int pt=s[i]-'0';
x+=pt;
if (pt==4 || pt==9) f=1;
rep(j,10) {
if (j==4 || j==9) continue;
if (pt==j) dp[i+1][0]+=dp[i][0];
if (pt>j) dp[i+1][1]+=dp[i][0];
if (i>0l) { dp[i+1][1]+=dp[i][1]; }
}
}
return x-dp[l][0]-dp[l][1]+1-(p==1 && f==1);
}
int main(){
int n,m;
char a[25],b[25];
scanf("%s %s",a,b);
long long ans=cnt(b,0)-cnt(a,1);
printf("%lld\n",ans);
return 0;
}
昔々にPythonで解いた場合：
桁DPわかりません。区間A,Bの個数をそのまま調べるのはかなり大変そうなので、(Bまでの個数) - (A-1までの個数) で区間A,Bを調べることを目指します。
あと1からXまでの間で4,9いずれかを一度でも使う個数を調べるのはうまくいかなかったので、一度も使わないものの個数を調べることにしました。調べた後でXから引けば同じことですね。個数が求まるので区間A,Bも求まります。
期間をあけてからC++で挑戦し直し：
かなり苦戦しました。
4,9を一度も使わないものを数えてA,Bから引いたりしてなんとか。とりあえずはAC出ているとは言えどもDPテーブルの準備とか更新とかこれでいいのかどうかなどよく分かっておらず。
