【競プロ】日本語を使おう 2

この記事は新歓ブログリレー2025 30日目の記事です。

はじめに

みなさま^[1]こんにちは、Nzt3です。
普段は競技プログラミングをやったり、競技プログラミングをやらなかったりしています。
みなさまも競技プログラミングをやりましょうね。

言語選択

この記事を読んでいるみなさまは既にAtCoderのアカウントを持っていてWelcome to AtCoderの正解を得ていると思います。

AtCoder Beginner Contest 400の参加登録もしていますよね。今年のICPC 国際大学対抗プログラミングコンテストに参加するためにチームメンバーを探しているか、既にチームを組んでいます。そろそろ海外のコンテストにも出てみようと、Codeforcesのアカウントも作りましたし、Universal Cupの参加を検討しているでしょう。

みなさまは競技プログラミングに C++17,C++20,C++23^[2] を使っていますが、AtCoderという国内最大のオンラインジャッジでは他にもたくさんのプログラミング言語を使うことができます。たまには他の言語も使ってみましょう。例えば、日本語プログラミング言語なら習得が簡単で使いやすいのではないでしょうか。

今回は「なでしこ」を使います。

「プロデル」を使った競技プログラミング入門については過去の記事【競プロ】日本語を使おうを参照してください。^[3]

ABCを解く

日本語プログラミング言語はどの程度の問題を解くことができるのでしょうか。日本の競技プログラマの多くが参加しているABC(AtCoder Beginner Contest)は一つの指標になります。

実際にABC300を解いてみましょう。^[4]

A - N-choice question

整数 $A, B$ が与えられるので、 $A + B$ の値を答えてください。
但し、この問題は $N$ 択問題であり、 $i$ 番の選択肢は $C_{i}$ です。
正解となる選択肢の番号を出力してください。

問題制約により正解の選択肢が一意に定まることが保証されています。

次の4ステップで解くことができそうです。

整数 $A, B$ を標準入力から受け取る。
$A + B$ を計算する。
選択肢 $C_{i}$ を受け取る。
$A + B$ と一致する番号を出力する。

入力形式を確認しましょう。

$N$ $A$ $B$
$C_{1}$ $C_{2}$ $\dots$ $C_{n}$

1行目に $N, A, B$ が空白区切りで与えられ、2行目に $C_{i}$ が $C_{1}$ から順に空白区切りで与えられることがわかります。

入力形式に合わせて入力を受け取るプログラムの実装も変わります。今回は 1行受け取って空白で分割することにします。

なでしこで書くと次のようになります。

入力を尋ねて、それを「 」で区切ってAに代入。
A@1+A@2をSに代入する。
入力を尋ねて、それを「 」で区切ってCに代入してください。
Cを反復
　もし、対象がSならば
　　対象キー+1を表示して。
　ここまで。
ここまで。

「入力を尋ねる」により標準入力から1行目を受け取り、「」(半角スペース)で区切って数値の配列としてA^[5]に代入しています。
配列Aの中身は[ $N$ , $A$ , $B$ ]であり、A@1+A@2で $A + B$ を計算してSに代入しています。

「入力を尋ねる」により2行目を受け取り、「」で区切って数値の配列としてCに代入します。
「反復」によって配列の値を初めから順に見て、対象が目的の値であれば「対象キー+1」を出力します。「反復」において「対象」は配列の要素、「対象キー」は配列の添字を表しています。

配列がどのような情報をどのような形態で保持しているかを知っていれば、あとは日本語として読めば動作が予想できますね。
語尾に多様性がありますが、なでしこの関数においては漢字で表記された「代入」「表示」などが重要であり、その部分さえあれば半分くらいの語尾は許されます。^[6]

B - Same Map in the RPG World

問題文が長いので概要だけお伝えします。

$H \times W$ の長方形のグリッドが2つあります。横巡回シフト、縦巡回シフトを行って一致させることはできますか？

横巡回シフトを $W$ 回行うことは $0$ 回行うことと同じです。横巡回シフトは $W$ 回未満行えばよいですね。同様に縦巡回シフトも $H$ 回未満でよいことがわかります。
ここから次の方針が生まれます。入力は省略します。

横、縦のシフトの回数 $H \times W$ 通りを全部試す。
1つでもシフト後に一致するものがあればYes、そうでなければNo

ここで、実際に巡回シフトしたグリッドを構築せずとも、一致判定のときに添字をずらすことで判定ができることがわかります。

これをなでしこで実装すると次のようになります。

なでしこでの実装

入力を尋ねて、それを「 」で区切ってHWに代入。
HにHW@0を代入。
WにHW@1を代入。
A=[]
iを0からH-1まで繰り返す
 入力を尋ねる。
  A@iにそれを代入。
ここまで。
B=[]
iを0からH-1まで繰り返す
 入力を尋ねる。
  B[i]にそれを代入。
ここまで。
関数　(sとtが)正しい条件とは
 xを0からH-1まで繰り返す
  yを0からW-1まで繰り返す
   もし、A[x][y]!=B[(s+x)%H][(t+y)%W]ならば
    falseを戻す。
   ここまで。
  ここまで。
 ここまで。
 trueを戻す。
ここまで。
答えに「No」を代入。
sを0からH-1まで繰り返す
 tを0からW-1まで繰り返す
  もし、sとtが正しい条件ならば
   答えに「Yes」を代入。
  ここまで。
 ここまで。
ここまで。
答えを表示する。

シフトの回数から一致判定する関数を定義して戻り値として真偽を返しています。引数は順番ではなく助詞で区別されます。
関数にまとめることで4重ループを陽に書かなくとも良くなり、読みやすくなります。

C - Cross

ここから先は問題概要を要約してお伝えすることはありません。見出しに該当する問題へのリンクを貼っていますので、リンク先の問題文をご自身でお読みください。

問題制約より、大きさを区別せずに全てのバツ印を数えるには次のような構造を数えれば良いことがわかります。

#.#
.#.
#.#

また、これを見つけることで「バツ印の中心」がわかるので大きさを調べることもできます。

これをなでしこで実装すると次のようになります。

実装

入力を尋ねて、それを「 」で区切ってHWに代入。
Hに(HW@0)*1を代入。
Wに(HW@1)*1を代入。
A=[]
iを0からH-1まで繰り返す
 入力を尋ねる。
 A[i]にそれを代入。
ここまで。
答え=[]
NにHを代入。
もしH>Wならば
 NにWを代入。
ここまで。
iを1からNまで繰り返す
 答え[i]は0。
ここまで。
xを1からH-2まで繰り返す
 yを1からW-2まで繰り返す
  もしA[x][y]="#"かつA[x-1][y-1]="#"かつA[x-1][y+1]="#"かつA[x+1][y-1]="#"かつA[x+1][y+1]="#"ならば
   カウンタに1を代入。
   sに0を代入。
   フラグに1を代入。
   ((x-カウンタ)が0以上)かつ((y-カウンタ)が0以上)の間
    もし、A[x-カウンタ][y-カウンタ]="#"ならば
     もしフラグが1ならば
      sにカウンタを代入。
     ここまで。
    違えば
     フラグに0を代入。
    ここまで。
    カウンタにカウンタ+1を代入。
   ここまで。
   答え[s]に答え[s]+1を代入。
  ここまで。
 ここまで。
ここまで。
iを1からNまで繰り返す
 答え[i]を表示。
ここまで。

D - AABCC

このレベルの問題になると競技プログラミングのメインコンテンツである「計算量改善」が効いてくるようになります。単純な全探索のコードが書けたとしても、実行に時間がかかればAC(正解)とは判定されません。

この問題では既に答えのわかっているサンプルに最大ケースがあります。その情報から、数えるべき数を1つずつ列挙できれば時間制限に間に合いそうなことが推測できます。
$a, b, c$ を小さい方から順に全探索しましょう。条件を満たさなくなるのは積が大きくなりすぎた時です。ある $(a, b)$ についてある $c$ が条件を満たさないならば、それ以上の任意の $c^{'}$ も条件を満たしません。

$c < 1 0^{6}$ がわかるのでエラトステネスの篩による素数列挙が有効です。

実装

篩=[]
iを1から1000000まで繰り返す
 篩[i]=true
ここまで。
篩[1]=false
iを1から1000000まで繰り返す
 もし篩[i]ならば
  j=i*i
  j<=1000000の間
   篩[j]=false
   j=j+i
  ここまで。
 ここまで。
ここまで。
入力を尋ねて、(それ)*1をNに代入。
素数=[]
t=0
Cを1から1000000まで繰り返す
 もし篩[C]なら
  素数[t]=C
  t=t+1
 ここまで。
ここまで。
i=0
答え=0
素数[i]*素数[i]<=Nの間
 j=0
 j<iかつ素数[j]*素数[j]*素数[i]*素数[i]<=Nの間
  k=j+1
  k<iかつ素数[j]*素数[j]*素数[i]*素数[i]*素数[k]<=Nの間
   答え=答え+1
   k=k+1
  ここまで。
  j=j+1
 ここまで。
 i=i+1
ここまで。
答えを表示。

E - Dice Product 3

有理数998(速度の制限上限られた精度で計算を行う競技プログラミングにおいて、有理数体の計算を998244353という素数を用いた有限体上の計算に置き換える問題)です。
素因数2,3,5を考えると小さめのDPが定義できます。

なでしこでは数値変数で64bit浮動小数点数の計算を行います。64bit浮動小数点数では998数え上げをするには整数の精度が足りません。なでしこには64bit整数はありませんが、中身のJavaScriptには多倍長整数があります。こちらを使いましょう。

なでしこ最強の命令「JS実行」(任意の文字列をJavaScriptとして解釈し実行する)を用いて「(nを)多倍長整数変換」という関数を定義します。

関数 (nを)多倍長整数変換とは
　"{n}n"をJS実行して、それを戻す。
ここまで。

また、「尋ねる」で入力を受け取った際に数値っぽいと判定されると自動で64bit浮動小数点数に変換されるので、この変換を行わない入力関数である「文字尋ねる」を使います。

実装

関数 (nを)多倍長整数変換とは
 "{n}n"をJS実行して、それを戻す。
ここまで。
MOD=998244353n
inv5=598946612n
入力を文字尋ねて、それを多倍長整数変換してNに代入。
cnt2=0
N%2nが0nと等しい間
 cnt2=cnt2+1
 N=N/2n
ここまで。
cnt3=0
N%3nが0nと等しい間
 cnt3=cnt3+1
 N=N/3n
ここまで。
cnt5=0
N%5nが0nと等しい間
 cnt5=cnt5+1
 N=N/5n
ここまで。
もしN=1nならば
 A=[]
 iを0からcnt2まで繰り返す
  A[i]=[]
  jを0からcnt3まで繰り返す
   A[i][j]=[]
   kを0からcnt5まで繰り返す
    A[i][j][k]=0n
   ここまで。
  ここまで。
 ここまで。
 A[cnt2][cnt3][cnt5]=1n
 iをcnt2から0まで繰り返す
  jをcnt3から0まで繰り返す
   kをcnt5から0まで繰り返す
    もしi+1<=cnt2ならば、A[i][j][k]=(A[i][j][k]+A[i+1][j][k]*inv5)%MOD。
    もしj+1<=cnt3ならば、A[i][j][k]=(A[i][j][k]+A[i][j+1][k]*inv5)%MOD。
    もしk+1<=cnt5ならば、A[i][j][k]=(A[i][j][k]+A[i][j][k+1]*inv5)%MOD。
    もしi+2<=cnt2ならば、A[i][j][k]=(A[i][j][k]+A[i+2][j][k]*inv5)%MOD。
    もしi+1<=cnt2かつj+1<=cnt3ならば、A[i][j][k]=(A[i][j][k]+A[i+1][j+1][k]*inv5)%MOD。
   ここまで。
  ここまで。
 ここまで。
 A[0][0][0]を表示。
違えば
 「0」を表示。
ここまで。

F - More Holidays

場合分けをして、全探索を行います。

実装

入力を尋ねて、それを「 」で区切ってNMKに代入。
N=NMK@0
M=NMK@1
K=NMK@2
入力を尋ねて、それをSに代入。
L=[]
R=[]
cntl=0
cntr=0
L[0]=0
R[0]=0
iを0からN-1まで繰り返す
    もしS[i]が"x"なら、cntl=cntl+1。
    L[cntl]=i+1
ここまで。
iをN-1から0まで繰り返す
    もしS[i]が"x"なら、cntr=cntr+1。
    R[cntr]=N-i
ここまで。
ans=0
もしKがcntl以下なら
    now=0
    r=0
    lを0からN-1まで繰り返す
      r<Nかつnow<=Kの間
        もしS[r]="x"なら、now=now+1。
        r=r+1
      ここまで。
      もしans< r-l-1なら、ans=r-l-1。
      もしS[l]="x"なら、now=now-1
      l=l+1
    ここまで。
    iを0からKまで繰り返す
      もしans<L[i]なら、ans=L[i]。
      もしans<R[i]なら、ans=R[i]。
    ここまで。
    もしMが2以上なら
      iをKから0まで繰り返す
          もし、ans<R[i]+L[K-i]なら、ans=R[i]+L[K-i]。
      ここまで。
    ここまで。
    ansを表示。
    終了。
ここまで。
iをcntrから0まで繰り返す
    (K-i)/cntlを切り捨て、それをxに代入。
    (K-i)をcntlで割った余りをyに代入。
    もしx>=M-1なら
        x=M-2
        y=cntl
    ここまで。
    もしans<x*N+R[i]+L[y]なら、ans=x*N+R[i]+L[y]。
ここまで。
ansを表示。

G - P-smooth number

素数を2グループに分けて半分全列挙を行います。
ある素数をどちらのグループに分けるかは毎回配列の大きさを調べて決定します。

素因数 $p$ を持つ値をあるグループ追加するときは、素因数 $p$ を持たないものを全て舐めて $p^{n}$ を掛けたものを追加します。
最後にソートして半分全列挙の集計を行いますが、最後に1回ソートするより素因数の追加時に毎回ソートした方が高速になりました。

なでしこには「配列ソート」「配列数値ソート」という文字列比較、浮動小数点数比較を用いて配列をソートする関数がありますが、どちらも多倍長整数を正しくソートできません。
多倍長整数をソートするには自身で三方比較関数を定義して「配列カスタムソート」を使う必要があります。

$N = 1 0^{14}, P = 97$ 程度であれば3800msで動きますが、問題の制約である $N = 1 0^{18}$ では実行時間制限に間に合わせることができませんでした。

実装

関数 (nを)多倍長整数変換とは
    "{n}n"をJS実行。
ここまで。
関数　多倍長整数比較(a,b)とは
  もし、a=bなら
    0を戻す。
  違えば、もし、a>bなら
    1を戻す。
  違えば
    -1を戻す。
  ここまで。
ここまで。

入力を文字尋ねて、それを「 」で区切ってNPに代入。
NP@0を多倍長整数変換して、それをNに代入。
NP@1を多倍長整数変換して、それをPに代入。
素数=[2n, 3n, 5n, 7n, 11n, 13n, 17n, 19n, 23n, 29n, 31n, 37n, 41n, 43n, 47n, 53n, 59n, 61n, 67n, 71n, 73n, 79n, 83n, 89n, 97n]
A=[1n]
B=[1n]

素数を反復
    対象をxに代入。
    もしxがP以下ならば
        もし(Aの要素数)が(Bの要素数)以下なら
            Aの要素数をnに代入する。
            iを0からn-1まで繰り返す
                A[i]をyに代入する。
                y*xがN以下の間
                    y*xをyに代入する。
                    yをAに追加する。
                ここまで。
            ここまで。
            Aを「多倍長整数比較」で配列カスタムソート。
        違えば
            Bの要素数をnに代入する。
            iを0からn-1まで繰り返す
                B[i]をyに代入する。
                y*xがN以下の間
                    y*xをyに代入する。
                    yをBに追加する。
                ここまで。
            ここまで。
            Bを「多倍長整数比較」で配列カスタムソート。
        ここまで。
    ここまで。
ここまで。
ans=0
l=Bの要素数-1
Aを反復
    l>=0かつ(B[l]*対象>N)の間
        l-1をlに代入。
    ここまで。
    ans=ans+l+1
ここまで。
ansを表示。

Ex - Fibonacci: Revisited

見なかったことにします。^[7]

結果

ABCDEFの6問が解けました。かなりいい感じですね。

数値が64bit浮動小数点数であることは競技プログラミングにおいて致命的な弱みになり得ますが、多倍長整数があるのでどうにかなりました。

おわりに

今回は「なでしこ」を使って競技プログラミングをしてみました。
C++には劣りますが、ある程度は戦えそうですね。
みなさまも競技プログラミングをやりましょうね。

おまけ AtCoder Library Practice Contest を解く

競技プログラミングにおいて頻出するデータ構造やアルゴリズムがあります。競技プログラミングでは使えるライブラリが限られており、公開されている実装を利用できない場合があります。そのようなものは自分で事前にコードを用意しておくことになります。

競技プログラミングにおいてはそのような「事前に用意したもの」のことも「ライブラリ」と呼びます。その「ライブラリ」の標準的な機能をチェックするための練習用コンテストがAtCoder Library Practice Contestです。

より高度なデータ構造のチェックにはLibrary Checkerが利用できます。

なでしこで頻出データ構造とアルゴリズムを実装してみましょう。

Disjoint Set Union

素集合を管理するデータ構造です。集合の合併と、ある2つの元が同じ集合に属しているかの判定を非常に高速に行うことができます。

シンプルな発想により驚異的な高速化が行われます。実装も簡潔で、天才的発想に感動することができます。
今回は時間計算量がクエリあたり $Θ (lo g (n))$ の簡易版を実装しました。

実装

入力を尋ねて、「 」で区切ってNQに代入します。
NQ@0をNに代入します。
NQ@1をQに代入します。
p=[]
iを0からN-1まで繰り返します
  p[i]に-1を代入します。
ここまで。


関数 (xの)リーダーとは
  もし、p[x]が-1と等しいなら
    (x)を戻します。
  違えば
    p[x]のリーダーをp[x]に代入します。
    p[x]を戻します。
  ここまで。
ここまで。

関数 (uとvが)同グループとは
  uのリーダーをuに代入します。
  vのリーダーをvに代入します。
  もしu=vなら
    trueを戻します。
  違えば
    falseを戻します。
  ここまで。
ここまで。

関数 (uとvを)マージとは
  もしuとvが同グループなら、falseを戻します。
  uのリーダーをuに代入します。
  vのリーダーをvに代入します。
  vをp[u]に代入します。
  trueを戻します。
ここまで。
Q回
  入力を尋ねて、それを「 」で区切ってqueryに代入します。
  query@0をTに代入します。
  query@1をUに代入します。
  query@2をVに代入します。
  もしT=0なら
    UとVをマージします。
  違えば
    もしUとVが同グループなら
      「1」を継続表示します。
      改行を継続表示します。
    違えば
      「0」を継続表示します。
      改行を継続表示します。
    ここまで。
  ここまで。
ここまで。
改行を表示します。

Fenwick Tree

数列の1点への加算と、数列の区間 $[0, r)$ の和の計算を高速に行うことができるデータ構造です。

実装において、2の補数表現を利用したbit演算のテクニックが用いられます。天才的です。^[8]

実装

入力を尋ねて、それを「 」で区切ってNQに代入します。
NQ@0をNに代入します。
NQ@1をQに代入します。
0をN+1だけ配列要素作成してBITに代入します。

関数　(pにvを)一点加算とは
    それは戻り値なし。
    p+1をpに代入します。
    pがN以下の間
        BIT[p]+vをBIT[p]に代入します。
        (pと(-p)のAND)+pをpに代入します。
    ここまで。
ここまで。

関数 (rの)区間和取得とは。
    resに0を代入します。
    rが1以上の間
        res+BIT[r]をresに代入します。
        r-(rと(-r)のAND)をrに代入します。
    ここまで。
    resを戻します。
ここまで。

入力を尋ねて、それを「 」で区切ってAに代入します。
iを0からN-1まで繰り返す
    iにA[i]を一点加算します。
ここまで。
ans=[]
Q回
    入力を尋ねて、それを「 」で区切ってqueryに代入します。
    もしquery@0=0なら
        query@1にquery@2を一点加算します。
    違えば
        query@1の区間和取得をlsumに代入します。
        query@2の区間和取得をrsumに代入します。
        rsum-lsumをansに配列追加します。
    ここまで。
ここまで。
ansを改行で配列結合して表示します。

Floor Sum

次の式を高速に計算します。

i = 0 \sum N - 1 ⌊ \frac{A \times i + B}{M} ⌋

式変形を頑張ると理解できます。

実装

関数　(nを)多倍長整数変換とは
    "{n}n"をJS実行。
ここまで。

関数 (nとmでaとbを)切り捨て足すとは
    0nをansに代入します。
    もしaがm以上なら
        ans+(n-1n)*n*(a/m)/2nをansに代入します。
        a%mをaに代入します。
    ここまで。
    もしbがm以上なら
        ans+n*(b/m)をansに代入します。
        b%mをbに代入します。
    ここまで。
    (a*n+b)/mをymaxに代入します。
    ymax*m-bをxmaxに代入します。
    もしymax=0nなら、ansを戻します。
    (ans+(n-(xmax+a-1n)/a)*ymax)をansに代入します。
    (ans+(ymaxとaでmと(a - xmax % a)%aを切り捨て足す)) をansに代入します。
    ansを戻します。
ここまで。
入力を尋ねて、それをTに代入します。
T回
    入力を尋ねて、それを「 」で区切ってqueryに代入します。
    query@0を多倍長整数変換して、Nに代入します。
    query@1を多倍長整数変換して、Mに代入します。
    query@2を多倍長整数変換して、Aに代入します。
    query@3を多倍長整数変換して、Bに代入します。
    NとMでAとBを切り捨て足し、それを表示してください。
ここまで。

Maxflow

グラフに水を流して問題を解きます。最大フロー最小カット定理などを利用した面白い使い方がたくさんあり、思ったより広い領域の問題に適用できます。

チェック用問題では二部マッチングを解いています。

実装

入力を尋ねて、「 」で区切ってNMに代入。
NM@0をNに代入。
NM@1をMに代入。
A=[]
iを0からN-1まで繰り返す
    入力を文字尋ねて、それをAに配列追加。
ここまで。
V=N*M+2
Gto=[]
Grev=[]
Gcap=[]
iを0からV-1まで繰り返す
  Gto[i]=[]
  Grev[i]=[]
  Gcap[i]=[]
ここまで。
pos0=[]
pos1=[]
E=0

関数　(uからvへ)辺追加とは
    pos0[E]=u
    eu=Gto[u]の要素数
    ev=Gto[v]の要素数
    pos1[E]=eu
    Gto[u][eu]=v
    Grev[u][eu]=ev
    Gcap[u][eu]=1
    Gto[v][ev]=u
    Grev[v][ev]=eu
    Gcap[v][ev]=0
    E=E+1
ここまで。

(-1)をVだけ配列要素作成してlevに代入。
関数　(sから)レベルBFSとは
    iを0からV-1まで繰り返す
        lev[i]=-1
    ここまで。
    bfs=[]
    lev[s]=0
    q=[]
    qにsを配列追加
    f=0
    fが(qの要素数)未満の間
        v=q[f]
        f=f+1
        iを0から(Gto[v]の要素数-1)まで繰り返す
            もし、(Gcap[v][i]>0)かつ(lev[Gto[v][i]]=-1)なら
                lev[Gto[v][i]]=lev[v]+1
                qにGto[v][i]を配列追加
            ここまで。
        ここまで。
    ここまで。
ここまで。

0をVだけ配列要素作成してiterに代入。
関数　(vからtへfで)増加パスDFSとは
    もしv=tなら、fを戻す。
    iter[v]が(Gto[v]の要素数)未満の間
        i=iter[v]
        to=Gto[v][i]
        cap=Gcap[v][i]
        rev=Grev[v][i]
        もしcap>0かつlev[v]<lev[to]なら
            f2=f
            もしf>capなら、f2=cap。
            d=(toからtへf2で増加パスDFS)
            もしd>0なら
                Gcap[v][i]=Gcap[v][i]-d
                Gcap[to][rev]=Gcap[to][rev]+d
                dを戻す。
            ここまで。
        ここまで。
        iter[v]=iter[v]+1
    ここまで。
    0を戻す。
ここまで。

関数 (sからtへ)最大流とは
    ret=0
    永遠の間
        sからレベルBFSする。
        もしlev[t]<0なら、retを戻す。
        0をVだけ配列要素作成してiterに代入。
        永遠の間
            sからtへVで増加パスDFSして、それをfに代入。
            もし、f<=0なら
              抜ける
            ここまで。
            ret=ret+f
        ここまで。
    ここまで。
ここまで。


source=N*M
sink=N*M+1
dx=[0,1,0,-1]
dy=[-1,0,1,0]

iを0からN-1まで繰り返す
    jを0からM-1まで繰り返す
        もし、i+jが偶数なら
            sourceから(i*M+j)へ辺追加。
            kを0から3まで繰り返す
                x2=i+dx[k]
                y2=j+dy[k]。
                もし、x2>=0かつx2<Nかつy2>=0かつy2<Mならば
                    もし、A[i][j]='.'かつA[x2][y2]='.'ならば
                        (i*M+j)から(x2*M+y2)へ辺追加。
                    ここまで。
                ここまで。
            ここまで。
        違えば
            (i*M+j)からsinkへ辺追加。
        ここまで。
    ここまで。
ここまで。

flow=sourceからsinkへ最大流。
flowを表示する。
ans=[]
iを0からN-1まで繰り返す
  ans[i]=[]
  jを0からM-1まで繰り返す
    ans[i][j]=A[i][j]
  ここまで。
ここまで。

iを0からE-1まで繰り返す
  v=pos0[i]
  d=pos1[i]
  もし Gcap[v][d]=0なら
    u=Gto[v][d]
    もし、v!=sourceかつu!=sinkなら
      x1=v/Mを切り捨て
      y1=v%M
      x2=u/Mを切り捨て
      y2=u%M
      もし、u-v=1ならば
        ans[x1][y1]='>'
        ans[x2][y2]='<'
      ここまで。
      もし、v-u=1ならば
        ans[x1][y1]='<'
        ans[x2][y2]='>'
      ここまで。
      もし、u-v=Mならば
        ans[x1][y1]='v'
        ans[x2][y2]='^'
      ここまで。
      もし、v-u=Mならば
        ans[x1][y1]='^'
        ans[x2][y2]='v'
      ここまで。
    ここまで。
  ここまで。
ここまで。

ansを反復
  対象を「」で配列結合して、それを表示。
ここまで。

Convolution

数列 $A = (A_{1}, \dots, A_{n}), B = (B_{1}, \dots, B_{m})$ について次のように定義される数列 $C$ を高速に計算します。

C_{k} = j + i = k \sum A_{i} \times B_{j}

この高速化には $1$ の原始 $2^{n}$ 乗根が関係しており、実数の計算にもかかわらず途中で複素数を経由します。
競技プログラミングにおいては $1$ の原始 $2^{23}$ 乗根が存在する有限体( $F_{998244353}$ )での出題が多いです。^[9]

私の実装が悪く、この問題のAC提出は用意できていません。TLE提出があるのでリンクを貼っておきます。

https://atcoder.jp/contests/practice2/submissions/64464724

おわりに 2

今回は「なでしこ」を使って競技プログラミングをしてみました。
C++には劣りますが、かなり戦えそうです。
みなさまも競技プログラミングをやりましょうね。

新歓ブログリレー2025はまだ続きます。

明日の担当は @Oxojo と @madara1687 です。お楽しみに。

「みなさま〜(天下無双)」ではありません。 ↩︎
言語として選択できたとしても、C++20,C++23の新機能が入っているとは限りませんが…… ↩︎
記事タイトルはこの記事を意識したものです。 Nintendo Switch 2 を意識したものではありません。 ↩︎
このブログの公開日(2025-04-05)にABC400が開催されますが、ABC300はその100回前ではありません。開催されていない回があります。 ↩︎
問題文中に使われている変数名と名前が被っていて紛らわしいですが、このような適当変数名も個人戦の競技プログラミングでは自己責任で許されます。チーム戦ではやめましょう。 ↩︎
お嬢様には少し難しいかもしれません。こちらのなでしこさんでお嬢様コーディングいたしますわ✨を参考に努力を続けましょう。 ↩︎
AtCoder Beginner Contestは時期によって問題数が異なります。300時点では8問ありました。 ↩︎
天才bit演算としては、他に部分集合の全列挙、大きさKの部分集合の全列挙などが挙げられます。蟻本p143を参照してください。 ↩︎
もちろん、複素数体での出題もあります。 ↩︎