kmjp's blog

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

UnKoder #06 : Tetraphobia

UnKoder06に参加。
AでFirst Acceptedを取るなどなかなか順調でした。
https://www.hackerrank.com/contests/unkoder-06/challenges/tetraphobia

問題

正整数Nが与えられる。
N以下の整数のうち、(10進数で)どの桁にも4を含まない最大の整数を答えよ。

解法

上の桁から4を探し、見つけたらそれ以降を39999...で置き換えればよい。
整数型よりstringで入力を受けた方がラク。

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>s;
	FOR(i,s.size()) if(s[i]=='4') {
		s[i++]='3';
		for(;i<s.size();i++) s[i]='9';
	}
	cout<<s<<endl;
}

まとめ

一瞬桁DPかと思ったけど、ずっとシンプルだった。

広告を非表示にする