競技プログラミングで C/C++ コードを効率的に作成する

まず最初に知っておくべきことは、テンプレートマクロそしてベクトル次のフェーズに進む前に！

テンプレートは、特定の型に依存しない方法でコードを記述する汎用プログラミングの基礎です。
マクロは、名前が付けられたコードの一部です。名前が使用されるたびに、マクロの内容に置き換えられます。
ベクターは動的配列と同じで、要素が挿入または削除されると、そのストレージがコンテナーによって自動的に処理され、自動的にサイズを変更する機能を備えています。

したがって、これらの強力なツールを使用して、効果的な方法でコードを作成できます。
競技プログラミングで使用できる素晴らしいトリックのいくつかを以下に示します。

範囲ベースの for ループの使用 : これは C++11 の非常に優れた機能で、最初から最後まで反復処理を行う場合に最適と考えられます。このコードは、ranged for ループを使用して配列とベクトルを反復処理する方法を示しています。 CPP

    // C++ program to demonstrate range based for   // loops for accessing vector and array elements   #include       #include         using     namespace     std  ;   int     main  ()   {      // Create a vector object that      // contains 5 elements      vector   <  int  >     vec     =     {  0       1       2       3       4  };      // Type inference by reference using auto.      // Range based loops are preferred when no      // modification is needed in value      for     (  const     auto     &  value     :     vec  )      cout      < <     value      < <     ' '  ;      cout      < <     'n'  ;      // Basic 5 element integer array      int     array  []  =     {  1       2       3       4       5  };      for     (  const     auto     &  value  :     array  )      cout      < <     value      < <     ' '  ;      return     0  ;   }

出力：

0 1 2 3 4 1 2 3 4 5

イニシャライザリスト: この型は、C++ 初期化リストの値にアクセスするために使用されます。ここで、この型のオブジェクトは、中括弧で囲まれたカンマ区切りの要素のリストである初期化リスト宣言からコンパイラーによって自動的に構築されます。 CPP

    #include       template   <  typename     T  >   void     printList  (  std  ::  initializer_list   <  T  >     text  )   {      for     (  const     auto     &     value  :     text  )      std  ::  cout      < <     value      < <     ' '  ;   }   // Driver program   int     main  ()   {      // Initialization list      printList  (     {  'One'       'Two'       'Three'  }     );      return     0  ;   }

出力：

One Two Three

最大値または最小値の割り当て: これは、max() または min() 関数を記述する際の余分な労力を避けるのに役立ちます。 CPP

    #include       // Call by reference is used in x   template   <  typename     T       typename     U  >   static     inline     void     amin  (  T     &  x       U     y  )   {      if     (  y      <     x  )      x     =     y  ;   }   // call by reference is used in x   template   <  typename     T       typename     U  >   static     inline     void     amax  (  T     &  x       U     y  )   {      if     (  x      <     y  )      x     =     y  ;   }   // Driver program to find the Maximum and Minimum value   int     main  ()   {      int     max_val     =     0       min_val     =     1e5  ;      int     array  []  =     {  4       -5       6       -9       2       11  };      for     (  auto     const     &  val  :     array  )      // Same as max_val = max (max_val val)      // Same as min_val = min (min_valval)      amax  (  max_val       val  )     amin     (  min_val       val  );      std  ::  cout      < <     'Max value = '      < <     max_val      < <     '  n  '       < <     'Min value = '      < <     min_val  ;      return     0  ;   }

出力：

Max value = 11 Min value = -9

C/C++ での高速入出力: 競技プログラミングでは、貴重な時間を節約するために、入力/出力をできるだけ早く読み取る必要があります。 C

    #include          template   <  typename     T  >     void     scan  (  T     &  x  )   {      x     =     0  ;      bool     neg     =     0  ;      register     T     c     =     getchar  ();      if     (  c     ==     '-'  )      neg     =     1       c     =     getchar  ();      while     ((  c      <     48  )     ||     (  c     >     57  ))      c     =     getchar  ();      for     (     ;     c      <     48  ||  c     >     57     ;     c     =     getchar  ());      for     (     ;     c     >     47     &&     c      <     58  ;     c     =     getchar  ()     )      x  =     (  x      < <     3  )     +     (     x      < <     1     )     +     (     c     &     15     );      if     (  neg  )     x     *=     -1  ;   }   template   <  typename     T  >     void     print  (  T     n  )   {      bool     neg     =     0  ;      if     (  n      <     0  )      n     *=     -1       neg     =     1  ;      char     snum  [  65  ];      int     i     =     0  ;      do      {      snum  [  i  ++  ]     =     n     %     10     +     '0'  ;      n     /=     10  ;      }      while     (  n  );      --  i  ;      if     (  neg  )      putchar  (  '-'  );      while     (  i     >=     0  )      putchar  (  snum  [  i  --  ]);      putchar  (  'n'  );   }   // Driver Program   int     main  ()   {      int     value  ;      // Taking input      scan  (  value  );      // Printing output      print  (  value  );      return     0  ;   }

Input: 756 Output: 756

高速入出力について詳しく知りたい場合この記事を読む。

for ループとしてマクロを使用する : コードの可読性が低下するため、そのようなマクロを使用するのはおそらく良いことではありませんが、高速なコードを記述するためには、そのリスクを負うことができます。 CPP

    #include          using     namespace     std  ;   #define rep(in) for (i = 0; i  < n; ++i)   #define REP(ikn) for (i = k; i  <= n; ++i)   #define REPR(ikn) for (i = k; i >= n; --i)   // Driver program to test above Macros   int     main  ()   {      int     i  ;      int     array  []     =     {  4       5       6       9       22       11  };      int     size  =     sizeof  (  array  )  /  sizeof  (  array  [  0  ]);          // Default 0 index based loop      rep  (  i       size  )         cout      < <     array  [  i  ]      < <     ' '  ;      cout   < <  '  n  '  ;          // Starting index based loop      REP  (  i       1       size  -1  )         cout      < <     array  [  i  ]      < <     ' '  ;      cout   < <  '  n  '  ;          // Reverse for loop      REPR  (  i       size  -1    0  )         cout      < <     array  [  i  ]      < <     ' '  ;      return     0  ;   }

出力

4 5 6 9 22 11 5 6 9 22 11 11 22 9 6 5 4

このファイルには競技プログラミングに必要なヘッダーファイルがすべて含まれており、時間を大幅に節約できます。コンテナ: ベクターリストマップなどのさまざまなコンテナーを使用すると、事前定義された関数を使用できるようになり、コードのサイズが大幅に (多くの場合) 削減されます。高速な cin と cout: I/O に cin と cout を使用する場合は、main() の直後に次の行を追加するだけです。

std::ios_base::sync_with_stdio(false);

自動: auto を使用してデータ型を宣言すると、プログラミングコンテスト中に時間を大幅に節約できます。変数が自動として定義されると、コンパイラはコンパイル時にその型を決定します。ライブラリと事前定義関数: __gcd(AB) swap _builtin_popcount(R) _builtin_clz(R) などの組み込み関数を適用できる場合はどこでも使用します。で利用できるさまざまな機能を学習してみてくださいアルゴリズム C++ のライブラリ。プログラム内でほとんどの場合に役立ちます。

最終的には、これらの賢いトリックを使用することで、最小限の時間と単語数で簡単にコードを作成できるようになります。

クイズの作成