AtCoder Beginner Contest 483 コンテストまとめ

コンテスト情報

AtCoder Beginner Contest 483 - AtCoderatcoder.jp favicon

コンテスト時間: 2026-11-07(土) 21:00 ~ 2026-11-07(土) 22:40 (100分)

A 問題

  • Difficulty: 16 / NoviSteps: 7Q / 解答時間: 0:48

問題概要

NN ページからなる資料をコピー用紙に両面印刷する。 NN ページを全て印刷するために必要なコピー用紙の枚数の最小値を求めよ。

解答方針

  • 求める必要な最小ページ数は ⌈N2⌉\left\lceil \dfrac{N}{2} \right\rceil で求められる。

ABC 483 A - Double-Sided Printingyuulisio.com favicon

B 問題

  • Difficulty: 75 / NoviSteps: 6Q / 解答時間: 9:50 + WA x1

問題概要

11 から NN までの番号が書かれた表裏の区別できるNN 枚のカードがあり、最初は上から 1,2,…,N1,2,\ldots,N の順ですべて表向きで積まれている。

高橋君はこの山に QQ 回の操作を行う。 ii 回目の操作の内容は以下の通り。

上から KiK_i 枚のカードをひとまとめにして裏返し、元の位置に戻す。これにより、上から KiK_i 枚のカードの順序が上下逆になり、それぞれのカードの表裏も反転する。

すべての操作を終えた後のカードの順序と表裏を求めよ。

解答方針

  • カードの番号を格納した配列を用意し、reverse関数を使って上からKiK_i枚のカードを裏返す操作を行う。
  • その際、裏返すカードの表裏を反転させるために、裏向きのカードの番号の符号を反転させる。

ABC 483 B - Flip Card Stackyuulisio.com favicon
  • 最初の実装方針が上手くいかず、1ペナしてしまった。

C 問題

  • Difficulty: 770 / NoviSteps: 1Q / 解答時間: 25:24

問題概要

ある村の村長候補者は NN 人いて、投票者は MM 人おり、ii 人目の投票者の投票先の第一希望は候補者 AiA_i、第二希望は候補者 BiB_i である。

候補者のうち一人のみが辞退した時、それぞれの投票者は以下のように投票する。

  • 第一希望の候補者が辞退していなければ、第一希望の候補者に投票する。
  • 第一希望の候補者が辞退していれば、第二希望の候補者に投票する。

辞退していない候補者のうち、得票数が最大の候補者が当選する。 また、そのような候補者が複数いる場合は、番号が最小の候補者が当選する。

k=1,2,…,Nk=1,2,\ldots,N それぞれについて、候補者 kk のみが辞退した場合に当選する候補者の番号を求めよ。

解答方針

  • cnti\mathrm{cnt}_i に候補者 ii の第一希望の得票数を格納し、候補者の番号 ii と共にsetに追加しておく。
    • ここで、比較関数は cnti\mathrm{cnt}_i の降順、それが同数なら ii の昇順に並べるものとする。このとき、setの先頭にある要素が当選する候補者である。
  • secondk\mathrm{second}_k に、候補者 kk を第一希望とする投票者の第二希望リストを格納しておくことで、候補者 kk が辞退した場合の得票数の変化を効率的に計算できる。
  • 各 kk に対して、次のことを行う。
    • 候補者 kk の要素 (cntk,k)(\mathrm{cnt}_k, k) をsetから削除する。
    • secondk\mathrm{second}_k の各要素 xx に対して、候補者 xx の要素 (cntx,x)(\mathrm{cnt}_x, x) をsetから削除し、cntx\mathrm{cnt}_x を 1 増やして再度setに追加する。
    • setの先頭にある要素の候補者番号を出力する。
    • secondk\mathrm{second}_k の各要素 xx に対して、候補者 xx の要素 (cntx,x)(\mathrm{cnt}_x, x) をsetから削除し、cntx\mathrm{cnt}_x を 1 減らして再度setに追加する。
    • 候補者 kk の要素 (cntk,k)(\mathrm{cnt}_k, k) をsetに追加する。

ABC 483 C - Second Choice Electionyuulisio.com favicon
  • C問題にしては難しい。

D 問題

  • Difficulty: 965 / NoviSteps: 1Q / 解答時間: 31:18

問題概要

数直線上にロボットがいて、はじめ、ロボットは座標 00 にある。

また、高橋君は長さ NN の整数列 A=(A1,A2,…,AN)A=(A_1,A_2,\ldots,A_N) を持っていて、次の操作を行う。

  • AA の要素を高々 11 つ選び、その符号を反転させる。
  • ロボットを起動する。ロボットは起動後、NN 回の行動を行う。ii 回目の行動では、現在の座標を xx として、座標 x+Aix+A_i へ直線的に移動する。

高橋君はロボットが一度以上通る整数座標の個数をなるべく多くしたい。 高橋君が最適に行動したときの、「ロボットが一度以上通る整数座標の個数」としてあり得る最大の値を求めよ。

解答方針

  • ロボットが移動中に到達する座標の最小値を LL、最大値を RR とすると、通過した整数座標の個数は R−L+1R - L + 1 で求められる。
    • したがって、各 AiA_i の符号を反転したときの最小座標・最大座標を効率的に求めればよい。
  • 配列 AA の累積和を SS として、ある AiA_i の符号を反転させたときを考えると、j≥ij \geq i のときの累積座標が、すべて −2Ai-2A_i だけ平行移動することがわかる。
  • これを用いて、前からの累積min pre_mi\mathrm{pre\_mi}、後ろからの累積min suf_mi\mathrm{suf\_mi}とすると、ii 番目の要素を反転させたときの最小座標 LiL_i は次の式で求められる。
    • Li=min⁡(pre_mii−1,suf_mii−2Ai)L_i=\min \left( \mathrm{pre\_mi}_{i-1}, \mathrm{suf\_mi}_i - 2A_i \right)
  • 最大座標 RiR_i についても、前後の累積max pre_mxi−1\mathrm{pre\_mx}_{i-1}, suf_mxi\mathrm{suf\_mx}_i を用いて同様に求めることができる。
  • あとは、i=1,2,…,Ni = 1,2,\ldots,N について、Ri−Li+1R_i - L_i + 1 の最大値を求めればよい。
  • なお、AiA_i の符号を反転させない場合は、L0=pre_miNL_0=\mathrm{pre\_mi}_N、R0=pre_mxNR_0=\mathrm{pre\_mx}_N で求めることができる。

ABC 483 D - Glitchy Robotyuulisio.com favicon

成績

Contest Result - AtCoderatcoder.jp favicon
  • 順位: 2094th / 10289
  • Performance: 1274
  • 1402 → 1390 (-12)