072 C - 4/N¶
- created: 2022-12-02 fri
- ご意見・ご要望はissue・プルリク用のGitHubまで
- GitHub上の対応ディレクトリ
- 公式ページ, TENKA1 2017 C - 4/N
数学から決まる議論¶
特に小さいN
に対して大学受験でもよくある問題です. 数学の話でもあって数学系学習と並行した議論を目指す私のスタンスからは大事なため, 公式解説の議論を簡単にくり返します.
対称性によってどれから議論してもよいためまずはh
から考えましょう. 必要条件からの絞り込みでh
を小さい方から増やして具体的に確認し続ければよく, まさにアルゴリズミックに次のように議論を進めます.
h=1
として4/N - 1
を計算する.- これは
1/n+1/k
に等しいはずだから再びn=1
として左辺に移行する.4/N-1-1
と1/k
が等しくなる整数k
が取れるか確認する.
- 取れなければ
n=2
で確認する.4/N-1/2-1
と1/k
が等しくなる整数k
が取れるか確認する.
- 取れなければ
n=3
で確認する.4/N-1/2-1
と1/k
が等しくなる整数k
が取れるか確認する.
- ...
- 順次
n=h
まで確認する.
- これは
h=2
として4/N-1/2
を計算する.- ...
と続けます. 原理的にこれしか議論しようはないものの, 時間内に解けるかが懸念点です. そして問題文でh,n,w≤3500
が保証されているため, この範囲内でけりが着くはずと思って全探索します. もちろん3つ全てでループするとTLE
するため, 2つ決まれば3つ目は自動的に決まる性質を使って二重ループで片付けます.
解答1: 素直なループ¶
1つ求めればよいため, 1つ決まったら計算を停止させます. 命令型的なfor
文とbreak
を使えればよいのですが, 残念ながらF#
にはbreak
がないようで, 使うならwhile
とフラグ管理です.
ただし命令型として素直なfor
とbreak
がないだけです. Haskellの遅延リスト・遅延評価と同じく, 遅延評価してくれるseq
を使いましょう. 次のような適切な書き方をすれば明示的なbreak
が不要です.
1 2 3 4 5 |
|
for h in 1L..N do
がカウントアップのfor
で, 二重ループだから二つ出てきます. 条件を満たした値を取る部分がif b then yield value
です. この場合はyield
キーワードはなくてもよいようですが手癖で書いています. 詳しくは公式のシーケンスを見てください. seq
とコンピュテーション式による見慣れない構文には慣れるしかありません.
seq {...}
でいわば遅延リストを作り, その先頭の値をSeq.head
で取れば必要な計算だけで処理が終わります. Schemeのように有理数を処理してくれる言語もありますが, F#標準で有理数はないため整数の範囲でおさまるように標準的な対処を取ります. 適当なところで打ち切った数による積で構成する三つ目の整数がint
に入る保証がないため, int64
で計算する点に注意すれば, あとは特に問題ないでしょう. 結論としては次のようなコードで通ります.
1 2 3 4 5 6 7 8 9 10 |
|
出力処理は何となく既存の出力処理を流用するために配列にしました. タプルのまま次のようにも書けます.
1 |
|
解説2: 再帰¶
「競技プログラミングのためのF#入門」で無限ループを含めてループは再帰で書けると書きました. 実際ここでも再帰で書けます. 提出結果を見ると再帰の方がメモリを食っています. 2022-12時点では効率を求めるよりも通るコードを書く, さらには基本的なアルゴリズムの教育用コンテンツを作る方に主眼があるため, 別解として再帰によるコードも紹介します.
for
のコードを素直に書き換えればよく, 結論としては次のように書けます.
1 2 3 4 5 6 7 8 9 10 |
|
ポイントはもちろんif
の条件分岐です. 最初に条件をみたして値を返すか(停止するか)判定し, 停止しなければh
かk
を適切にカウントアップします. ここでは上記のseq
+ループアルゴリズムに合わせました.
コードが読みにくくなるためここでは勧めませんが, 例えば次のようにまとめて書けます.
1 2 3 4 5 |
|
さらに次のようにも書けます.
1 2 |
|
let ... in
はOCamlのコードでよく出てきます.