今年の入試問題の数学(東工大)についての感想

はじめに

二次試験の当日に解いた感想と, 予備校の解答を見た感想を合わせて書きます. 解答見るまで, 大問4 (3) はわかりませんでした.

AtCoder Beginner Contest 115 の問題を解きました

abc115.contest.atcoder.jp

A問題

条件分岐を使って解く. または, 25 - 日は 回 Eve がつけば良いので, 演算子 * を使う.

計算量としては

B問題

1つの商品しか割引してもらえないので, 最大のものを割引してもらえば良い.

したがって, 偶数ということを加味して 最大値 と 総和を計算すれば解ける.

計算量としては

C問題

個 からなる集合 から 個のもの(部分集合)を取ってくる時の「最大値と最小値の差」の最小値を求める問題.

「最大値と最小値の差」を求めるのには, 個 をソートすると簡単に求められる. そこから, 直ちに最小値は求められる.

計算量としては,

D問題

レベル バーガー自体が レベル にバーガーによって定義されているので, 漸化式で解く,すなわち, 再帰をすれば良い.

{ レベル のバーガーの サイズ }, { レベル のバーガーに含まれるパティの数 }

とすれば, 簡単な漸化式を解くことで, , および が得られる. ( これはビット演算で簡単に計算可能 )

これから, 簡単な再帰関数を書けば良い. DP でメモ化する必要も, 末尾再帰にしてループにする必要もない.

なお, 自分は 再帰の止める部分で 2 WA しました.

計算量は ?

結果

438位 パフォーマンス 1322でした

反省点

やっぱり, まずはコードを書くスピードが遅いという点.

今回のミスに限って言えば, 32bit に収まらないということを 64bit に収まらないと勘違いして C++ のコードを一回 Python に直したことも時間のロスにつながった.

基本, 64bit で収まるはずの入力がくるはずだし, 競プロ は C 系 は不利にならないからそんなことはありえないと考えておくべきだった.

精進します

深さ優先探索

大学の講義の方で深さ優先探索( depth- first search : DFS ) や 幅優先探索( breath-first search : BFS ) について学んではいたが 実際にコードを書く経験はあまりなかったので訓練目的で以下の問題を解いて見ます

AtCoder Typical Contest の問題 atc001.contest.atcoder.jp

概要

スタック( Stack ) と キュー ( Queue )

深さ優先探索と幅優先探索の違いは, スタック ( Stack ) を用いるのか or キュー ( Queue ) を用いるのかという違いだけです.

スタック, キューはともにデータの保存 および 取り出しの機能を持つデータ構造です.

• スタック( Stack )
  保存したデータから新しいものから取り出すことができます.
  1, 2, 3, ... 10 の順番にデータを詰めたとしたら, 10, 9, 8 , ..., 1の順番で取り出されます.
  

  • 例 ) 思いつかなかったので, ここでは 僕のカバンにしておきます( 笑 )
    
    

• キュー ( Queue )
  逆に古いものから取り出すことができます.
  すなわち, 1, 2, 3, ..., 10 の順番にデータを詰めたとしたら, 1, 2, 3, ..., 10 の順番で取り出されます.
  

  • 例 ) ロケット鉛筆や, レジやラーメン屋の順番待ち

深さ優先探索と幅優先探索

以上のデータ構造の違いによって深さ優先探索と幅優先探索の違いが生まれます.

深さ優先探索は, スタック ( Stack ) を用いて 1方向に対してどんどん掘り下げていきます.

一方で, 幅優先探索は, 始点の位置から「距離が 1 のものを全て調べる」→「距離が 2 のものを全て調べる」

→ ... →「距離が n のものを全て調べる」... という風にグラフを調べていきます.

これらについての詳しい説明は

mathtrain.jp

などのもっと素晴らしいサイトを参照していただければ良いと思います.

My Answer

関数 dfsの引数に於いて, int aとなどとせずに, int &aとアドレスをするように, 引数に受け取るようにして
参照渡しとすることで, 関数 dfs 内部 Stackの反映が, main内のスタックに反映させられるようにしています.

// テンプレは省略
// 型の略称
using vc = vector<char>;
using vcc = vector<vc>;
using vb = vector<bool>;
using vbb = vector<vb>;

int n, m;

/* 深さ優先探索 ; ゴールに到着したら, true, 
                それ以外は スタックに詰めて falseを返す関数 */
bool dfs(int i, int j, vcc &dt, stack<pii> &st, vbb &ccd){
  if(0 <= i && i < n && 0 <= j && j < m){ // 配列内参照かチェック
    if(dt[i][j] == 'g') return true;
    if(dt[i][j] == '.' && !ccd[i][j]){ // 未到着でいける場所
      st.push(make_pair(i, j));
      ccd[i][j] = true;
    }
  }
  return false;
}


int main(){
  // 入力値の受け取り
  cin >> n >> m;
  int sx, sy, gx, gy;
  vcc data(n, vc(m)); char k;
  REP(i, n) REP(j, m){
      cin >> k;
      if(k == 's'){
        sx = i; sy = j;
      }
      else if(k == 'g'){
        gx = i; gy = j;
      }
      data[i][j] = k;
  }

  vbb checked(n,vb(m, false)); checked[sx][sy] = true;
  string yes = "Yes", no = "No"; // 出力用文字列
  stack<pii> search;  // スタック 
  search.push(make_pair(sx, sy));
  // 探索を行う
  while(!search.empty()){
    pii tmp = search.top(); search.pop(); // データの取り出し
    int x = tmp.first, y = tmp.second;
    bool TTT = dfs(x - 1, y, data, search, checked)
            || dfs(x + 1, y, data, search, checked)
            || dfs(x, y - 1, data, search, checked)
            || dfs(x, y + 1, data, search, checked);
    if(TTT){
      cout << yes << "\n";
      return 0;
    }
  }
  cout << no << "\n";
  return 0;
}

ブログとしての Hello World

はじめに

このブログについて

個人的なメモ書き程度のブログのつもりです ( 更新に関しては, 気の向いたときに行います )

ブログの内容としてが, 恐らくプログラミングや数学, その他好きな音楽などについて語るつもりでいます

その際 プログラミング言語としては, C++, Scala, Python についてとなると思います

なお, C++に関しては特に断りがなければ下のテンプレートを使うことを想定するつもりです

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <map>
#include <math.h>
using namespace std;

using lli = long long int;
using Vint = vector<int>;
using Vlli = vector<lli>;
using Wint = vector<Vint>;
using Wlli = vector<Vlli>;
using pii = pair<int, int>;
using pll = pair<lli, lli>;

const int MOD = 1e9 + 7;
const int INFi = 2e9 + 1;
const lli INFl = (lli)(9e18) + 1;
const vector<pii> DXDY = {make_pair(1, 0), make_pair(-1, 0), make_pair(0, 1), make_pair(0, -1)};
const char BR = '\n';

#define FOR(i, a, b) for(int (i) = (a); (i) < (b); (i)++)
#define FOReq(i, a, b) for(int (i) = (a); (i) <= (b); (i)++)
#define rFOR(i, a, b) for(int (i) = (b); (i) >= (a); i--)
#define FORstep(i, a, b, step) for(int (i) = (a); i < (b); i += (step))
#define REP(i, n) FOR(i, 0, n)
#define rREP(i, n) rFOR(i, 0, (n-1))
#define vREP(ele, vec) for(auto &(ele) : (vec))
#define SORT(A) std::sort((A).begin(), (A).end())


template <class T> inline int argmin(vector<T> vec){return min_element(vec.begin(), vec.end()) - vec.begin();}
template <class T> inline int argmax(vector<T> vec){return max_element(vec.begin(), vec.end()) - vec.begin();}
template <class T> inline void chmax(T &a, T b){a = max(a, b);}
template <class T> inline void chmin(T &a, T b){a = min(a, b);}
inline int toInt(string &s){int res = 0; for(char a : s) res = 10 * res + (a - '0'); return res;}
inline int toInt(const string s){int res = 0; for(char a : s) res = 10 * res + (a - '0'); return res;}
inline long long int toLong(string &s){lli res = 0; for(char a : s) res = 10 * res + (a - '0'); return res;}
inline long long int toLong(const string s){lli res = 0; for(char a : s) res = 10 * res + (a - '0'); return res;}
template <class T> inline std::string toString(T n){
  if(n == 0) return "0";
  std::string res = "";
  if(n < 0){n = -n;while(n != 0){res += (char)(n % 10 + '0'); n /= 10;} std::reverse(res.begin(), res.end()); return '-' + res;}
  while(n != 0){res += (char)(n % 10 + '0'); n /= 10;} std::reverse(res.begin(), res.end()); return res;
}

// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~



int main(){
  // code is here
  return 0;
}

おわりに

温かく見守ってください