$\huge{元氣ですかーーーーッ！！！}$
$\huge{元氣があればなんでもできる！}$
$\huge{闘魂とは己に打ち克つこと。}$
$\huge{そして闘いを通じて己の魂を磨いていく}$
$\huge{ことだと思います}$
はじめに
AtCoder Beginner Contest 409をElixirとRustで解いてみます。
AtCoderを解くのが趣味で、休憩時間に解いているという若い人がいて、それってすごい意識の高い休憩時間の過ごし方だと思って、私も真似してみることにしました。
AtCoderをElixirでやってみる
入力の読み取り方や解答の作り方は、別の記事にまとめています。
ご参照くださいませ。
ElixirでAtCoderを楽しむためには、エントリポイントをMain.main/0にする必要があります。つまりMainモジュールを作って、その中にmain/0関数を定義するわけです。
B - Citation
問題はリンク先をご参照くださいませ。
私の解答を貼っておきます。
プログラミングの基本である「順次」「分岐」「繰り返し」のうち、「順次」「分岐」「繰り返し」すべてを理解できているのかを問う問題です。
Elixir
Elixirを使った私の解答です。
私の解答(Elixir)
問題文を読んでいることを前提にひとこと解説をしておきます。
なかなかハマりました。
最初は「最大値から1に順に調べていく」素直な実装を試しましたが、A の要素が 10 ** 9 のような大きな値を取ると、100個調べるだけでも時間がかかり、TLE（実行時間超過）になってしまいました。
Elixirだから遅いのか？と思いRustに書き換えても、同じようにTLE。
ここで、計算量を減らすための発想の転換が必要だと気づきました。
問題の条件は：
「x 以上の値が、x 回以上ある」
これを別の角度から見ると、こう言い換えられます：
「大きな値が、少なくともその数（回数）だけ存在するか？」
これをもとに、次のように解法を再構築しました。
✨ 解法の発想転換
-
Aを降順にソートすることで、大きい値から順に並べる - ソートした配列の上から
i番目（1-indexed）に注目すると、
その位置の値A[i - 1]がi以上なら「i個のi以上の値がある」ことが分かる - この条件を満たす 最大の
iを答えとして返せばよい！
✅ 例：A = [10, 6, 3, 2, 2, 2, 1]（降順済）
| x (= i) | A[i-1] | A[i-1] ≥ x? | 条件成立？ |
|---|---|---|---|
| 1 | 10 | 10 ≥ 1 | ✅ |
| 2 | 6 | 6 ≥ 2 | ✅ |
| 3 | 3 | 3 ≥ 3 | ✅ |
| 4 | 2 | 2 ≥ 4 | ❌ |
したがって、最大の x は 3。
defmodule Main do
def main do
_ = IO.read(:line)
list =
IO.read(:line)
|> String.trim()
|> String.split()
|> Enum.map(&String.to_integer/1)
solve(list)
|> IO.puts()
end
def solve(list) do
list
|> Enum.sort(:desc)
|> Enum.with_index(1)
|> Enum.reduce(0, fn {value, idx}, acc ->
if value >= idx do
idx
else
acc
end
end)
end
end
Rust
RustはAI先生のお力をお借りして、Elixirのコードを置き換えてもらいました。
私は、Rustを勉強中です。万年勉強中です。闘魂にゴールはない。いつまでも挑戦中です。
私の解答(Rust)
use std::io::{self, BufRead};
fn main() {
let stdin = io::stdin();
let mut lines = stdin.lock().lines();
let _n: usize = lines.next().unwrap().unwrap().trim().parse().unwrap();
let mut list: Vec<u32> = lines
.next()
.unwrap()
.unwrap()
.split_whitespace()
.map(|s| s.parse().unwrap())
.collect();
let answer = solve(&mut list);
println!("{}", answer);
}
fn solve(list: &mut Vec<u32>) -> u32 {
list.sort_unstable_by(|a, b| b.cmp(a)); // 降順ソート
let mut result = 0;
for (idx, &val) in list.iter().enumerate() {
let x = (idx + 1) as u32;
if val >= x {
result = x;
} else {
break;
}
}
result
}
さいごに
AtCoder Beginner Contest 409をElixirとRustで解くことを楽しみました。
あなたのお好きなプログラミング言語でお楽しみください。
闘魂とは、 「己に打ち克つこと。そして闘いを通じて己の魂を磨いていくことである」 との猪木さんの言葉をそのまま胸に刻み込んでいます。
知っているだけで終わらせることなく、実行する、断行する、一歩を踏み出すことを自らの行動で示していきたいとおもいます。
アントニオ猪木さんのメッセージから元氣をもらったものとして、それを次代に語り継ぎ、自分自身が「闘魂」を体現するものでありたいとおもいます。
$\huge{元氣ですかーーーーッ！！！}$
$\huge{元氣があればなんでもできる！}$
$\huge{１、２、３ ぁっダァー！}$