n度あることはn+1度ある

書きたいことを書く 統一性はない

変わったforループの使用法

Linuxカーネルを少しだけ読む必要があり読んでいたのですが、面白いfor文の使われ方を見つけたのでご紹介致します。 該当部分は以下のマクロ #define for_each_process(p) \ for (p = &init_task ; (p = next_task(p)) != &init_task ; ) https://elixir.boo…

ABC114 所感

お疲れさまでした。最近さぼってた割にはそこそこ頑張れたんじゃないのかなと思います。今月はできるだけ復帰していきます。 A - 753 入力が7,5,3のときだけ"YES"をだす。 #include <bits/stdc++.h> using namespace std; int main(){ int x; cin>>x; if(x==7||x==5||x==3) </bits/stdc++.h>…

Dwango Programming Contest V B - Sum AND Subarrays

最近さぼりすぎなので頑張っていきたいです。 解答は解説で明らかなのですが、実装でてこずった問題。 flagを作るときにシフト演算を使用していたのですが、オーバーフローしていてずっと躓いていました。 シフト演算ではあまり大きなシフトを行うとオーバー…

ABC071 D - Coloring Dominoes

リハビリがてら解いた一問 特別な知識が必要ない問題です。ドミノの置き方のパターンを考えればOKです。 結論を言いますと、一番左のドミノが上下に積まれていれば6倍、一本ならば3倍。 上下にドミノが積まれている場合、左も上下に積まれていれば場合の数は…

ABC113 D - Number of Amidakuji

こちらに詳細を書きます。解法はDPです。データ構造はdp[i][j]で、問題の画像でいうところの、ind rowでjにたどり着ける場合の数です。 例えば以下の画像でj=1の線にいるとします。ここで、このポイントから移動できるのは、1から2へ線を引いた時のj=2と、1…

ABC113 所感

お疲れ様です。beta版がめちゃくちゃ重いコンテストでした。最近あまりこちらにモチベーションがないのと、これの影響であまり集中してできませんでした(言い訳) A - Discount Fare 半額になるほうを半額にして出力 #include <bits/stdc++.h> using namespace std; int ma</bits/stdc++.h>…

ABC104 D - We Love ABC

DPが本当に苦手なので解説も放送も野良解説も訳がわからなく苦労した問題。 i番目の文字に対して以下の情報を保存しながらDPします 0. i番目までで1つも文字を選ばない組み合わせ 1. i番目までで"A"までを選ぶ組み合わせ 2. i番目までで"AB"までを選ぶ組み合…

Tenka1 Programmer Beginner Contest 2018(天下一プログラマーコンテスト) 所感

コンテストお疲れさまでした。自分としては非常に悔しくも今までのコンテストの中で一番いい結果に終わりました。 コードはコンテストに提出したものそのままで、ブラッシュアップしていません。 以降ネタバレ注意 A - Measure 受け取った文字のサイズを見て…

Tenka1 Programmer Beginner Contest 2017 D - IntegerotS

bitの生成に難儀した問題。 詳しい解法は公式放送や解説を見てもらえれば分かると思います。 簡単に説明すると、与えられたkよりも小さな値でbitが立っている数値を足していき、一番大きなものを出力するというものです。一見230全てのパターンを行わなけれ…

ABC098 D - Xor Sum 2

ビット演算の性質とアルゴリズムの難しさが重なった問題でした。 XORというものは、A XOR BとA OR Bを考えたとき、必ずA XOR B ≦ A OR Bとなります。これは解説にもあるように、桁上がりがされないからです。 そのため、l=1,r=3が成り立ち、l=1,r=4がダメで…

ABC035 C - オセロ

初めてのいもす法を使用してACした問題。 いもす法とはいもすさんが考案されたアルゴリズムです。 自分も詳しく知っているわけではありませんが、配列の1番目から10番目まで2を足す、3番目から6番目まで5を足す....とやっていき、最後に配列の中身を表示する…

ABC067 D - Fennec VS. Snuke

木構造の性質を忘れていて解答ACしてしまった悔しい問題。 この問題は問題文に最大のヒントが与えられています。 マスと道から構成されるグラフは木です つまりこのグラフ上に閉路(ループ)は存在しません。ある点iからある点jに行くための道は1つしか存在…

ABC073 D - joisino's travel

初めてワーシャルフロイド法を使用した問題。 1つ前の記事で挙げた迷路のような、スタートとゴールがはっきりしている問題では幅優先探索が使用できますが、定まらない場合やグラフの全ての頂点と頂点間の最短距離を求めるのに有効なアルゴリズムとしてワー…

ABC088 D - Grid Repainting

初めて幅優先探索を使用する問題を解いてみました。 最短の道を通り、残りの白い面を埋めればACという考え方です。 幅優先探索自体は知っていたのですが、最初に見つかったゴールが最短ということを忘れており、チェックするのめんどくさいと投げ出してしま…

ABC044 C - 高橋君とカード / Tak and Cards

思考ではなくプログラムの実装で嵌った問題。 基本的な考え方は、満点解法2のように差分のDPを計算していき、最後に差分0の個数を出力するというものです。 単純にDPするとメモリが溢れそうですが、同じ差分が出力されるのでその個数をmapでとることで節約で…

ABC078 D - ABS

一見実装が難しそうですがめちゃめちゃ簡単な問題です。途中までできたのですが、ポイントに気づけず非常に悔しかったので記述。 与えられた数列がa,b,c,d,eとします。このときXがaを取る時、bを取る時...としたとき、取得ポイントは以下のようになります。 …

ABC046 C - AtCoDeerくんと選挙速報 / AtCoDeer and Election Report

難しく考えすぎてしまった300点問題。 解説では、新たに与えられた比を基準に考えていますが、自分は現在の投票数を新しい比に合わせることを考えてしまったため沼にハマりましたが一応ACできました。以下の考え方では互いに素でないとできない気がします。 …

ABC085 D - Katana Thrower

久しぶりのD問。本質的にはそこまで難しくないけど妙なところでひっかかっていたので簡単に書きます。 解説にもある通り、投げダメージが、殴りダメージの一番高い刀a_maxより高いダメージの刀を投げつけ、残ったダメージをa_maxで攻撃します。順序が逆です…

AGC028 A - Two Abbreviations

久しぶりに時間内(といってもペナルティ合わせて120分超え・・・)に300点問題をACできたので記念に書き込み。 まずLは必ずNとMの最小公倍数です。自分で書いてみると分かりますが、SとTで被る文字(一致すべき文字)は必ず一致します。そのため最小公倍数…

ABC110 C - String Transformation

解説がよく分からなかったので自分なりの考えと解法を載せます(本質的には変わらないと思います)。 問題の操作の内容としては、アルファベット1をアルファベット2と交換するというものです。ここで注目するのは全てのアルファベット1とアルファベット2を置…

ABC068 C - Cat Snuke and a Voyage

Union-Findを用いた解法で解いてみました。(Union-Findは前回紹介したものを使用) 入力が(a,b) ≠ (1,N)なので単純に以下のように解けます。ただしUnion-Findが実力を発揮するのは、a番目からb番目の島にたどり着けるか?のような問題だと思います。少々贅…

ABC075 C - Bridge

初めてUnion-Findを使用してACした問題なのでメモ。 流れとしては 1. i番目に入力された辺を除いたグラフを作る 2. その辺を構成する頂点が接続されているか確かめる といった感じです。 解説ではDFSを使用しているので、確認用の配列なども必要になりますが…

ABCで気をつけること(C/C++)

主に自分用のメモですが、コンテスト初心者がC/C++でやっていくにあたって注意していきたいことをメモ書きしていきます。(随時追加予定) intは使わない 計算途中でintの範囲を超える計算がC問以上からでてきます。 WAの理由がintの範囲を越えているから、と…

ABC104 C - All Green

久しぶりに問題を解いていたら、C問の中でも個人的に骨が折れた問題があったのでメモ ボーナス点という要素がなければ欲張り法で解ける問題ですが、これの所為で他の解説者の方の言う通り、2nの全解探索が必要です。 最高で1024通りを試しますが、対象の問題…

OpenCVでステガノグラフィの実験をしてみる

今までだ・である調を使ってブログを書いてきたが、普通に書きにくいので以下よりです・ます調でブログを書いていく。 以上蛇足 OpenCVを使って、画像に画像を埋め込むステガノグラフィ的なことをしてみました。 埋め込み対象画像 hidden.bmp 埋め込む画像 h…

珍しい(?)ギター・ベースの練習環境

楽器 →(シールド)→ AudioBox 22VSL →(モノラル→AUX)→ HD-DAC1 → ヘッドフォン みたいな感じで今現在練習している。 AudioBoxのつまみは小っさいのと、ヘッドフォンが今1つしかないのでジャックの抜き差ししたくないからこのような形になった。 ジャックの抜…

HD-DAC1の入力をUSBから光デジタルにした

入力が無いときにリレーが切り替わるとノイズが聞こえるレベルで発生し、電源を切ってもなっていたので光デジタルにした。 光デジタルにしたところ、今の所可聴レベルのノイズは発生していない。またSPDIF端子は音がなっていなくても、出力しっぱなしなよう…

マザボの光出力だとHD-DAC1から音が出ないときの解決策

症状 マザボのSPDIF出力からHD-DAC1に出力してもUNSUPPORTと表示される 原因 realtekの5.1chに非対応(ヘッドフォン用のDACだから当たり前?) 解決策 コンパネのサウンドから出力形式を2chにする

折り畳み傘のススメ

折り畳み傘を購入して半年くらい経ったが、とても素晴らしいので是非様々な人に使ってほしいという記事 折り畳み傘の良い点 傘の盗難・忘れを防止できる ビニール傘を盗まれたり、帰り際晴れていて傘を置き忘れたという経験は無いだろうか。 折り畳み傘は基…

Ubuntuでユーザー切り替えがうまくいかないときに

症状 新規に作成したユーザーでUbuntuにログインしようとすると、ログインGUIから移り変わらない 原因 ユーザーのホームディレクトリが作成されていない 解決策 adduserコマンドで作り直すなどホームディレクトリを作る 参考 qiita.com