ABC454 C - Straw Millionaire

ABC454 C

アプローチ

入力 A, B を A → B の有向グラフで保持
グラフをDFS(深さ優先探索)で操作した結果の辿り着いた箇所を数えた
渡すアイテム A が減ることがないから、A → B で辿れる箇所を見つけるだけでOK

コード

import fs from 'fs';

const main = (): void => {
  const input = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
  let idx = 0;
  const next = (): number => input[idx++];
  const N = next(), M = next();
  const items: number[][] = Array.from({ length: N }, () => []);
  for (let i = 0; i < M; i++) {
    const A = next() - 1, B = next() - 1;
    items[A].push(B);
  }

  const seen: boolean[] = Array(N).fill(false);
  const dfs = (val: number): void => {
    seen[val] = true;
    for (let i = 0; i < items[val].length; i++) {
      const next = items[val][i];
      if (seen[next]) continue;
      dfs(next);
    }
  } 

  dfs(0);
  let ans = 0;
  for (let i = 0; i < N; i++) {
    if (seen[i]) ans++;
  }
  console.log(ans);
}
main();

ABC476 C - Third Largest Number

ABC476 C

問題文

3 以上の整数 N と長さ N の正整数列 A = ( A1, A2, …, AN ) が与えられます。

k=3,4,…,N それぞれに対し以下の問題を解いてください:

A1, A2, …,Ak を降順に並べたとき、前から 3 番目にくる値を求めてください。

制約

3 ≤ N ≤ 5 × 105

1 ≤ Ai ≤ 109

入力される値は全て整数

アプローチ

愚直に 3, 4, 5, ...N と触れていくサイズを増やしながら配列操作を行うのは、
制約上、タイムオーバーになるのが目に見えているため、
問題文にある 前から3番目に注目し、1から3番目までを保持する方針をとった
前準備として、入力 A の先頭から3番目までを事前にソートし、
各変数にて保持をしておき、以降の A の要素を1つずつ各変数と比較していった

コード

import fs from 'fs';

const main = (): void => {
  const [N, ...A] = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
  let [first, second, third] = [...A.slice(0, 3).sort((a, b) => b - a)];
  for (let i = 3; i < N + 1; i++) {
    console.log(third);
    if (first <= A[i]) {
      [first, second, third] = [A[i], first, second];
    } else if (second <= A[i]) {
      [second, third] = [A[i], second];
    } else if (third <= A[i]) {
      third = A[i];
    }
  }
}
main();

ABC075 C - Bridge

(ABC075 C - Bridge)https://atcoder.jp/contests/abc075/tasks/abc075_c "ABC075 C -Bridge"

Approach

  • グラフはboolean配列で作成
    number配列の場合、辺の除外と戻す操作が困難に感じた
  • 探索の中で辿った頂点を表すseen変数(boolean[])、
    探索操作後にseen変数にfalseの要素が存在する、つまり除外した辺は橋となるため、
    その数を数えればいい

Code

import fs from 'fs';

const main = (): void => {
  const input = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
  let idx = 0;
  const next = (): number => input[idx++];
  const N = next(), M = next();
  const graph: boolean[][] = Array.from({ length: N }, () => Array(N).fill(false));
  for (let i = 0; i < M; i++) {
    const a = next() - 1;
    const b = next() - 1;
    graph[a][b] = true;
    graph[b][a] = true;
  }

  const dfs = (val: number, ary: boolean[][], trace: boolean[]): void => {
    trace[val] = true;

    for (let i = 0; i < ary[val].length; i++) {
      if (!ary[val][i]) continue;
      if (trace[i]) continue;
      dfs(i, ary, trace);
    }
  }

  let ans = 0;
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      if (!graph[i][j]) continue;   // 辺なしはスキップ
      [graph[i][j], graph[j][i]] = [false, false];    // 辺を除外
      const seen: boolean[] = Array(N).fill(false);

      dfs(0, graph, seen);

      if (seen.includes(false)) ans++;
      [graph[i][j], graph[j][i]] = [true, true];    // 除外した辺を戻す
    }
  }

  console.log(ans/2);
}
main();

AGC016 A - Shrinking

AGC016 A - Shrinking

Approach

  • 制約 (|s| ≦ 100) と緩いため、a ~ z の考えうる文字で全探索を実施
    最悪でも O(N2*26) 程度に収まるため、全探索でも間に合う
  • 操作後の新しい文字列の i 文字目は、元の文字列の i 文字目または i+1 文字目のどちらかとなる
    目的の文字を多く残したいため、貪欲に「 i+1 文字目が求めている文字なら i 文字目を i+1 文字目で書き換える」 という操作だけを行い、それ以外の場合は i 文字目のままとする
    注:TypeScriptで解いているため、文字列の変更ができず配列で操作

Code

import fs from 'fs';

const main = (): void => {
  const str = fs.readFileSync(0, 'utf8').trim();
  let ans = Infinity;

  // a ~ z まで
  for (let i = 97; i < 123; i++) {
    const c = String.fromCharCode(i);
    const tmp = [...str];
    if (!tmp.includes(c)) continue;

    let count = 0;

    const calc = (): number => {
      // 全文字が c に揃う間
      while (true) {
        const char = tmp[0];

        // 全文字が c に揃っているか確認
        for (let k = 0; k < tmp.length; k++) {
          if (char !== tmp[k]) break;
          if (k === tmp.length - 1 && char === tmp[k]) return count;
        }

        for (let j = 0; j < tmp.length - 1; j++) {
          if (tmp[j+1] === c) tmp[j] = tmp[j+1];
        }
        tmp.pop();
        
        count++;
      }
    }
    ans = Math.min(ans, calc());
  }

  console.log(ans);
}
main();

競プロ典型90問 084 - There are two types of characters

典型90問 084

問題文

o と x からなる長さ N の文字列 S が与えられます。

以下の条件をすべて満たす整数の組 (l,r) の個数を求めてください。

  • 1≤l≤r≤N
  • S の l 文字目から r 文字目までの区間に、o と x 両方が含まれる

制約

  • 1≤N≤106
  • S は o, x からなる長さ N の文字列である

考えたこと

二重ループで愚直に探すのは制約上不可能なので、
ランレングス圧縮で同一マークがどれだけ続いているか調べ、
調べあげた文字数と、それ以降の残数から導く方法をとった。
調べあげた文字数は、l に該当し圧縮処理が途切れた、つまり別のマーク(r に該当)に、
出会ったことになるため、l までの個数と r 以降の個数を掛け合わせれば良い
あとは、上記を S の最後まで繰り返し足し合わせていけば完了

コード

import fs from 'fs';

const main = (): void => {
  const input = fs.readFileSync(0, 'utf-8').trim().split('\n');
  const N = Number(input[0]), S = input[1];
  let total = 0;
  for (let i = 0; i < N;) {
    let j = i;
    // 同一文字数チェック(圧縮のメイン)
    while (j < N && S[i] === S[j]) j++; 
    // 同一文字数 x 全体から同一文字数分を引いた数
    i = j;
    total += (j - i) * (N - j);
  }
  console.log(total);
}
main();

ABC108 C

ABC108-C - Triangular Relationship

考えたこと

制約上、for文を1つに抑えたかったので愚直にa,b,cを全探索はできないため、色々考えた。
mod Kの結果として考えられる値は、K-1なのでその範囲でどうにか実装できないか、
mod Kの結果は1...K-1, 0の範囲をN/K週(プラスN mod K)分繰り返されることを、
理解できたからその結果を元にどうにか実装できないか、結局は以下の考え方でなんとかできた。

1...Nまでの mod Kを持つリストを用意し、
そのリスト内に条件を満たす要素がいくつ存在するかを探した。
条件(Kの偶奇によって分岐)
偶数
 mod K の値はN/2もしくは0であること
奇数
 mod K の値は0であること
上記の条件をスルーしたリスト内の要素を数え、その要素数の3乗の合計値が答えとなる。
3乗となる理由は、a,b,cの3パターンに格要素全てが考えられる、
例えば、(a,a,a), (a,a,b), (b,a,a), (a,a,b)これらはすべて別の扱いとなる。

import fs from 'fs';
const input = fs.readFileSync('/dev/stdin', 'utf-8').trim();

const main = (): void => {
  const [N, K] = input.split(/\s+/).map(Number);
  const list: number[] = [];
  for (let i = 1; i <= N; i++) {
    list.push(i%K);
  }
  if (K%2===0) {
    const tmp2 = list.filter(e => e === K/2);
    const tmp0 = list.filter(e => e === 0);
    console.log(tmp2.length**3 + tmp0.length**3);
  } else {
    const tmp0 = list.filter(e => e === 0);
    console.log(tmp0.length**3);
  }
}
main();

AtCoder Begginer Contest 084

ABC084-D.2017-like Number

概要

「N も (N + 1) / 2 も素数」を満たす奇数 N
上記を満たす値を2017に似た数とし、
与えられた区間にいくつ存在するかを問われている。

考え

1..105(制約 r <= 105)の区間で2017に似た数の総数を保持する累積和を作って、
与えられた、l , r (r+1) の区間で似た数が存在するかを出力すればいけると考えた。

素数か否か

i が素数か否かを表す配列を用意

  const rMax = 10**5;
  // エラトステネスの篩
  const flag = (): number[] => {
    const list = Array.from({ length: rMax },() => 1);
    list[0] = 0, list[1] = 0;
    for (let i = 2; i <= rMax; i++) {
      if (list[i]) {
        for (let j = i*2; j <= rMax; j+=i) {
          list[j] = 0;
        }
      }
    }
    return list;
  }

2017に似た数か否か

素数判定の配列に対して、
問いの条件を満たすか否かを表す配列を用意

  const flagList = flag();
  const prefix = Array.from({ length: rMax }, () => 0);
  for (let i = 0; i < rMax; i++) {
    if (flagList[i] && flagList[Number((i+1)/2)]) {
      prefix[i] = 1; 
    }
  }

累積和

2017に似た数が i までに幾つ存在するかを表す配列

  const a = Array.from({ length: rMax+1 }, () => 0);
  for (let i = 0; i < rMax; i++) {
    a[i+1] = a[i] + prefix[i];
  }

提出コード

import fs from 'fs';
const input = fs.readFileSync('/dev/stdin', 'utf-8').trim();

const main = (): void => {
  const rMax = 10**5;
  // エラトステネスの篩
  const flag = (): number[] => {
    const list = Array.from({ length: rMax },() => 1);
    list[0] = 0, list[1] = 0;
    for (let i = 2; i <= rMax; i++) {
      if (list[i]) {
        for (let j = i*2; j <= rMax; j+=i) {
          list[j] = 0;
        }
      }
    }
    return list;
  }
  // 2017-likeかどうか
  const flagList = flag();
  const prefix = Array.from({ length: rMax }, () => 0);
  for (let i = 0; i < rMax; i++) {
    if (flagList[i] && flagList[Number((i+1)/2)]) {
      prefix[i] = 1; 
    }
  }
  // 累積和
  const a = Array.from({ length: rMax+1 }, () => 0);
  for (let i = 0; i < rMax; i++) {
    a[i+1] = a[i] + prefix[i];
  }
  const lines = input.split(/\s+/).map(Number);
  const Q = lines[0];
  for (let i = 0; i < Q; i++) {
    const right = lines[i*2+1];
    const left = lines[i*2+2];
    console.log(a[left+1]-a[right])
  }
}
main();