Cプログラミング

この記事では、あらかじめ値が定められた4つの変数 a、b、c、d に応じて対応する括弧を出力し、それらをすべて使い切ったバランスの取れた括弧式を生成するCプログラムについて解説します。 問題の概要 各変数は、次の括弧ペアに対応しています。 a … (( b … () c … )( d … )) 求められているのは、与えられたすべての括弧を使い切ってバランスの取れた括弧式を出力することです。もしバランスの取れた式を構成できない場合は -1 を出力します。答えが複数存在する場合は、そのうちのどれを出力しても構いません。 入出力例 入力: a = 3, b = 2, c = 4, d = 3 出

概要 サイズ2×2以上の2次元配列（行列）が与えられたとき、その四隅に格納されているすべての要素を取り出し、合計を求めて出力するのが本記事のテーマです。 四隅の要素とは？ 行数「r」、列数「c」（いずれも0から開始）をもつ行列 mat[r][c] を考えると、四隅の要素は次の4つになります。 左上：mat[0][0] 右上：mat[0][c-1] 左下：mat[r-1][0] 右下：mat[r-1][c-1] したがって、求める合計は次の式で表されます。mat[0][0] + mat[0][c-1] + mat[r-1][0] + mat[r-1][c-1]これらの四隅の要素を取得して加算

N行M列のサイズを持つ行列が与えられたとき、各列に含まれる0の個数を数え、その個数に基づいて列をソートし、ソート後の列のインデックスを出力するのが課題です。 例えば、1列目に0が1つ含まれ、2列目には0がまったく含まれず、3列目に0が2つ含まれている場合、0の少ない順に並べると出力は「2 1 3」になります。 入力例と出力例 Input:     0 0 0     1 1 1     1 0 1 Output: 1 3 2 解説 上記の入力における各列の0の個数は次のとおり

N個の整数を含む配列 a[] が与えられたとき、そのインデックスのk個の異なる順列を出力することを考えます。ただし、それぞれの順列において、そのインデックスに対応する値が非減少列（昇順または同じ値が並ぶ列）になる必要があります。条件を満たす順列がk個作れない場合は -1 を出力します。入出力例入力: arr[] = {2,5,6,2,2,2,2}, k = 4 出力: 0 3 4 5 6 1 2 3 0 4 5 6 1 2 0 3 4 5 6 1 2 3 0 4 5 6 1 2解法のアプローチまず与えられた配列をソートし、同時に各要素の元のインデックスを記録して

本記事では、サイズnの整数配列と複数の回転位置kが与えられたとき、指定されたインデックスkから配列を左方向へ回転させた結果を出力する方法を、時間計算量O(n)・空間計算量O(1)の制約のもとで解説します。 配列の左回転とは、各要素を左へk個分ずらし、はみ出した要素を右端に折り返して配置する操作です。例えば、配列 {1, 2, 3, 4, 5} を1回左に回転すると {2, 3, 4, 5, 1} になります。 この手法の鍵となるのは剰余演算（%）です。回転後の配列を新たに作成することなく、インデックス計算だけで結果を直接出力できるため、追加のメモリ領域を一切必要としません。 入力例と出力例

N×N の行列が与えられたとき、M ≤ N かつ M ≥ 1 を満たすサイズ M×M の部分行列の中から、すべての要素の合計が最大となるものを見つけます。入力される行列には、0・正の整数・負の整数のいずれも含まれる可能性があります。 例 入力:     {{1, 1, 1, 1, 1},     {2, 2, 2, 2, 2},     {3, 3, 3, 3, 3},     {4, 4, 4, 4, 4},  &nbs

左の子と右の子を持つ二分木が与えられたとき、その木の最も左端および右端に位置するノード(コーナーノード)を出力するのが課題です。ここでいう「左端ノード」とは、各レベルにおいて親ノードから見て左側に連なるノードのことを指し、「右端ノード」とは、ルートから見て右側に連なるノードのことを指します。この問題は、キューを用いたレベル順走査(幅優先探索:BFS)で効率的に解くことができます。各レベルの最初のノードと最後のノードだけを結果に追加していけば、木全体の左右の端の値が得られます。例入力: 106 20 320 100 21 61 52 出力: 106 20 320 100 52この例では、各レベル

複数のスレッドが与えられたとき、それぞれの役割(優先度)に従って1から10までの数字を正しい順序で出力するプログラムを、C言語で作成します。 スレッドとは? スレッドとは、プログラムの内部で動作する軽量プロセスのことです。ひとつのシンプルなプログラムの中に、n個のスレッドを含めることができます。 Javaと異なり、C/C++の言語仕様自体はマルチスレッドをサポートしていません。C/C++でマルチスレッドを実現する際の標準として広く使われているのが、POSIX Threads(Pthreads)です。C言語にはマルチスレッドアプリケーション向けの組み込みサポートが用意されておらず、この機能は完全

文字列が与えられたとき、その文字列を「X」字型のパターンとして出力するプログラムを作成します。完成イメージは以下の通りです。考え方このパターンを実現するには、3つの変数を活用します。i：行ごとに左から右へ進む位置を表す変数j：右から左へ進む位置を表す変数（len-1-i で計算）k：各行内のスペースと文字の出力位置を判定するための変数各行では、k の位置が i または j と一致した場合にのみ該当する文字を出力し、それ以外の位置にはスペースを表示します。これにより、対角線上に文字が配置された「X」字型のパターンが描かれます。アルゴリズム 関数 void print(string str, in

問題概要N個の頂点とM個の辺からなる連結グラフが与えられます。このとき、頂点1から探索を開始した場合の幅優先探索(BFS)の訪問順序のうち、辞書式順序で最小となるものを出力します。ここで「辞書式順序で最小」とは、各ステップで訪問可能な頂点の中から常に最も小さい番号の頂点を選んでいく順序のことです。頂点には1からNまでの番号が付けられているものとします。入力例と出力例Input: N = 5 M = 5     edges(1,4, arr)     edges(3,4, arr)    

N個の頂点とM個の辺からなる連結グラフが与えられたとき、頂点1を起点として探索を行う深さ優先探索（DFS）のうち、辞書式順序で最も小さいトラバーサル順を出力することを考えます。なお、頂点には1からNまでの番号が割り当てられているものとします。入力例と出力例Input: N = 5 M = 5 edge(1, 4, arr) edge(3, 4, arr) edge(5, 4, arr) edge(3, 2, arr) edge(1, 5, arr) edge(1, 2, arr) edge(3, 5, arr) edge(1, 3

問題の概要 整数 n が与えられたとき、XOR（排他的論理和）演算を利用して、その数値を 2^X − 1 の形式に変換するまでの一連の手順を出力します。 操作のルール 奇数番目のステップ： 数値を任意の 2^M − 1（M は自分で選択可能）と XOR 演算します。 偶数番目のステップ： 数値を 1 増やします（インクリメント）。 この操作を、n が 2^X − 1 の形式になるまで繰り返し、実行したすべての手順を出力します。なお、最初から n が 2^X − 1 の形になっている場合は、実行すべき手順はありません。 入出力例 入力：22 出力： ステップ 1 : 15 と

長さnの文字列strが与えられます。この文字列の各要素の位置を出力し、それらを並べ替えることで回文を形成できるようにします。回文が作れない場合は、画面に「No palindrome」というメッセージを出力します。回文とは?回文とは、前から読んでも後ろから読んでも同じになる単語や文字列のことです。例えば「MADAM」や「racecar」などが挙げられます。ある文字列が回文かどうかを判定する一般的な方法は、元の文字列を逆順にしたものを別の文字列に保存し、両者を比較することです。両者が一致すれば、その文字列は回文であると判断できます。しかし本記事の問題では、回文の判定ではなく、与えられた文字列を並べ

n×nサイズの配列が与えられたとき、その整数型の行列要素を斜め下方向に出力するのが課題です。「斜め下方向」とは、任意のn×nサイズの配列を、下図のように左上から右下へ斜めに移動しながら順番に出力することを意味します。具体的には、まず「1」を出力し、次に「2」を出力した後、斜め下の「4」へ移動して出力します。この操作を行列のすべての要素に対して繰り返していきます。入力例と出力例入力：Matrix [3][3] = {    { 1, 2, 3 },    { 4, 5, 6 },    { 7, 8, 9 }} 出力：1 2 4 3 5

n×n の行列が与えられたとき、その行列を下三角行列(下三角形パターン)の形で出力するのが本記事のテーマです。下三角行列とは、主対角線より下の要素(主対角線上の要素を含む)が元の値をそのまま保持し、主対角線より上の要素がすべて 0 になった行列のことです。次の図を見ると理解しやすくなります。図の緑色の要素は主対角線より下(および主対角線上)の要素で、元の値がそのまま残ります。一方、赤色の要素は主対角線より上の要素で、すべて 0 に設定されます。入力と出力の例入力: matrix[3][3] = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9

本記事では、整数m個を含む配列arr[m]と、配列に加算する値nが与えられ、開始位置と終了位置を指定したr個のクエリを処理するCプログラムを紹介します。各クエリに対して、指定された開始インデックスから終了インデックスまでの範囲にあるすべての要素に値nを加算し、その結果を出力します。実行例入力: arr[] = {1, 2, 3, 4, 5} query[] = { { 0, 3 }, { 1, 2 } } n = 2 出力: Query1: { 3, 4, 5, 6, 5 } Query2: { 3, 6, 7, 6, 5 }この問題は、シンプルなアプローチで解決できます。手順は以下の通りで

この記事では、与えられた文字列の中から「接頭辞（プレフィックス）」と「接尾辞（サフィックス）」が一致する最長部分の長さを求めるC言語のプログラムを紹介します。 例えば、文字列 “abcab” の場合、先頭の “ab”（接頭辞）と末尾の “ab”（接尾辞）が一致しており、その長さは 2 です。これが「接頭辞と接尾辞が同一である最長の部分文字列」となります。 入力例と出力例 入力: str[] = { aabbccdaabbcc } 出力: 6 入力: abdab 出力: 2 一見すると、文字列の先頭と末尾にそれぞれポインタを置いて比較すればよさそうに思えます。しかし、その方法では途中でポインタ

この記事では、与えられた二分木（バイナリツリー）の左側ビュー（Left View）、すなわち木を左側から見たときに見えるノードを出力する方法を解説します。ユーザーがデータを挿入して二分木を構築し、その後、完成した木の左側ビューを表示するという流れです。 二分木の各ノードが持てる子は最大2つなので、プログラムは各ノードに紐づく左ポインタを優先的にたどる必要があります。 左ポインタがNULLでなければ、その先に子ノード（データ）が存在します。各レベルで最初に到達した最左ノードを出力対象とし、それを画面に表示します。 例 入力：1 0 3 2 4 出力：1 0 2 図のオレンジ色のノードが、二分木

この記事では、二分木（バイナリツリー）において、ユーザーが指定したレベル k にあるリーフノード（葉ノード）を出力する方法を解説します。リーフノードとは、左ポインタと右ポインタがどちらも NULL になっている終端ノードのことです。つまり、そのノードには子ノードが存在せず、親ノードとしての役割を持たないノードを指します。例入力 : 11 22 33 66 44 88 77 出力 : 88 77ここで k は、出力対象となる木のレベルを表しています。基本的なアプローチは、すべてのノードを走査しながら、そのノードが子へのポインタを持っているかどうかを確認することです。左・右のいずれか一方、あるいは

問題の概要この問題では、n個の正の整数からなる配列が与えられ、その中から最大のAND値を持つペアを見つける必要があります。例入力: arr[] = { 4, 8, 12, 16 } 出力: pair = 8 12 最大AND値 = 8 入力: arr[] = { 4, 8, 16, 2 } 出力: pair = No possible AND 最大AND値 = 0アプローチ最大AND値の求め方は、配列内の最大AND値を求める問題と基本的な考え方は同じです。ただし、このプログラムでは、その最大AND値を実際に生み出す要素のペアまで特定する必要があります。要素を特定するには、配列全体を走査し、各