A video encoding apparatus determines whether to substitute all quantized coefficients in a target coefficient group by zero, on the assumption that the subsequent coefficient groups include one or more quantized coefficients that are not zero, the target coefficient group being sequentially selected from the lowest-frequency among coefficient groups included in a block serving as a unit in orthogonal transform, and determines, for each coefficient group sequentially from the lowest-frequency coefficient group, whether to update, to a first quantized-coefficient candidate that is not zero and corresponding to the highest frequency in the coefficient group on the assumption that all the quantized coefficients in the subsequent coefficient groups are zero, a second quantized-coefficient candidate, which is already obtained, based on comparison between the first candidate and the second candidate in terms of a comparison cost obtained by subtracting a coding error related to the subsequent coefficient groups from a cost.