yukicoder No.83 最大マッチング 解説

問題文

解説

まず、答えは最大$10^{10^4\times 5}$にもなる。よって、愚直に整数を一個一個試していく方法では到底間に合わない。
ここで考えよう。
まず、桁はできるだけ大きくしたい。なぜなら、桁が大きいほうがその分数字も大きくなるからである。
よって、できるだけマッチ棒を使わない数字を探す。今回の場合それは$1$となる。
$1$を作るのにマッチ棒は$2$使うので、$1111$...$11$と$1$が$\lfloor \frac{N}{2}\rfloor$続く整数が答え...とはいかない。
なぜなら、$N$が奇数だった時に$1$本余ってしまうからである。
これを有効活用する方法はマッチ棒を$3$本ちょうど使い、かつ$1$より大きい数字でないとならない。
この条件を満たすのが$7$。
よって、$N$が奇数なら$1$を一つ$7$に変えればよい。
もちろん、$117$などよりも$711$の方が大きいので、最初の1桁目を$7$にすればよい。
実行時間は$O(N)$なので、十分高速。

C++での解答例

#include <bits/stdc++.h>
using namespace std;

int main(){
  int N;cin>>N;
  if(N%2==1){
    cout<<7;
    N-=3;
  }
  while(N!=0){
    cout<<1;
    N-=2;
  }
  cout<<endl;
}