概要
keymoon さんと F# 縛りで ABC 112 速解きバトルをしました。
コンテストの様子
A - Programming Education (lap time: 6:11)
問題概要
N = 1 ならば Hello, World を、N = 2 ならば A + B の結果を計算しましょう。
解法
天才なのでひらめきました。これは標準入力と if と たし算と標準出力の問題です。 早速 「AtCoder 標準入出力」 で検索です。
えへへ、天才ですね。
……って、
ないじゃないですか！！
諦めて今度は 「F# AtCoder」でググるをしました。私は天才なので知っているんですね。 どの言語にも必ず「解いてみたシリーズ」があります。
ありましたね。kuuso さん、熱烈感謝です🙏
標準入出力は、コピペです。 10 問あるサンプルコードから、if で検索です。 この問題は無事 AC をすることができました。
たった 6 分で F# を完全理解です。天才ですね。（ところで keymoon さんは 2 分です）
open System
let n = stdin.ReadLine() |> int
if n = 1 then
"Hello World" |> printfn "%s"
else
let a = stdin.ReadLine() |> int
let b = stdin.ReadLine() |> int
a + b |> printfn "%d"
B - Time Limit Exceeded (laptime: 20:40)
問題概要
T より時間の短いものの中で、最もコストの小さいものを探しましょう。 なければ "TLE" です
解法
だんだんとコツがわかってきました。
ループは関数型言語の腕の見せ所なのですが、そんなことは知りません。for ループをして、コストの小さかったものの勝ちです。時間の長すぎるものは continue ですね。照れますね。プログラミングが上手です。
なにやら不穏を感じますね。シンタックスハイライトが壊れているのでしょうか。
まあよいです。私のスピードについてこられなかったのでしょう。えい！ dotnet run です。
The identifier 'continue' is reserved for future use by F#
あら？
ないじゃないですか！！！
私としたことが、keyword を間違えているのですね。仕方がないですね。他文化理解は重要です。「F# continue」でググるをしましょう！！ でん！
＿人人人人人人人＿
＞ 継続モナド ＜
￣YYYYYYY^￣
ん〜〜〜〜、 はい。見なかったことにして、条件に not をつけて if に包みしょう。神回避ですね。（はい！？！？）
open System
let NT = stdin.ReadLine().Split(' ');
let N = NT.[0] |> int;
let T = NT.[1] |> int;
let mutable min = 1000000;
for i in 0..N-1 do
let ct = stdin.ReadLine().Split(' ');
let c = ct.[0] |> int;
let t = ct.[1] |> int;
if t <= T then
min <- Math.Min(min, c)
if min = 1000000 then
"TLE" |> printfn "%s"
else
min |> printfn "%d"
地味に int.MaxValue の使い方がわからなくて 1000000 をしているところがポイントです。
C - Pyramid (laptime: 45:55)
問題概要
101 × 101 のグリッドがあって、どこかにピラミッドの頂点があります。 そこからマンハッタン距離で高さが下がっていくのですが、地中にめり込むことはありません。 いくつかの地点の高さを教えていただけるので、頂点の位置と高さを当てましょう。
ポエム
ところでこの問題は、私が競技プログラミングを始めたてのときに、お友達から紹介をしていただいて、なかなか解けなかった思い出の問題です。 当時の私には全探索をするという発想がなく（といいますか、定数時間で解けそうなので遅く解くいう発想がなく）、最小限の情報から復元をしようと頑張っていました。 青春ですね。
でも今なら解けます。余裕です。見ていてください🔥
解法
全探索をするのですが、なによりまずタプルの配列を作らなければいけません。
let N = stdin.ReadLine() |> int
let data : (int * int * int) [] = Array.zeroCreate N
for i in 0..N-1 do
let xyh = stdin.ReadLine().Split() |> Array.map int
data.[i] <- (xyh.[0],xyh.[1],xyh.[2])
どんなものですか！ F# では型の直積が operator * で表されるのですね。美しいです。
さて全探索です。i, j を 0 から 100 までイテレートです。高さはどこか 1 点を見れば決まります。 （嘘で、高さが 0 でない頂点を見ないと行けないのですが、はじめめり込んではいけないを読み落としていて WA を頂いてしまいました。）
これが出来たら更に内側でループをして、間違いがないかをチェックです。 ここは古代より伝わる古のメソドロジー、† ng フラグ † で対処です。 え、関数型プログラミングですか？ 美味しそうなお名前です。
let mutable ng = false;
for k in 0..N-1 do
let (i0, j0, h0) = data.[k]
let mutable di = i - i0
let mutable dj = j - j0
if di < 0 then
di <- -di
if dj < 0 then
dj <- -dj
if Math.Max(0, h - di - dj) <> h0 then
ng <- true
さて、これで答えが見つかったらどうすればよいのでしょう。break でループを脱出ですね。
はーい、知っていますよ。どうせないんですよね。でん！ エラーなやつ〜〜（パクリ）
The identifier 'break' is reserved for future use by F#
真に F# を使いこなす方々には必要のないものなのでしょう。
ここで制約をチェックです。
「ピラミッドの中心座標と高さをちょうど 1 つに特定することができる」
はい勝ちです私の勝ちです。break をせずに処理を続行です。どうせ 1 回しかあたりません。（はい！？！？）
完成品のコードは、せっかくですから keymoon さんのコードと並べますね。 さあ、どちらがながたかなでどちらが keymoon さんだか、あなたはわかりますか？ 私はわかります。（突然のマウンティング）
A
B
D - Partition (laptime: 61:24)
さて、ボス問です。 ここで順位表をチェックすると、keymoon さんは C を飛ばして D から解いているようでした。 ということはおそらくこちらは軽実装です。言語に慣れるてから C を解く作戦ですね。さすがです。
問題概要
N, M がありますから、M / N 以下の M の約数の最大値を計算しましょう
解法
思ったより難しいですね。まずは M 以下の自然数の全探索を √M までで止める必要があります。
お待ちかね、† ググりパワー発動 † です！！ C# 同様 Math.Sqrt が使えます。使いましょう。
あとはキャストを書きましょう。
正直書き方がよくわかっていないのですが、|> int でできそうな雰囲気を感じるので書きます。忖度の達人ですね。
let sqrt = Math.Sqrt(m |> float) |> int
あとはここまで全探索をして、条件を満たしているかをチェックし、Max で更新です。
for d in [1..sqrt] do
if (m % d = 0L) && (d * n <= m) then
ans <- Math.Max(ans, d)
if (m % d = 0L) && ((m / d) * n <= m) then
ans <- Math.Max(ans, (m / d))
演算子の優先順位は言語によって違う可能性があります。安定を取ってたよいムーブです（？）
おっと、(m / d) * n はオーバーフローをしてしまいますね。（これは気が付かずに 1 WA をした人です。）
C++ の long long（的なもの）は C# では long です。嬉しいですね。えい！
The value or constructor 'long' is not defined.
ないじゃないですか！！！
ここでググりアゲインです。もう慣れたものです。スムーズな手付きで検索をしていきます。
int64 さんといういうのですね。うーん long のほうが好きです。
open System
let nm = stdin.ReadLine().Split() |> Array.map int64
let n = nm.[0]
let m = nm.[1]
let mutable ans = 1L
let sqrt = Math.Sqrt(m |> float) |> int64
for d in [1L..sqrt] do
if (m % d = 0L) && (d * n <= m) then
ans <- Math.Max(ans, d)
if (m % d = 0L) && ((m / d) * n <= m) then
ans <- Math.Max(ans, (m / d))
printfn "%d" ans
というわけで、無事提出が出来ました。
完走した感想
難しいじゃないですか！！！
自分のコードに微塵も関数型プログラミング要素がなくて笑っています。F# の神様に踏み潰されてしまいあそうですね。
なによりびっくりしたのが、keymoon さんがかなりそれっぽいコードを書いているところです。 ものすごい適応力です。F# で C++ をしているどこかの誰かさんとは大違いですね。聞こえていますか、誰かさん？
F# らしい書き方をまなぶよりは C++-style でゴリおしをするほうが速いという読みだったのですが、keymoon さんの提出を見てしまうと、きちんとお勉強をする時間を 15 分でも取ったほうが結果てきに速かったという説はいなめません。
正直今回は、「この 1 回を走り切る」ことにフォーカスをしていて、調べるのも最低限になってしまったのですが、 今度はもう少しちゃんと書けるようになってから「競プロ with F#」をしてみたいものです。
そして悲しいお知らせなのですが、Codeforces の提出言語には F# がありません。悲しいですね。
