noyのブログ

プログラミングとかゲームとか

AtCoder Beginner Contest D問題ジャンル分け

imos法 D: 感雨時刻の整理 - AtCoder Beginner Contest 001 | AtCoder 全探索 D: 派閥 - AtCoder Beginner Contest 002 | AtCoder D: バレンタインデー - AtCoder Beginner Contest 018 | AtCoder D: 語呂合わせ - AtCoder Beginner Contest 031 | AtCoder D…

ARC016 - C ソーシャルゲーム

C: ソーシャルゲーム - AtCoder Regular Contest 016 | AtCoder 問題概要 商品が n 種類、くじが m 種類あります。 くじを一度引くのにお金がかかります。 くじからは、ある確率である商品が手に入ります。最善を尽くしたとき、全ての商品を集める金額の期待…

ARC067 - E Grouping

E: Grouping - AtCoder Regular Contest 067 | AtCoder 問題概要 N 人をグループ分けします。 一つのグループにつき A ~ B 人で構成し、 同じ人数のグループは 0 か C ~ D 個作らなければいけません。 このようなグループ分けは何通りありますか。 DPの解説 …

ABC009 - D 漸化式

D: 漸化式 - AtCoder Beginner Contest 009 | AtCoder 問題概要 二つの数列 と が入力で与えられる。数列 A は以下の式によって計算できる。 数列 A の M 番目の値を求めよ。 解き方 漸化式を計算するには、DPを使えば良いです。しかし、制約が大きく、DPで…

ABC025D - 25個の整数

D: 25個の整数 - AtCoder Beginner Contest 025 | AtCoder 解説を見て実装を放置していたため、考察要素はないです。 問題概要 5 * 5 のマスがあります。 1 ~ 25 までの数値を、各マスに一つずつ書きます。 ただし、以下の条件を満たすように書かなければい…

AOJ 0553 ダンジョンの解説

AOJ 0553 ダンジョン ダンジョン | Aizu Online Judge 考察 問題点 あり本にある優先度キューを用いたガソリン問題と似ています。 ただし、こちらの問題では、ガソリンを入れられる量の上限があります。体力が0以下になる前に、どこかで回復しなければいけな…

構文解析初心者でも解ける問題を集めた+解説

競技プログラミングにおいての構文解析問題を集めました。難易度はAOJ-ICPCで300点程度です。

vimに構文チェックのプラグインを入れた(C++)

syntastic 導入の流れ 導入してわかったこと ファイル上書き時に構文チェックされる。 割と重い w0rp/ale Asynchronous Lint Engine 導入してわかったこと syntasticと比べて速い 結論 syntastic このようになりました。 導入の流れ GitHub - vim-syntastic/…

AOJ 1249 Make a Sequence

Make a Sequence | Aizu Online Judge AOJ-ICPC 200点所用時間:1時間30分 遅すぎる。実装力が足りてない。 問題概要 簡単に言うと3次元五目並。 n * n個のマスがある。黒いボールと白いボールを交互に置いていき、先にm個一直線に並べれば勝ち。 同じマスに…

AOJ - 2170 Marked Ancestor

Marked Ancestor | Aizu Online Judge 問題概要 木が与えられる。 以下の2つのクエリを処理し、出力された番号の合計を求める。 頂点aをマークする 頂点aから最も近いマークされた祖先の番号を出力する 解法 union-findこのスライドにある解法をそのまま実…

『SOFT SKILLS ソフトウェア開発者の人生マニュアル』の各章を1行でまとめた

『SOFT SKILLS ソフトウェア開発者の人生マニュアル』の内容を各章ごとに1行で表した。 章を要約するつもりで書いたが、上手くできているかはわからない。 第1部 02. 自分自身はソフトウェアを作れる能力を提供する事業である 03. キャリアの目的を決めよう …

ネットワークインターフェイスの名前

MacBook Air でifconfigして表示されたネットワークインターフェイス一覧。lo0 ループバックアドレスgif0 トンネリングを行うen0 Etherneten1 有線のEtherneten1 Air Macstf0 IPv6パケットをIPv4ネットワークにルーティングするp2p0 Air Dropの機能用awdl0 H…

vimで構文ハイライトをいじった

こんな感じに。 おしゃれしたい 競技プログラミングでよく使うマクロやデータ構造に色をつけたくなったので構文ハイライトをいじった。これでforとrepが肩を並べるよう(同じ色)になり、デバッグ用のマクロが目立つようになった。 あと、色がついて気分が良…

sshでリモートマシンへログインする際にやったこと

ログインするだけなのに時間がかかった。 mac -> VMware CentOS7 opensshのインストール yum install openssh-server sshdサービスの起動 systemctl start sshd-serviceここでエラーが出て実行できなかった。SELinuxが原因な気がしたので、 setenforce permi…

グラフ メモ

連結 任意の2点間に辺がある。 連結グラフは、グラフ上の任意の2点間に辺があるグラフのこと。 関節点 削除すると部分グラフが非連結になる点。 橋 削除すると部分グラフが非連結になる辺。 強連結 任意の2点間に有向路がある、という条件を満たしている有…

典型探索問題を解く

問題の解法が浮かばないなら、とりあえず解法の全探索をすればいいと思った。パラメータそれぞれに注目して解けるか考える。 DPなら、テーブルに何を持つかを全通り考えてみる。 AOJ ALDS1_4-D Search - Allocation 問題概要 数字がn個与えられる。それをk個…

Binary Indexed Tree(BIT)を学ぶ(1)

BITとはなんぞや POJ1990 MooFest 解法 コード 参考 BITとはなんぞや 参考:蟻本159頁列a_1, a_2, ... , a_nがある。 iが与えられたとき、a_1からa_iまでの和を求める。 (iとjが与えられたとき、a_iからa_jまでの和を求める。) iとxが与えられたとき、 a_i +…

やるだけ問題について メモ

やるだけ問題で特に気を付けること 別にやるだけ問題に限ったことではないけれど。 細かく関数化する できるだけ処理を分けて考えること。見やすいし、後になって直しやすい。main関数だけに書かれたコードを直すのは精神的にとてもつらい。 やるだけ問題を…

C++ 素数を求める2種類の方法

素数を求める方法 ひとつ目は愚直な割り算の繰り返し。ふたつ目はエラトステネスのふるい。割り算を繰り返せば、どんな素数でも求められる。しかし、多くの数を素数か判定するのには遅すぎる。 エラトステネスさえ覚えれば、多くの素数問題は攻略できる。し…

ABC021 C 正直者の高橋君

C: 正直者の高橋くん - AtCoder Beginner Contest 021 | AtCoder状態AC AC AC WA AC . . . AC_人人人人人人人人人人_ > なぜかACできない <  ̄Y^Y^Y^Y^Y^Y^Y^Y^Y ̄ #include<bits/stdc++.h> #define range(i,a,b) for(int i = (a); i < (b); i++) #define rep(i,b) rang</bits/stdc++.h>…

ABC026 C 高橋君の給料

C: 高橋君の給料 - AtCoder Beginner Contest 026 | AtCoder 解説に書いてある解法、再帰で解いた。 ただ、なんとなく通してしまったのであまり考えていない。 そこで、ちょっとは頭を使ってみる。 #include<bits/stdc++.h> #define range(i,a,b) for(int i = (a); i < (b);</bits/stdc++.h>…