競技プログラミングの鉄則演習問題集への解説¶

A01 - The First Problem¶

created: 2022-12-25 sun
ご意見・ご要望はissue・プルリク用のGitHubまで
GitHub上の対応ディレクトリ
公式ページ
要点: なし

入出力¶

let N = stdin.ReadLine() |> int
solve N |> stdout.WriteLine

解説¶

特にコメントはありません. 変数の範囲も問題ないため素直に次のように実装します.

let solve N = N*N
let N = stdin.ReadLine() |> int
solve N |> stdout.WriteLine

A02 - Linear Search¶

created: 2022-12-25 sun
ご意見・ご要望はissue・プルリク用のGitHubまで
GitHub上の対応ディレクトリ
公式ページ
要点: なし

入出力¶

let N,X = stdin.ReadLine().Split() |> Array.map int |> (fun x -> x.[0],x.[1])
let Ia = stdin.ReadLine().Split() |> Array.map int
solve N X Ia |> stdout.WriteLine

解説¶

線型探索だから先頭から調べます. 命令型言語ではforで見つかり次第breakします. F#でもほぼ同じように書けるもののbreakがありません. 見つかり次第breakするには再帰関数で処理を書くしかありません.

let solve N X Ia =
  let rec lsearch i =
    if i = N-1 then "No"
    elif Array.get Ia i = X then "Yes"
    else lsearch (i+1)
  lsearch 0

最後まで見つからなかったら"No"を返すのを忘れないようにしましょう. 上記のように停止条件を忘れないように条件分岐の一番最初に書いておくのがベターです.

A03 - Two Cards¶

created: 2022-12-26 mon
ご意見・ご要望はissue・プルリク用のGitHubまで
GitHub上の対応ディレクトリ
公式ページ
要点: なし

入出力¶

let N,K = stdin.ReadLine().Split() |> Array.map int |> (fun x -> x.[0],x.[1])
let Pa = stdin.ReadLine().Split() |> Array.map int
let Qa = stdin.ReadLine().Split() |> Array.map int
solve N K Pa Qa |> stdout.WriteLine

方針¶

素直に全探索します. 見つかり次第打ち切るタイプのforループ(再帰関数)を回しても構いません. ここではもう少しF#らしい書き方にします. 入力をフルスキャンするため必ずしも効率はよくありません.

解説1: 関数型らしい(?)実装¶

シンプルに関数をつなげる¶

何はともあれ全探索用の全ての和を取ります.

Pa
|> Array.map (fun p -> Qa |> Array.map (fun q -> p+q))

これで配列の配列(int array array)として和が取れます. これをArray.concatで整数の配列(int array)にします.

Pa
|> Array.map (fun p -> Qa |> Array.map (fun q -> p+q))
|> Array.concat

あとはKと一致する値があるかfilterで確認したあと, 配列が空であれば"No", 空でなければ"Yes"で処理すれば終わりです. まとめると次のように書けます.

Pa
|> Array.map (fun p -> Qa |> Array.map (fun q -> p+q))
|> Array.concat
|> Array.filter (fun x -> x=K)
|> Array.isEmpty
|> fun b -> if b then "No" else "Yes"

少し凝った関数を使う¶

collectとchooseを使って短くします. 特にmap >> concatがcollect, map >> filterがchooseです. 実際に挙動を確認するのが一番です. 上記リンクからREPLですぐに実行できるようなコードを準備しているため, 必要に応じてそちらから確認してください.

一応こちらにも入力値を用意します.

let N,K,Pa,Qa = 3,100,[|17;57;99|],[|10;36;53|]
let N,K,Pa,Qa = 5,53,[|10;20;30;40;50|],[|1;2;3;4;5|]

具体的に書き換えましょう. まずはmap >> concatをcollectにします.

Pa
|> Array.collect (fun p -> Qa |> Array.map (fun q -> p+q))
|> Array.filter (fun x -> x=K)
|> Array.isEmpty
|> fun b -> if b then "No" else "Yes"

次はmap >> filterをchooseにします. 慣れていないとすぐに自力で書き換えられないかもしれません. これを見て参考にしてください.

Pa
|> Array.collect (fun p -> Qa |> Array.choose (fun q ->
   let s = p+q
   if s=K then Some s else None))
|> Array.isEmpty
|> fun b -> if b then "No" else "Yes"

chooseの中の関数はfilterで残したい値は条件分岐でSome xを返し, 排除したい値はNoneを返すようにします.

見づらくなると思うならやる必要はありませんが, chooseに与えるラムダを一行にまとめたければlet inが使えます.

Pa
|> Array.collect (fun p -> Qa |> Array.choose (fun q -> let s = p+q in if s=K then Some s else None))
|> Array.isEmpty
|> fun b -> if b then "No" else "Yes"

解説2: 先に添字の配列を作る¶

内包表記の使い方を説明するだけです. 先の処理は本質的にmapを二つ使います. 必ずしも見やすくありません. どうせ全探索するなら命令型的に配列の添字を作っておく手法もあります.

次の内包表記で走査したい全添字の組のタプルからなる配列((int*int)[])が作れます.

1	`[\| for i in 0..N-1 do for j in 0..N-1 do (i,j) \|]`

これに対してArray.chooseでmap >> filterします.

  [| for i in 0..N-1 do for j in 0..N-1 do (i,j) |]
  |> Array.choose (fun (i,j) -> let s = Pa.[i]+Qa.[j] in if s=K then Some s else None)

あとは配列が空かどうかで判定します.

let solve N K (Pa:int[]) (Qa:int[]) =
  [| for i in 0..N-1 do for j in 0..N-1 do (i,j) |]
  |> Array.choose (fun (i,j) -> let s = Pa.[i]+Qa.[j] in if s=K then Some s else None)
  |> fun Xa -> if Array.isEmpty Xa then "No" else "Yes"

A04 - Binary Representation 1¶

created: 2022-12-26 mon
ご意見・ご要望はissue・プルリク用のGitHubまで
GitHub上の対応ディレクトリ
公式ページ
要点: 定型処理・零埋め(ゼロパディング)

入出力¶

let N = stdin.ReadLine() |> int
solve N |> stdout.WriteLine

方針¶

よく出てくる定型処理です. 暗記してもいいほどです. 自分用のライブラリを作って記録しておくといいでしょう. 私はArithmetics.fsxに記録しています.

解説1: 再帰¶

大枠¶

今回入力のNは1以上の自然数です. しかしN=0で問題(?)がある実装を紹介するため, 念のため場合分けを明確につけておきます.

結論からいうと再帰関数で0,1の数値からなるリストとして二進展開を作ります. 最初に書いたようにN=0の場合を別にして次のように書きます.

1	`let rec frec acc N = if N=0 then acc else "再帰処理"`

これで[1;1;0;1]のようなリスト(int list)ができます. ここから二進展開の文字列を作って文字列を零埋めします. 零埋めのよい方法がいまだによくわかっていないものの, C#の文字列系のメソッドを使えばいいでしょう. リストを文字列に変換して文字列を零埋めします.

  if N=0 then [0] else frec [] N |> List.map string |> String.concat "" |> fun s -> s.PadLeft(10,'0')

frec [] N以降は次のように処理しています.

List.map stringでint listをstring listに変換する.
System.String.concat ""でstring listを空文字列で連結する.
s.PadLeftで文字列に対して零埋めする.

再帰関数の構成を考える¶

いきなり二進展開で考えるとわかりにくいでしょう. K=10として十進数を十進展開し, 最後にK=2で置き換えると多少なりともわかりやすいはずです.

まず十進展開されたもとの数をNとします. 特にN = 123456789として, これの一番下からK進展開を考えます. 一番下の桁は9だから何とかしてNから9を切り出します. これをNをK = 10で割ったあまりとみなせばN%Kで9が取れます. 次にN/Kを考えると一番下の桁が削れてN1 = 12345678が得られます. これに対してさらにN1%Kを考えると8が得られます. これを再帰的に続けてNk = 0になるまで続ければ求める十進展開が得られます.

箇条書きでは次のように書けます.

K進展開したい数をNとする.
最低桁を取る.
- N%Kで最低桁が得られるからこの値を積む.
- 次の桁を得るためにN1 = N/Kを次のステップに回す.
二桁目を取る.
- N1%KでN1の最低桁, Nの二桁目が得られるからこの値を積む.
- 次の桁を得るためにN2 = N1/Kを次のステップに回す.
これをNk = 0までくり返す.

再帰関数を書く¶

結論だけ書きます.

1	`let rec frec acc N = if N=0 then acc else frec ((N%2)::acc) (N/2)`

解説2: `unfold`¶

F#入門コンテンツでループは再帰の構文糖衣とみなせると書きました. 特にループは配列から配列を作るか, 配列から値を作るか二通りあると書きました. 今回の処理は再帰を使って値から配列(リスト)を生成しています. 特定の場合にはこの逆の処理をしてくれる関数があり, それはunfoldです. 慣れないと難しいため無理に使う必要はありません. しかし関数型言語による処理では時々顔を見せる関数であるため, 念のため紹介します.

本質的には再帰と同じで, 関数についてはリファレンスを見てもらうとして簡潔に結果だけ示します.

let solve N =
  if N=0 then [|0|] else N |> Array.unfold (fun n -> if n=0 then None else Some (n%2,n/2))
  |> Array.rev
  |> Array.map string |> String.concat "" |> fun s -> s.PadLeft(10,'0')

unfoldを使う場合は再帰と違ってArray.revで順序を反転する必要があります.

A05 - Three Cards¶

created: 2022-12-26 mon
ご意見・ご要望はissue・プルリク用のGitHubまで
GitHub上の対応ディレクトリ
公式ページ
要点: アルゴリズム, ループを減らす

入出力¶

let N,K = stdin.ReadLine().Split() |> Array.map int |> (fun x -> x.[0],x.[1])
solve N K |> stdout.WriteLine

方針¶

これもよく出てくる処理です. 単純に三重ループを回すとTLEで時間内に終わりません. 時間内に終わらせる工夫が必要です.

解説¶

単純な処理の累積¶

三つ目のループをどうにかして回避する必要があります. 発想を転換して二つ目までのループで次のような和を作りましょう.

1	`[\| for i in 1..N do for j in 1..N do yield K-i-j \|]`

この配列はN^2個の要素を持っています. 仮に三つ目のループを回すとしてその変数をxとすると, x = K-i-jが所定の範囲である1からNにおさまっていれば条件をみたします. そこでfilterを使ってチェックしましょう.

  [| for i in 1..N do for j in 1..N do yield K-i-j |]
  |> Array.filter (fun x -> 1<=x && x<=N)

これで条件をみたす要素だけが抜き出せました. あとはこの配列の長さを取れば終わりです.

  [| for i in 1..N do for j in 1..N do yield K-i-j |]
  |> Array.filter (fun x -> 1<=x && x<=N)
  |> Array.length

`for`の中でフィルターする¶

他の言語と同じくforの内包表記の中で次のようにフィルターできます.

  [| for i in 1..N do for j in 1..N do let x=K-i-j in if 1<=x && x<=N then x |]

あとは同じく配列の長さを取れば終わりです.

let solve N K =
  [| for i in 1..N do for j in 1..N do let x=K-i-j in if 1<=x && x<=N then x |] |> Array.length

filterでN^2個の配列を再びチェックしなくていい分, こちらの方が二割ほど速いです.

A06 - How Many Guests?¶

created: 2022-12-27 tue
ご意見・ご要望はissue・プルリク用のGitHubまで
GitHub上の対応ディレクトリ
公式ページ
要点: アルゴリズム, ループを減らす

入出力¶

let N,Q = stdin.ReadLine().Split() |> Array.map int |> (fun x -> x.[0],x.[1])
let Aa = stdin.ReadLine().Split() |> Array.map int
let Ia = Array.init Q (fun _ -> stdin.ReadLine().Split() |> Array.map int |> fun x -> x.[0],x.[1])
solve N Q Aa Ia |> Array.iter stdout.WriteLine

方針¶

都度入場者数を計算していたら間に合わないため先に計算します. あとの処理を綺麗に書くための計算法もポイントです.

解説¶

`i`日目までの入場者数の計算¶

累積的な計算が必要です. もちろんAiから素直に計算すれば問題ありません. 例えば次のように書けます.

let Na0 = Array.create N 0
for i in 0..N-1 do
  if i=0 then Na0.[i] <- Aa.[i]
  else Na0.[i] <- Aa.[i]+Na0.[i-1]

forで破壊的に書きました. もう少し関数型らしく書きたければ次のようにfoldで書けます.

let Na0 =
  (Array.zeroCreate N, [|0..N-1|])
  ||> Array.fold (fun Na0 i ->
    if i=0 then Na0.[i] <- Aa.[i]; Na0
    else Na0.[i] <- Aa.[i]+Na0.[i-1]; Na0)

ここでNa0.[i] <- Aa.[i]などはunitを返すだけで配列を返さないため, 明示的に配列Na0を返す必要があります.

少し余談を挟みます. ちなみにfoldの内部で破壊的な計算をしています. しかしこれはfoldの外部には漏れません. 関数プログラミングでもパフォーマンスを求める場合は破壊的な処理を使いますし, 破壊的な操作はできる限り外に漏れないようにします. いまは必ずしもパフォーマンスを求める場面ではないものの, F#の配列に対する仕様によって破壊的な処理が便利な部分です. Haskellでは明示的にモナド環境下で作業するように強制されます.

さて, これを使って計算しても構いません. ただ後の処理がやや面倒になるため, 次のようにscanを使って累積和を計算しましょう.

1	`let Na = (0,Aa) \|\|> Array.scan (+)`

これと先のNa0が何が違うかは実行するとわかります. 問題で出てきた入力例で確認しましょう.

#r "nuget: FsUnit"
open FsUnit

let N,Q,Aa,Ia = 10,5,[|8;6;9;1;2;1;10;100;1000;10000|],[|(2,3);(1,4);(3,9);(6,8);(1,10)|]

(Array.zeroCreate N, [|0..N-1|])
||> Array.fold (fun Na0 i ->
  if i=0 then Na0.[i] <- Aa.[i]; Na0
  else Na0.[i] <- Aa.[i]+Na0.[i-1]; Na0)
|> should equal [|8; 14; 23; 24; 26; 27; 37; 137; 1137; 11137|]

(0,Aa) ||> Array.scan (+) |> should equal [|0; 8; 14; 23; 24; 26; 27; 37; 137; 1137; 11137|]

後者は先頭に0がはさまっています. (0,Aa)とした0です. 今回はこれを使いますが, もし先頭の0がほしくない場合は例えば次のように書くといいでしょう.

(Array.head Aa, Array.tail Aa) ||> Array.scan (+)
|> should equal [|8; 14; 23; 24; 26; 27; 37; 137; 1137; 11137|]

クエリへの対応¶

先のNaを使えば素直に計算できます.

  let Na = (0,Aa) ||> Array.scan (+)
  Ia |> Array.map (fun (l,r) -> Na.[r]-Na.[l-1])

ここでのポイントはNa.[r] - Na.[l-1]です. Liには1が来る場合もあり, この場合はRi日目までの全ての入場者を計算する必要があります. 特にNa.[l-1]の減算なしでNa.[r]だけを返す必要があって条件分岐が入ります. さらに条件分岐で適切な対処をしなければ, Na.[l-1]はl-1 = -1に対する配列外参照の実行時エラーまで起こり得ます. これが先のscanでの初項0の意義です.

コードがわかりにくくなるためわざわざ書きませんが, scanによる初項0がなくてももちろん正しいコードは書けます.

A07 - Event Attendance¶

created: 2022-12-27 tue
ご意見・ご要望はissue・プルリク用のGitHubまで
GitHub上の対応ディレクトリ
公式ページ
要点: アルゴリズム, ループを減らす

入出力¶

let D = stdin.ReadLine() |> int
let N = stdin.ReadLine() |> int
let Ia = Array.init N (fun _ -> stdin.ReadLine().Split() |> Array.map int |> fun x -> x.[0],x.[1])
solve D N Ia |> Array.iter stdout.WriteLine

方針¶

これも前問A06と同じくどうループを減らすかが問題です. このデータ数で速い言語なら無理を通せるものの, 明らかな無駄は省くべきでもあります. さらにA06と同じくあとの処理を綺麗に書くための前処理もポイントです. もちろん前回と違って今回は各日の出席者数の勘定で, 何日から何日までの指定ではない点も注意が必要です.

結論から言えば入力Iaを使ってi日に何人の出入りがあったかを勘定します.

liを使ってi日に人が一人入った.
riを使ってi+1日に人が一人抜けた.

こう考えて出欠を管理すれば計算できます. 上記のriの処理でi+1を考えているため, 配列で処理する場合は配列外参照の実行時エラーを起こさないように注意しましょう. 特にri = Dがありるため, 途中に出てくる配列の要素数はD+1にしなければいけません. 実際私は提出コードで一回REを出してしまいました. テストケースをきちんと考えれば防げた問題でもあり, テストケース生成の重要性もわかります.

解説¶

出欠管理¶

方針で書いた内容を素直に実装します.

  (Array.create (D+1) 0, Ia)
  ||> Array.fold (fun Xa (l,r) -> Xa.[l-1] <- Xa.[l-1]+1; Xa.[r] <- Xa.[r]-1; Xa)

Array.create (D+1)が重要です. 配列の添字は1-originではなく0-originである点にも注意しましょう.

累積和¶

これも単純にscanで十分です.

  (Array.create (D+1) 0, Ia)
  ||> Array.fold (fun Xa (l,r) -> Xa.[l-1] <- Xa.[l-1]+1; Xa.[r] <- Xa.[r]-1; Xa)
  |> Array.scan (+) 0

必要な要素の切り出し¶

今回も初項0が余計です. さらにD+1で配列を生成したため最終項も余計です. スライスで次のように書けばいいでしょう.

  (Array.create (D+1) 0, Ia)
  ||> Array.fold (fun Xa (l,r) -> Xa.[l-1] <- Xa.[l-1]+1; Xa.[r] <- Xa.[r]-1; Xa)
  |> Array.scan (+) 0
  |> fun Xa -> Xa.[1..(Xa.Length-2)]

ここも0-originの配列で後ろから二つめを取るにはXa.Length-2であって, Xa.Length-1ではない点に注意します.

A08 - Two Dimensional Sum¶

created: 2022-12-27 tue
ご意見・ご要望はissue・プルリク用のGitHubまで
GitHub上の対応ディレクトリ
公式ページ
要点: アルゴリズム, ループを減らす

入出力¶

let H,W = stdin.ReadLine().Split() |> Array.map int |> (fun x -> x.[0],x.[1])
let Xa = Array.init H (fun _ -> stdin.ReadLine().Split() |> Array.map int)
let Q = stdin.ReadLine() |> int
let Qa = Array.init Q (fun _ -> stdin.ReadLine().Split() |> Array.map int |> fun x -> x.[0],x.[1],x.[2],x.[3])
solve H W Xa Q Qa |> Array.iter stdout.WriteLine

方針¶

これもやはり典型的な処理です. 結論から言うと, 予め問題中の添字でいう(1,1)から(i,j)までの総和を取って配列Sa.[i,j]にためます. 求める部分長方形領域に対しては余計な要素を削って処理します. 部分総和を取る部分でO(HW), 質問のQa全体をチェックする部分でO(Q)だから十分間に合います.

方針さえはっきりすれば, 実装で問題になるのは最後の余計な要素を削る部分の添字の指定ミス程度でしょう.

解説¶

総和の配列を計算¶

計算の仕方はいろいろあります. C/C++/Rustのコードを参考にして, 例えば次のような破壊的な書き方をしてもいいでしょう.

  let Sa =
    let sa = Array2D.create (H+1) (W+1) 0
    let Ia = [| for i in 0..H-1 do for j in 0..W-1 do (i,j) |]
    Ia |> Array.iter (fun (i,j) -> sa.[i+1,j+1] <- sa.[i+1,j]+Xa.[i].[j])
    Ia |> Array.iter (fun (i,j) -> sa.[i+1,j+1] <- sa.[i+1,j+1]+sa.[i,j+1])
    sa

これはSaの計算の内部で破壊的なコードが閉じているため, 関数プログラミング的な実装とみなして構いません.

しかしここまでと同じくscanを使うともっとすっきり書けます. 「横を足してから縦に足す」素直な計算が次のように書けます.

  let Sa =
    Xa
    |> Array.map (Array.scan (+) 0)
    |> Array.scan (Array.map2 (+)) (Array.create (W+1) 0)

はじめのXa |> Array.map (Array.scan (+) 0)が横を足しているのはわかりやすいでしょうから, 問題は縦に足す部分です. 公式の入力例に即してどう計算しているか追いかけます. 説明の便宜のため次のように書き換えます.

  let Sa =
    let Ya = Xa |> Array.map (Array.scan (+) 0)
    Array.scan (Array.map2 (+)) (Array.create (W+1) 0) Ya

まずYaから書きます.

let Ya = Xa |> Array.map (Array.scan (+) 0)

val it: int array array =
  [|[|0; 2; 2; 2; 7; 8|];
    [|0; 1; 1; 4; 4; 4|];
    [|0; 0; 8; 13; 13; 15|];
    [|0; 4; 5; 5; 5; 11|];
    [|0; 0; 9; 11; 18; 18|]|]

これに対してscanの処理を追いかけましょう.

第一巡
- Array.create (W+1) 0 = [|0; 0; 0; 0; 0; 0|]
- 二重配列Yaの一行目: [|0; 2; 2; 2; 7; 8|]
- これらをmap2 (+)で足す: [|0; 2; 2; 2; 7; 8|]
- これをscanとして積み足しつつ次の入力に回す
第二巡
- scanの前段: [|0; 2; 2; 2; 7; 8|]
- 二重配列Yaの二行目: [|0; 1; 1; 4; 4; 4|]
- これをmap2 (+)で足す: [|0; 3; 3; 6; 11; 12|]
- これをscanとして積み足しつつ次の入力に回す
第三巡
- scanの前段: [|0; 3; 3; 6; 11; 12|]
- 二重配列Yaの三行目: [|0; 0; 8; 13; 13; 15|]
- これをmap2 (+)で足す: [|0; 3; 11; 19; 24; 27|]
- これをscanとして積み足しつつ次の入力に回す
第四巡
- scanの前段: [|0; 3; 11; 19; 24; 27|]
- 二重配列Yaの四行目: [|0; 4; 5; 5; 5; 11|]
- これをmap2 (+)で足す: [|0; 7; 16; 24; 29; 38|]
- これをscanとして積み足しつつ次の入力に回す
第五巡
- scanの前段: [|0; 7; 16; 24; 29; 38|]
- 二重配列Yaの五行目: [|0; 0; 9; 11; 18; 18|]
- これをmap2 (+)で足す: [|0; 7; 25; 35; 47; 56|]
- これをscanとして積み足しつつ終了

これで縦の和も計算できました.

求めるクエリに回答¶

先のscan二発で一行・一列が追加されています. それを前提にすると次のように書けます.

  Qa |> Array.map (fun (a,b,c,d) -> Sa.[c].[d] - Sa.[c].[b-1] - Sa.[a-1].[d] + Sa.[a-1].[b-1])

わかりにくければ図を描いて確認してください.

A09 - Winter in ALGO Kingdom¶

created: 2022-12-27 tue
ご意見・ご要望はissue・プルリク用のGitHubまで
GitHub上の対応ディレクトリ
公式ページ
要点: アルゴリズム, ループを減らす

入出力¶

let H,W,N = stdin.ReadLine().Split() |> Array.map int |> (fun x -> x.[0],x.[1],x.[2])
let Ia = Array.init N (fun _ -> stdin.ReadLine().Split() |> Array.map int |> fun x -> x.[0],x.[1],x.[2],x.[3])
solve H W N Ia |> Array.iter (Array.map string >> String.concat " " >> stdout.WriteLine)

方針¶

これもやはり典型的な処理です. 二次元になって積み方にもう一捻り必要になっただけでA07と本質的に同じです. 方針さえはっきりすれば, 実装で問題になるのは最後の余計な要素を削る部分の添字の指定ミス程度でしょう. 正しい実装を導くために入力例をうまく使うと便利です.

解説¶

方針にも書いたように基本はA07と本質的に同じです. ここでは大幅に解説を省略します.

結論から言えば入力の二次元配列への積み方は次の通りです.

  (Array.init (H+1) (fun _ -> Array.create (W+1) 0), Ia)
  ||> Array.fold (fun Xa (a,b,c,d) ->
    Xa.[a-1].[b-1] <- Xa.[a-1].[b-1]+1;
    Xa.[a-1].[d] <- Xa.[a-1].[d]-1;
    Xa.[c].[b-1] <- Xa.[c].[b-1]-1;
    Xa.[c].[d] <- Xa.[c].[d]+1;
    Xa)

(a-1,d)と(c,b-1)に-1を追加し, (c,d)に+1を追加するのがポイントです. (a-1,b-1)で立てた追加フラグを削除するのがこの二つの指定です. 余計なマイナスを削るためにさらに(c,d)に+1を追加します. これで必要な領域にだけ+1できます.

あとは横に足してから縦を足します.

  (Array.init (H+1) (fun _ -> Array.create (W+1) 0), Ia)
  ||> Array.fold (fun Xa (a,b,c,d) ->
    Xa.[a-1].[b-1] <- Xa.[a-1].[b-1]+1;
    Xa.[a-1].[d] <- Xa.[a-1].[d]-1;
    Xa.[c].[b-1] <- Xa.[c].[b-1]-1;
    Xa.[c].[d] <- Xa.[c].[d]+1;
    Xa)
  |> Array.map (Array.scan (+) 0)
  |> Array.scan (Array.map2 (+)) (Array.create (W+2) 0)

これはscan (+) 0の影響で二つついた余計な項を次のようなスライスで落とします.

  (Array.init (H+1) (fun _ -> Array.create (W+1) 0), Ia)
  ||> Array.fold (fun Xa (a,b,c,d) ->
    Xa.[a-1].[b-1] <- Xa.[a-1].[b-1]+1;
    Xa.[a-1].[d] <- Xa.[a-1].[d]-1;
    Xa.[c].[b-1] <- Xa.[c].[b-1]-1;
    Xa.[c].[d] <- Xa.[c].[d]+1;
    Xa)
  |> Array.map (Array.scan (+) 0)
  |> Array.scan (Array.map2 (+)) (Array.create (W+2) 0)
  |> fun Xa -> Xa.[1..H] |> Array.map (fun Ra -> Ra.[1..W])

A10 - Resort Hotel¶

created: 2022-12-28 wed
ご意見・ご要望はissue・プルリク用のGitHubまで
GitHub上の対応ディレクトリ
公式ページ
要点: アルゴリズム, ループを減らす

入出力¶

let N = stdin.ReadLine() |> int
let Aa = stdin.ReadLine().Split() |> Array.map int
let D = stdin.ReadLine() |> int
let Ia = Array.init D (fun _ -> stdin.ReadLine().Split() |> Array.map int |> fun x -> x.[0],x.[1])
solve N Aa D Ia |> Array.iter stdout.WriteLine

方針¶

ふつうに都度計算していたら凄まじい時間がかかるため, やはりクエリ処理の前の事前計算が重要です. 真ん中を抜いた配列に対する最大値の計算は, 左からLi-1番目までの最大値と, 右からRi+1番目からの最大値を計算すればよいです. 特に左からi番目までの最大値と, 右からi番目までの最大値を比較すればよいため, これを事前に計算しておけば十分です.

この方針さえ立てばあとは素直に実装できます.

解説¶

命令型的にforを回す計算でも対応できます. ここでは関数プログラミングらしい処理としてscan maxを使います.

  let La = Array.scan max 0 Aa
  let Ra = Array.scanBack max Aa 0

Laが左からの最大値でRaが右からの最大値です. それぞれ左右の端からはじめるにはscanとscanBackと使えばよいです. 気分としてscanBackはArray.rev >> Array.scanだと思ってください. 上のコードを見ればわかるように初期値0とAaの引数の順番が入れ替わっています. ちなみにscanとscanBackはHaskellだとfoldlとfoldrで, このlとrはleftとrightに由来します.

あとはクエリごとに最大値を比較すれば終わりです.

1	`Ia \|> Array.map (fun (l,r) -> max La.[l-1] Ra.[r])`

scanとscanBackは初期値0に由来する「余計な項」が入っている点に注意して添字を指定してください. 公式の入力例でLaとRaは次のようになっています.

Array.scan max 0 Aa |> should equal [|0; 1; 2; 5; 5; 5; 5; 5|]
Array.scanBack max Aa 0 |> should equal [|5; 5; 5; 5; 3; 3; 1; 0|]

scanでは最初に0が, scanBackでは最後に0が入ります. REPLを使うと簡単に確認できます.

A11 - Binary Search 1¶

created: 2022-12-28 wed
ご意見・ご要望はissue・プルリク用のGitHubまで
GitHub上の対応ディレクトリ
公式ページ
要点: アルゴリズム

入出力¶

let N,X = stdin.ReadLine().Split() |> Array.map int |> (fun x -> x.[0],x.[1])
let Ia = stdin.ReadLine().Split() |> Array.map int
solve N X Ia |> stdout.WriteLine

方針¶

入力の配列が既にソートされていて必ず要素が存在する前提の問題です. 入力のソートは絶対に必要で, 後者は探索処理として適切な仕様決めが必要です. ここでは二分探索の結果をOptionにし, Option.defaultValue (-1)でモノがない場合は決して存在しない配列の添字-1を返すとします.

解説¶

命令型の言語ではwhileで処理する方が多いように思います. ここでは再帰関数で処理します. 二分探索はアルゴリズムのどの本にも載っているため細かい解説は省略します.

  let rec binSrch l r =
    let m = (l+r)/2
    if r<l then None
    elif Ia.[m]=X then Some m
    elif X<Ia.[m] then binSrch l (m-1)
    else binSrch (m+1) r
  binSrch 0 (N-1) |> Option.map ((+) 1) |> Option.defaultValue (-1)

最後のOption.map ((+) 1)だけ注意します. これは適合する配列の値が得られたelif Ia.[m]=X then Some mでmを返した点に対する修正です. 0-originのF#の配列の添字としてはmである一方, 問題では1-originであるためその分を加算処理しています.

A12 - Printer¶

created: 2022-12-28 wed
ご意見・ご要望はissue・プルリク用のGitHubまで
GitHub上の対応ディレクトリ
公式ページ
要点: アルゴリズム

入出力¶

let N,K = stdin.ReadLine().Split() |> Array.map int64 |> (fun x -> x.[0],x.[1])
let Ia = stdin.ReadLine().Split() |> Array.map int64
solve N K Ia |> stdout.WriteLine

方針¶

二つ要点があります. 一つは何回目で実現できるかに関連して二分探索を思いつけるか, 二分探索を思いつけたとしてどう実装するかです.

ここでは後者の二分探索で何をどう調べるか考えましょう. あるm秒目で必要な枚数が印刷できたかどうかを調べる必要があります. 問題設定からその時間までに各i番目のプリンターはm/Ai枚印刷できています. あとはこの総和を取って必要枚数印刷できたか確認します.

解説¶

命令型の言語ではwhileで処理する方が多いように思います. ここでは再帰関数で処理します. 二分探索はアルゴリズムのどの本にも載っているため細かい解説は省略します.

  let rec bsearch l r =
    if r<=l then l
    else
      let m = (l+r)/2L
      let s = Ia |> Array.sumBy (fun a -> m/a)
      if K<=s then bsearch l m
      else bsearch (m+1L) r
  bsearch 1L (pown 10L 9)

問題の制約で答えは 10^9 を超えないとあるため, 最大値(最初のr)はr = 10^9に取ればよいでしょう. もちろん1 \leq Aiの仮定からも保証されます.

途中の印刷枚数確認はArray.sumByでmi/aの和を積めば計算できます.

A13 - Close Pairs¶

created: 2022-12-29 thu
ご意見・ご要望はissue・プルリク用のGitHubまで
GitHub上の対応ディレクトリ
公式ページ
要点: アルゴリズム

入出力¶

let N,K = stdin.ReadLine().Split() |> (fun x -> int x.[0], int64 x.[1])
let Ia = stdin.ReadLine().Split() |> Array.map int64
solve N K Ia |> stdout.WriteLine

方針¶

尺取り法で対処します. ここでは尺取り法は解説しません. オンライン上の資料としては例えばここを参考にしてください.

C/C++/Rustなど速い言語, またはHaskellでは問題ないようですが, AtCoder上のF#では単純な探索でTLEしてしまったため, 尺取り法の探索部分を二分探索で書く必要がありました.

2022/12時点の私の実装力だと, 二分探索ではまり倒したために力づくの部分があり, あまり綺麗なコードになっていません. いつかもう少しすっきり書き直したいです.

解説¶

前処理¶

今回は親切に入力の配列がソートされているため不要です. 実際には必要に応じてソートします.

大枠¶

配列の各添字に対して条件をみたす最長の添字を取ればよいため, 各iごとに最長の添字を探す関数をsearchとすれば実装の本体は次のように書けます.

  [|0..N-1|] |> Array.sumBy (fun i -> search i |> function | Some j -> (j-i |> int64) | None -> 0L)

条件をみたす添字がない可能性があるため, searchの返り値はOptionにしています. 特に条件をみたす添字jに対してj-iを積み, そうでない場合は0にして和を取れば求める組み合わせの総和が得られます. ここで一般に総和の値はintの範囲を越えるため, j-iにint64をかませる必要があります. 実際これでREをくらって原因がわからず30分ほどはまり倒しました.

何はともあれあとはsearchを実装すれば終わりです.

`search`の実装¶

二分探索に入る前にまずは条件をみたす添字があるかどうかを判定します. ここでは次のように書きます.

  let search i = if i=N-1 || K<Ia.[i+1]-Ia.[i] then None else Some "二分探索"

i=N-1の場合は後続がありません. また既にソートされているため, 配列の次の添字との差が既にKを越えていれば条件をみたす添字がありません. したがってこの二者の場合はNoneを返します. あとは探索値が必ず存在する仮定のもとで二分探索します.

二分探索の実装¶

まず真偽計算用の関数を用意します.

1	`let p i j = Ia.[j] - Ia.[i] <= K`

各iごとにこれを使って次のように計算します.

  let search i = if i=N-1 || K<Ia.[i+1]-Ia.[i] then None else Some (bsearch (p i) i (N-1))

あとはpまたはp iを使って次のように二分探索を書きます.

  let rec bsearch pi l r =
    if r<=l then if pi l then l else l-1
    else
      let m = (l+r)/2
      if pi m then bsearch pi (m+1) r
      else bsearch pi l m

いつも通り終了条件はr <= lです. 実際に実行してみるとわかるように, 上記の実装ではlが適切な添字の値になるとは限りません. そこでpi l = p i lを判定して条件をみたすならlを, みたさない場合は1を引いたl-1にします. (TODO: ここでスカっとlを返したい.)

次は再帰部分です. これもいつも通りまずは中点を取るべくm = (l+r)/2を取ります. もしIa.[m]が条件をみたすならm+1以上r以下から新たに添字を探します. もしIa.[m]が条件をみたさないからl以上m以下から新たに添字を探します.

A14 - Four Boxes¶

created: 2022-12-29 thu
ご意見・ご要望はissue・プルリク用のGitHubまで
GitHub上の対応ディレクトリ
公式ページ
要点: アルゴリズム

入出力¶

let N,K = stdin.ReadLine().Split() |> fun x -> int x.[0], int64 x.[1]
let Aa = stdin.ReadLine().Split() |> Array.map int64
let Ba = stdin.ReadLine().Split() |> Array.map int64
let Ca = stdin.ReadLine().Split() |> Array.map int64
let Da = stdin.ReadLine().Split() |> Array.map int64
solve N K Aa Ba Ca Da |> stdout.WriteLine

方針¶

全て正の数に対する状況下で和を考える前提ではK以下の要素だけ考えればよいと言ったところで, データによっては全探索が必要です. もちろん単純な計算ではO(N^4)で全く間に合いません. 今回はN <= 1000であるためO(N^3)程度まで計算量を減らす必要があります.

そこで豪快な手に打って出ます. まとめ方は何でも構いませんが, 例えばAaとBa, CaとDaに対してそれぞれ和を取ってまとめて要素がN^2個ある配列を二つ作り, 一方に対しては全探索, 他方に対しては二分探索して計算量を減らします. これで計算量がN^2 * log N程度にまで落とせます.

解説¶

前処理¶

ここでは和を取ってまとめた配列を二つ作ります. 二分探索用のソートが必要です. さらに全ての要素は1以上であるため, K以上の項を見る必要はないためそれもフィルターして外しましょう. つまり次のような量を用意します.

  let Xa = [| for a in Aa do for b in Ba do let s=a+b in if s<K then yield s |] |> Array.sort
  let L1 = Xa.Length-1
  let Ya = [| for c in Ca do for d in Da do let s=c+d in if s<K then yield s |] |> Array.sort
  let L2 = Ya.Length-1

どちらか一方だけソートすれば十分です. ここではデバッグしやすいように両方ソートしました. 処理速度を求めるなら余計な処理は削りましょう.

ここでフィルター処理の結果, どちらかの配列が空になっている可能性があります. 全ての要素が1以上である前提下で既に二項の和でKを越えている以上, どちらかの配列が空なら問答無用でNoです.

大枠¶

今回のデータの範囲では上記前処理の上で全探索してもそれほど時間は変わりませんでしたが, 命令型言語でのwhileループのように見つかり次第すぐに打ち切るべく今回は再帰で書きます. 処理のメインは次のように書けます.

  // Xaに関して全探索
  let rec frec i =
    if i=L1 then "No"
    elif "各`i`ごとに`Ya`に対して二分探索" then "Yes"
    else frec (i+1)
  if L1=(-1) || L2=(-1) then "No" else frec 0

あとは二分探索を書けば終わりです.

二分探索の実装¶

これはもはや定型処理です.

  let rec bsearch x l r =
    if r<=l then if Ya.[l]+x=K then true else false
    else let m = (l+r)/2 in if Ya.[m]+x<K then bsearch x (m+1) r else bsearch x l m

この二分探索に対して再帰関数を正確に書くと次のようになります.

  let rec frec i =
    if i=L1 then "No"
    elif bsearch Xa.[i] 0 L2 then "Yes"
    else frec (i+1)
  if L1=(-1) || L2=(-1) then "No" else frec 0

A15 - Compression¶

created: 2022-12-29 thu
ご意見・ご要望はissue・プルリク用のGitHubまで
GitHub上の対応ディレクトリ
公式ページ
要点: アルゴリズム

入出力¶

let N = stdin.ReadLine() |> int
let Aa = stdin.ReadLine().Split() |> Array.map int
solve N Aa |> Array.map string |> String.concat " " |> stdout.WriteLine

方針¶

問題を分解して考えます. まず対処すべきは指定通りの要素の順序づけです. 同じ値を持つ要素があるため一意化した上でソートすればよいでしょう. あとは値と順番に対する辞書を作り, 逆引きして要素に順番を割り当てれば求める結果が得られます.

解説¶

方針で書いた通りに関数を積めば終わりです.

  let flip (a,b) = (b,a)
  let Xm = Aa |> Array.distinct |> Array.sort |> Array.indexed |> Array.map flip |> Map
  Aa |> Array.map (fun x -> Xm.[x]+1)

A16 - Dungeon 2¶

created: 2022-12-30 fri
ご意見・ご要望はissue・プルリク用のGitHubまで
GitHub上の対応ディレクトリ
公式ページ
要点: アルゴリズム

入出力¶

let N = stdin.ReadLine() |> int
let Aa = stdin.ReadLine().Split() |> Array.map int
let Ba = stdin.ReadLine().Split() |> Array.map int
solve N Aa Ba |> stdout.WriteLine

方針¶

ごく単純な動的計画法で対応できます.

解説1: 配列と`fold`¶

問題の通りに前から決めます. はじめは一部屋しか進めないためAから選ぶしかなく, あとは一部屋前から来るか二部屋前から来るかのどちらかです. 最短時間を取るにはminを取ります. 最終的には次のように計算できます.

  (Array.create N 0, [|1..(N-1)|])
  ||> Array.fold (fun Xa i ->
    if i=1 then Xa.[i] <- Aa.[i-1] else Xa.[i] <- min (Aa.[i-1]+Xa.[i-1]) (Ba.[i-2]+Xa.[i-2])
    Xa)
  |> Array.last

解説2: メモ化再帰¶

注意¶

メモ化再帰による動的計画法も有名です. 試したところ, F#のデータ型であるMapで実装したTLEしてしまいました. 一方.NETのSystem.Collections.Generic.Dictionaryでは問題なく通ります. ここでは後者の実装を紹介します.

テンプレート¶

まずメモ化再帰用の次の関数はテンプレートとして自作ライブラリに収録するとよいでしょう. 以下で説明する実装自体も完全にパターンです.

  let memorec f =
    let memo = System.Collections.Generic.Dictionary<_,_>()
    let rec frec j =
      match memo.TryGetValue j with
        | exist, value when exist -> value
        | _ -> let value = f frec j in memo.Add(j, value); value
    frec

この関数の中のDictionaryとして定めたmemoが値をためるメモです. この関数の中で再帰関数のfrecを定義します. TryGetValueで既にメモ化された値があるか確認します. 既にあればメモ化された値を返し, そうでなければ別途引数として与えた関数fで値を計算し, メモに積んで計算された値を返します. 最後に返すのもこの再帰関数です.

関数`f`の処理¶

F#入門記事で再帰はループで書け, 典型的な処理はmapやfoldで書けると説明しました. ここではfoldに食わせた関数をほぼそのままfとして採用すればよいです. 具体的には次のように書きます.

  let f frec j =
    if j<=0 then 0 elif j=1 then Aa.[j-1]
    else min (Aa.[j-1] + frec (j-1)) (Ba.[j-2] + frec (j-2))
  memorec f (N-1)

解説を読みやすくするためfの呼び出し部分まで書いておきました. 上記のテンプレートのmemorecにfを食わせ, 配列+foldでArray.lastとして得た「最後の項」を得るためにN-1を食わせています. 解説1の配列とfoldは添字が小さい方から順に計算した一方, メモ化再帰ではほしいN-1を食わせて添字が小さい方の降りる形になっています.

さてfを解説します. これはif j <= 0を追加した分が解説1のfと変わっているだけで, fold版と本質的には同じ関数です. foldでは添字が小さい方から計算していたためXa.[j-1], Xa.[j-2]などとした分が, メモから呼び出すために再帰関数の呼び出しに変わっています. ちなみにこのfrecはmemorecの内部で作っているfrecが入る部分です. 慣れないとこのfrecがどこから来るのかと混乱するかもしれません. 上記コードのように関数の名前や引数名をきちんと揃えておくと参照しやすいでしょう.

まとめ¶

コードの全体は次のように書けます.

let solve N (Aa:int[]) (Ba:int[]) =
  let memorec f =
    let memo = System.Collections.Generic.Dictionary<_,_>()
    let rec frec j =
      match memo.TryGetValue j with
        | exist, value when exist -> value
        | _ -> let value = f frec j in memo.Add(j, value); value
    frec
  let f frec j =
    if j<=0 then 0 elif j=1 then Aa.[j-1]
    else min (Aa.[j-1] + frec (j-1)) (Ba.[j-2] + frec (j-2))
  memorec f (N-1)

let N = stdin.ReadLine() |> int
let Aa = stdin.ReadLine().Split() |> Array.map int
let Ba = stdin.ReadLine().Split() |> Array.map int
solve N Aa Ba |> stdout.WriteLine

A17 - Dungeon 2¶

created: 2022-12-30 fri
ご意見・ご要望はissue・プルリク用のGitHubまで
GitHub上の対応ディレクトリ
公式ページ
要点: アルゴリズム

入出力¶

let N = stdin.ReadLine() |> int
let Aa = stdin.ReadLine().Split() |> Array.map int
let Ba = stdin.ReadLine().Split() |> Array.map int
solve N Aa Ba |> stdout.WriteLine

方針¶

これもA16と同じ動的計画法を少し修正すれば対応できます. 経路を積む処理を明確にするため配列の初期化法が少し変えました.

解説1: 配列と`fold`¶

単純に時間の計算に加えて経路の情報を積むだけです. コードを読みやすくするために変数を用意しただけで, 本質的にはA16と変わりません.

具体的にはリターンする配列の各要素をタプルにして, fstは経路のリスト, sndは時間にしているだけです.

let solve N (Aa:int[]) (Ba:int[]) =
  Array.create N ([],0)
  |> fun Xa ->
    Xa.[0] <- ([1],0)
    Xa.[1] <- ([2;1],Aa.[0])
    Xa
  |> Array.fold (fun Xa i ->
    let (xs,x) = Xa.[i-1]
    let (ys,y) = Xa.[i-2]
    let (a,b) = (Aa.[i-1],Ba.[i-2])
    Xa.[i] <- if y+b<x+a then ((i+1)::ys, y+b) else ((i+1)::xs, x+a)
    Xa) [|2..N-1|]
  |> (Array.last >> fst >> List.rev)
  |> fun Xs -> sprintf "%d\n%s" (Xs.Length) (Xs |> List.map string |> String.concat " ")

let N = stdin.ReadLine() |> int
let Aa = stdin.ReadLine().Split() |> Array.map int
let Ba = stdin.ReadLine().Split() |> Array.map int
solve N Aa Ba |> stdout.WriteLine

解説2: メモ化再帰¶

これも関数の返り値が変わるだけです. このくらい簡単な内容ならどちらも完全に定型処理にはめるだけです. 読み書きしやすい方で対処してください.

let solve N (Aa:int[]) (Ba:int[]) =
  let memorec f =
    let memo = System.Collections.Generic.Dictionary<_,_>()
    let rec frec k =
      match memo.TryGetValue(k) with
        | true, v -> v
        | _ -> let v = f frec k in memo.Add(k,v); v
    frec
  let f frec k =
    if k=0 then ([1],0)
    elif k=1 then ([2;1],Aa.[0])
    else
      let (xs,x) = frec (k-1)
      let (ys,y) = frec (k-2)
      let (a,b) = (Aa.[k-1],Ba.[k-2])
      if y+b<x+a then ((k+1)::ys, y+b) else ((k+1)::xs, x+a)
  memorec f (N-1) |> (fst >> List.rev)
  |> fun Xs -> sprintf "%d\n%s" (Xs.Length) (Xs |> List.map string |> String.concat " ")

let N = stdin.ReadLine() |> int
let Aa = stdin.ReadLine().Split() |> Array.map int
let Ba = stdin.ReadLine().Split() |> Array.map int
solve N Aa Ba |> stdout.WriteLine

A18 - Subset Sum¶

created: 2022-12-30 fri
ご意見・ご要望はissue・プルリク用のGitHubまで
GitHub上の対応ディレクトリ
公式ページ
要点: アルゴリズム

入出力¶

let N,S = stdin.ReadLine().Split() |> Array.map int |> (fun x -> x.[0],x.[1])
let Aa = stdin.ReadLine().Split() |> Array.map int
solve N S Aa |> stdout.WriteLine

方針¶

完全一致する選び方の存在・非存在を調べるために全探索が必要です. 全ての組み合わせを取ると2^{60}個の組み合わせを確認する必要があるため, この組み合わせの量を減らしつつ, 効率よく適合する要素があるか確認する方法も考える必要があります.

ここでは要素の追加と検索に強いデータ構造として集合(Set)を採用します. 適合する組み合わせが見つかり次第早期リターンするべく, ここでは再帰で実装します.

解説¶

前処理¶

結論から言えば今回は不要ではあったものの, 考えなくてもよい要素ははじめから削りましょう. 再帰関数には入力の配列と値をためる集合を食わせるとすれば, 再帰関数に食わせる前に次のように書いておけばよいでしょう.

  Aa
  |> Array.filter (fun a -> a<=S)
  |> fun Aa ->
    if Array.isEmpty Aa then "No"
    else frec "配列" "集合"

和がSになるように考える以上, フィルターでS以下の要素だけ取ってきます. フィルターした結果, 配列から要素がなくなる可能性があるため, その条件分岐も入れておきます. あとは再帰に注力すれば十分です.

再帰関数¶

再帰的に処理するためはじめに終了条件を書く必要があります. 要素を追加した集合が求めるSを含んでいればそこでYesを返して終わりです. 一方で入力の配列を食い尽くしてなお適切な値がなければNoを返して終わりです. したがって大枠は次のように書けます.

  let rec frec Aa St =
    if Set.contains S St then "Yes"
    elif Array.isEmpty Aa then "No"
    else "再帰の本体"

else部分を考えましょう. まず入力から一つ食べて残りを再帰で回すと思えば次の大枠が作れます.

      let a = Array.head Aa
      "新たな集合を作る処理"
      |> frec (Array.tail Aa)

あとは新たな集合を作る処理を考えれば十分です. frec Aa StのStにはそこまでに貯めた組み合わせが入れる必要があります. いまは組み合わせそのものではなく総和だけが問題だから和を積めば十分です. 集合の積まれた各数値に対して新たなに配列から取り出したaを和で積めば十分です. ここで欲しい和の値であるSより大きい値を積む必要はないため, その振り分け処理が入ります. つまりループはStで回して処理もStに積む必要があります. ここでは次のようなfoldで対応できます.

      (St,St) ||> Set.fold (fun st0 v ->
        let st = if S<a then st0 else (Set.add a st0)
        if S<a+v then st else (Set.add (a+v) st))
      |> frec (Array.tail Aa)

念のため書いておくと(St,St)の左が値を積んでいく集合で, 右のStがループ用のStです. foldの内部で値を積みましょう. まず配列から取った値aがSより大きければ積む必要がないためその条件分岐があります. 次に配列から取った値と積んだ値の和a+vがSより小さければ値を積む中で適合した和を構成する可能性があるため, 集合に積みます. これがif S<a+vの行です. あとはこれで更新した集合を再帰関数に食わせて終わりです. 配列も一つ減らしておきましょう.

A19 - Knapsack 1¶

created: 2022-12-30 fri
ご意見・ご要望はissue・プルリク用のGitHubまで
GitHub上の対応ディレクトリ
公式ページ
要点: アルゴリズム

入出力¶

let N,W = stdin.ReadLine().Split() |> Array.map int |> (fun x -> x.[0],x.[1])
let Ia = Array.init N (fun _ -> stdin.ReadLine().Split() |> fun x -> int x.[0],int64 x.[1])
solve Ia |> stdout.WriteLine

方針¶

典型的な動的計画法で処理する問題です. 重さを添字wにした配列を作り, 各wごとに価値を格納します. あとはこれをひたすらに計算して書き換えます.

解説¶

配列を書き換え続ける処理は積み上げ系の処理で, 特にfoldで次のように実現できます.

  (Array.create (W+1) 0L, Ia)
  ||> Array.fold (動的計画法の処理)
  |> Array.last

書き換える配列でW+1個作るのは重さwをそのまま解釈できるようにするためです.

次にfold処理の関数を考えます. 動的計画法を考えるとき配列はよくdp(dynamic programming)で表します. ここでもその慣習を踏襲します. このdp[w]は重さwまで荷物を積んだときの価値を表します. ひたすらな書き換えは次のように実現します.

  ||> Array.fold (fun dp (w,v) ->
    [|0..W|] |> Array.map (fun w0 -> if w0<w then dp.[w0] else max (dp.[w0-w]+v) dp.[w0]))

foldの内部ではIaの各要素(w,v)で更新します. 入力のArray.create (W+1) 0Lと揃えた添字の配列を[|0..W|]とします. この配列の値を重さ(に関する添字)とみなしてw0とします. もしw0がwより小さい場合, dp[w0]に重さwのモノを積めないためdp.[w0]で素通りします. 逆にw<=w0のときは価値が大きい方で置き換えます.

A20 - LCS¶

created: 2022-12-31 sat
ご意見・ご要望はissue・プルリク用のGitHubまで
GitHub上の対応ディレクトリ
公式ページ

入出力¶

let S = stdin.ReadLine()
let T = stdin.ReadLine()
solve S T |> stdout.WriteLine

方針¶

やはりこれも動的計画法で対処する典型的な問題です. 改めて書くと最長の部分文字列を見つけるためには全探索が必要です. それをパターンにはめて書くのがポイントです. さらに文字を積んでいくだけの簡単な修正で最長の部分文字列も取れます. このコードも簡単に紹介します.

命令型的なふつうのコードでも十分に読みやすく書きやすいため, 今回もメインは命令型的なコードです. 関数プログラミングだとどう書くのかと思い, Haskellのコードを漁ってみたところ, 今の私の腕では読みやすくも書きやすくもない状態です. さらにいまの私の腕で対応できるHaskellコードの直移植だとF#ではパフォーマンスも出ません. 念のため関数型コードも紹介しますが, とりあえずは命令型的なコードが読み書きできれば十分です.

解説: 命令型コード¶

文字列長だけ¶

大枠¶

今回は二重配列で状態を管理します. 大枠は次のように書けます.

  let sLen = String.length S
  let tLen = String.length T
  (Array2D.create (sLen+1) (tLen+1) 0, [|0..sLen-1|])
  ||> Array.fold (fun dp i ->
    // 何かしらの処理
    dp)
  |> fun dp -> dp.[sLen,tLen]

あとはfoldの内部を考えます.

`fold`¶

それぞれの文字列の長さの配列を作り, ループの添字を(i,j)としましょう. もしS.[i] = T.[j]になったら値を足せばよいです. そうでない場合は値が大きい方を適切に取ります.

文章よりもコードを読んだ方が簡単です. 具体的には次のように書きます.

  (Array2D.create (sLen+1) (tLen+1) 0, [|0..sLen-1|])
  ||> Array.fold (fun dp i ->
    [|0..tLen-1|] |> Array.iter (fun j ->
      if S.[i]=T.[j] then dp.[i+1,j+1] <- dp.[i,j]+1
      else dp.[i+1,j+1] <- max dp.[i,j+1] dp.[i+1,j])
    dp)

どうせ破壊的に配列を変更するなら[|0..tLen-1|]も無理にArray.foldにせず, Array.iterで最後にdpを返す方が読み書きしやすいです.

まとめ¶

let solve S T =
  let sLen = String.length S
  let tLen = String.length T
  (Array2D.create (sLen+1) (tLen+1) 0, [|0..sLen-1|])
  ||> Array.fold (fun dp i ->
    [|0..tLen-1|] |> Array.iter (fun j ->
      if S.[i]=T.[j] then dp.[i+1,j+1] <- dp.[i,j]+1
      else dp.[i+1,j+1] <- max dp.[i,j+1] dp.[i+1,j])
    dp)
  |> fun dp -> dp.[sLen,tLen]

let S = stdin.ReadLine()
let T = stdin.ReadLine()
solve S T |> stdout.WriteLine

部分文字列も取る¶

積む値を整数と文字のリストのタプルに変えます. こちらは簡素に結論だけにしましょう.

let solveWithSubString S T =
  let sLen = String.length S
  let tLen = String.length T
  (Array2D.init (sLen+1) (tLen+1) (fun _ _ -> 0,([]:char list)), [|0..sLen-1|])
  ||> Array.fold (fun dp i ->
    [|0..tLen-1|] |> Array.iter (fun j ->
      if S.[i]=T.[j] then dp.[i+1,j+1] <- (1+fst dp.[i,j], (S.[i]::snd dp.[i,j]))
      else
        dp.[i+1,j+1] <-
          let (n1,s1),(n2,s2) = dp.[i,j+1],dp.[i+1,j]
          if n1<n2 then (n2,s2) else (n1,s1))
    dp)
  |> fun dp -> dp.[sLen,tLen]

解説: 関数型コード¶

元にしたのはこのHaskellコードです. 私が味を汲み尽くしきれていない可能性もあります. こちらは文字列長の計算だけ簡潔に紹介します.

関数型コードも本質的には命令型コードと同じです. しかし遅延型リストのHaskellではさっと書ける部分がF#ではもたつきます. Listの代わりにSeqを使えばさっと書ける部分はあるものの, 今度はSeq.consがないためにもたつく部分があります.

補助変数・関数¶

次の二つを準備します.

  let sLen = String.length S
  let init xs = if List.length xs <= 1 then [] else xs.[0..(List.length xs-2)]

後者はF#のList.initではなくHaskellのData.List.initの移植で, リストの最後の項を除いたリストを返します.

大枠¶

次のように書きます.

  let lcs Ss Ts =
    (Ts, List.replicate (1+sLen) 0)
    ||> List.foldBack (fun y dp -> "適切な処理")
  lcs (S |> Seq.toList) (T |> Seq.toList)

ここでメインがfoldBackになっているのがポイントです. 少なくとも以下で解説する書き方をfoldで書くと, 例えばS = "bceae"とT = "eddce"の組で適切な値2ではなく3が得られてしまいます. なぜかというとS.[1..2] = "ce"とT.[3..4] = "ce"のマッチが最長である一方, 処理の途中でS.[4] = 'e'とT.[4] = 'e'のマッチが入って3が返ってきてしまうからです. これを避けるために右からマッチさせるべくfoldBackを使っています.

左から順に処理する命令型的なコードと違い, 右から処理するfoldBackを使わなければいけないのも関数型コードの難しい点です.

`fold`¶

次のように書きます.

  let lcs Ss Ts =
    (Ts, List.replicate (1+sLen) 0)
    ||> List.foldBack (fun y dp ->
      let l3 = List.zip3 Ss (init dp) (List.tail dp)
      (l3, [0]) ||> List.foldBack (fun (x,n1,n2) dp ->
        if x=y then (1+n2)::dp else max n1 (List.head dp) :: dp))
    |> List.head

F#でもたつく部分がl3です. Haskellではinit dpは単にdpと書けます. あとは命令型コードと比較すると意図は明確でしょう. 命令型dp.[sLen,tLen]と違い, こちらはリストのconsで前に最長の値を積んでいるため, 最後に値を取得する部分はList.headで取ります. リスト処理で値が取りやすいようにしている点にも注意してください.

まとめ¶

let solve S T =
  let sLen = String.length S
  let init xs = if List.length xs <= 1 then [] else xs.[0..(List.length xs-2)]
  let lcs Ss Ts =
    (Ts, List.replicate (1+sLen) 0)
    ||> List.foldBack (fun y dp ->
      let l3 = List.zip3 Ss (init dp) (List.tail dp)
      (l3, [0]) ||> List.foldBack (fun (x,n1,n2) dp ->
        if x=y then (1+n2)::dp else max n1 (List.head dp) :: dp))
    |> List.head
  lcs (S |> Seq.toList) (T |> Seq.toList)

let S = stdin.ReadLine()
let T = stdin.ReadLine()
solve S T |> stdout.WriteLine

A21 - Block Game¶

created: 2022-12-31 sat
ご意見・ご要望はissue・プルリク用のGitHubまで
GitHub上の対応ディレクトリ
公式ページ

入出力¶

let N = stdin.ReadLine() |> int
let Ia = Array.init N (fun _ -> stdin.ReadLine().Split() |> Array.map int |> fun x -> x.[0],x.[1])
solve N Ia |> stdout.WriteLine

方針¶

いわゆる区間DPです. 改めてHaskellコードもあさったところ, やはり命令型の方が読み書きしやすいように思います.

解説¶

結果コード¶

let solve N (Ia:(int*int)[]) =
  let score l r (p,a) = if l<=p-1 && p-1<r then a else 0
  (Array2D.create (N+1) (N+1) 0, [|N..(-1)..0|])
  ||> Array.fold (fun dp r ->
    [|0..r-1|] |> Array.iter (fun l ->
      dp.[l+1,r] <- max dp.[l+1,r] (dp.[l,r] + score l r Ia.[l])
      dp.[l,r-1] <- max dp.[l,r-1] (dp.[l,r] + score l r Ia.[r-1]))
    dp)
  |> fun dp -> [|0..N|] |> Array.map (fun i -> dp.[i,i]) |> Array.max

let N = stdin.ReadLine() |> int
let Ia = Array.init N (fun _ -> stdin.ReadLine().Split() |> Array.map int |> fun x -> x.[0],x.[1])
solve N Ia |> stdout.WriteLine

Array.iterを使った部分をArray.foldに変えたり, もう少し関数型らしく書ける部分はあります. 今の私にとっての読み書きしやすさ, そして多少のパフォーマンスのバランスを取って現状はこのコードを採用しました.

ここで紹介したコードは最終的に対角成分に結果の候補が積まれるため, その中で最大値を取ります.

[[50; 50; 50; 10;  0]
 [ 0; 60; 60; 20; 20]
 [ 0;  0; 60; 50; 50]
 [ 0;  0;  0; 50; 50]
 [ 0;  0;  0;  0; 50]]

メモ¶

`score l r Ia.[l]`, `score l r Ia.[r-1]`¶

score 0 1 Ia[0]: 0
score 0 1 Ia[0]: 0
score 0 2 Ia[0]: 0
score 0 2 Ia[1]: 0
score 0 3 Ia[0]: 0
score 0 3 Ia[2]: 40
score 0 4 Ia[0]: 20
score 0 4 Ia[3]: 10
score 1 2 Ia[1]: 0
score 1 2 Ia[1]: 0
score 1 3 Ia[1]: 30
score 1 3 Ia[2]: 40
score 1 4 Ia[1]: 30
score 1 4 Ia[3]: 0
score 2 3 Ia[2]: 0
score 2 3 Ia[2]: 0
score 2 4 Ia[2]: 0
score 2 4 Ia[3]: 0
score 3 4 Ia[3]: 0
score 3 4 Ia[3]: 0

ありうる特典¶

取り除く順番	得点
`1,2,3,4`	20+30+0+0=50
`1,2,4,3`	20+30+0+0=50
`1,4,2,3`	20+40+0+0=60
`1,4,3,2`	20+30+0+0=50
`4,3,2,1`	10+40+0+0=50
`4,3,1,2`	10+40+0+0=50
`4,1,2,3`	10+30+0+0=40
`4,1,3,2`	10+40+0+0=50

A45 - Card Elimination¶

created: 2023-01-08 sun
ご意見・ご要望はissue・プルリク用のGitHubまで
GitHub上の対応ディレクトリ
公式ページ

入出力¶

let N,C = stdin.ReadLine().Split() |> fun x -> int x.[0], char x.[1]
let S = stdin.ReadLine()
solve N C S |> stdout.WriteLine

方針¶

文字列間の距離をL^1距離(マンハッタン距離)で表して考えます. 特に(R,B,W)で原点からの距離を表すと, 初期値は原点からの距離がNで, そこからL^1距離を1ずつ減らして目標地点((1,0,0),(0,1,0),(0,0,1)のどれか)に到達できるかが問題です.

次に文字の変換を距離で解釈します. 名前があると便利なため, それぞれの変換に番号をつけます.

WW - W: W-1移動
WR - R: W-1移動
WB - B: W-1移動
RR - B: R-2,B+1移動
BB - W: B-2,W+1移動
RB - W: 立方体の対角線上の移動でR-1, B-1, W+1

いずれにせよステップごとに原点からのL^1距離は1ずつ減ります. ある時点での距離Lを別に記録して状態を(R,B)だけで考えると, 注目すべきは上記の2,3,6です. 特に直線R-B=k上で考えると, 6は直線上の移動で, 2,3 はk ± 3移動します. 三つつのゴールはそれぞれk=1,-1,0にあたるため, 初期位置からkを±3して目標に位置合わせできるなら"Yes"です. 特に(R-B)%3の値がそれぞれ1,2,0のどれになるかが問題です.

解説¶

アルゴリズムさえ考えられれば, あとは各文字を数値に変換して計算すれば終わりです.

let solve N C S =
  let f c = match c with | 'W' -> 0 | 'R' -> 1 | _ -> 2
  S |> Seq.sumBy f |> fun n -> if n%3 = f C then "Yes" else "No"

let N,C = stdin.ReadLine().Split() |> fun x -> int x.[0], char x.[1]
let S = stdin.ReadLine()
solve N C S |> stdout.WriteLine

競技プログラミングの鉄則 演習問題集への解説¶

A01 - The First Problem¶

入出力¶

解説¶

A02 - Linear Search¶

入出力¶

解説¶

A03 - Two Cards¶

入出力¶

方針¶

解説1: 関数型らしい(?)実装¶

シンプルに関数をつなげる¶

少し凝った関数を使う¶

解説2: 先に添字の配列を作る¶

A04 - Binary Representation 1¶

入出力¶

方針¶

解説1: 再帰¶

大枠¶

再帰関数の構成を考える¶

再帰関数を書く¶

解説2: unfold¶

A05 - Three Cards¶

入出力¶

方針¶

解説¶

単純な処理の累積¶

forの中でフィルターする¶

A06 - How Many Guests?¶

入出力¶

方針¶

解説¶

i日目までの入場者数の計算¶

クエリへの対応¶

A07 - Event Attendance¶

入出力¶

方針¶

解説¶

出欠管理¶

累積和¶

必要な要素の切り出し¶

A08 - Two Dimensional Sum¶

入出力¶

方針¶

解説¶

総和の配列を計算¶

求めるクエリに回答¶

A09 - Winter in ALGO Kingdom¶

入出力¶

方針¶

解説¶

A10 - Resort Hotel¶

入出力¶

方針¶

解説¶

A11 - Binary Search 1¶

入出力¶

方針¶

解説¶

A12 - Printer¶

入出力¶

方針¶

解説¶

A13 - Close Pairs¶

入出力¶

方針¶

解説¶

前処理¶

大枠¶

searchの実装¶

二分探索の実装¶

A14 - Four Boxes¶

入出力¶

方針¶

解説¶

前処理¶

大枠¶

二分探索の実装¶

A15 - Compression¶

入出力¶

競技プログラミングの鉄則演習問題集への解説¶

解説2: `unfold`¶

`for`の中でフィルターする¶

`i`日目までの入場者数の計算¶

`search`の実装¶

解説1: 配列と`fold`¶

関数`f`の処理¶

解説1: 配列と`fold`¶

`fold`¶

`fold`¶

`score l r Ia.[l]`, `score l r Ia.[r-1]`¶