SMU 2024年秋期 第1回個人戦 解説
A. 辞書順最小文字列生成
解法概要
2つの文字列を降順にソートし、交互に文字を取り出す。同じ文字列から連続して取り出す回数が制限値kを超えないようにしながら、最終的に辞書順が最小になるように構築する。
変更版コード例
#include <iostream>
#include <algorithm>
using namespace std;
void process() {
int lenA, lenB, maxSame;
cin >> le ...
7月12日 19:03 投稿
C言語で学ぶ二分木の基礎と応用
二分木の基本的な操作
二分木は、各ノードが最大2つの子ノードを持つ木構造です。この記事では、C言語を用いて二分木の作成、走査、特性の計算、および部分木の交換といった基本的な操作を実装する方法を学びます。
ノードの定義
二分木の各ノードは、データと左右の子ノードへのポインタを持ちます。以下にその構造体を示します。
struct Node {
char data;
str ...
7月11日 20:42 投稿
C言語プログラミング演習：関数とアルゴリズム
演習課題1：成績評価システム
#include <stdio.h>
char evaluate_score(int mark); // 関数宣言
int main() {
int mark;
char evaluation;
while(scanf("%d", &mark) != EOF) {
evaluation = evaluate_score(mark); // 関数呼び出し
printf("得点: %d, 評価: %c\n\n", mark, evaluation);
}
...
7月3日 21:29 投稿
バックトラッキングアルゴリズムとその応用問題
組合せ問題（Leetcode77）
// アプローチ: 1からnまでの数を再帰的に探索し、リストでk個の組み合わせが作成されたかを記録
// 各ループの開始値が前の値と重複しないように、開始インデックスを設定
class Solution {
private List<List<Integer>> 結果;
private List<Integer> 現在の組み合わせ;
private int 目標サイズ;
public ...
7月2日 17:53 投稿
二分探索法と再帰を用いたデータ構造の問題解決
1. 二次元配列内の要素検索
二次元配列（各一次元配列の長さが同じ）で、各行が左から右に昇順に、各列が上から下に昇順にソートされている場合、与えられた整数が配列内に存在するかを判断する関数を作成します。
public class Solution {
public boolean find(int target, int[][] array) {
for (int i = 0; i < array.length; i++) {
for (in ...
6月29日 23:37 投稿
Pythonにおける木構造の実装と応用
Pythonにおける木構造の実装と応用
木構造の基本概念
木構造は階層的な関係を模倣するデータ構造で、各要素はノードと呼ばれます。木の各ノードはゼロ個以上の子ノードを持つことができますが、各ノードは親ノードを一つしか持たない、という特徴があります。ルートノードだけは親ノードを持たない例外です。木構造の重要な特性は、循環がないことです。つまり、あるノー ...
6月24日 16:08 投稿
再帰関数の設計手法
1. はじめに
再帰は、関数型言語のみならず、あらゆるプログラミングパラダイムにおいて極めて重要な概念である。本稿では、数学的帰納法との関連性を踏まえながら、再帰関数の設計手法について体系的解説していく。
2. 再帰と数学的帰納法
2.1 数学的帰納法の原理
数学的帰納法は、自然数に関する命題を証明するための手法である。その原理は以下の2つのステップから ...
6月22日 22:05 投稿
二分木の中順走査：再帰と反復による実装
二分木の根ノード root が与えられたとき、中順走査（In-order Traversal）の結果を返す。
中順走査の順序は：左部分木 → 根ノード → 右部分木
二分木ノードの定義
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) { ...
6月21日 18:13 投稿
二分木の基本操作と実装
二分木の基礎知識（概念、特性、走査方法）について前回の記事で学びました。今回は主にコードの実装に焦点を当てます。
目次
二分木の疑似作成
二分木の走査
二分木のノード数の取得
二分木の葉ノード数の取得
二分木の第Kレベルのノード数の取得
二分木の高さの取得
二分木での要素検索
二分木の疑似作成
なぜ疑似作成と呼ぶのでしょうか。二分木の作成は非常に複雑なプ ...
6月17日 16:41 投稿
ソート済み配列を平衡二分探索木に変換する方法
二分探索木の中間順走査は昇順シーケンスを生成します。問題で与えられた配列は昇順でソートされているため、この配列は二分探索木の中間順走査シーケンスであることが保証されます。
1. 二分探索木の中間順走査が与えられた場合、二分探索木を一意に決定できるか？
答えは否定的です。もし二分探索木の高さバランスを要求しない場合、任意の数字を根ノードとして選択で ...
6月8日 21:28 投稿